class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

def insert(self, value):
    # 創(chuàng)建一個(gè)新節(jié)點(diǎn)
    new_node = Node(value)
    # 如果樹(shù)為空，則將新節(jié)點(diǎn)設(shè)為根節(jié)點(diǎn)
    if self.root is None:
        self.root = new_node
        return
    # 否則從根節(jié)點(diǎn)開(kāi)始遍歷
    current = self.root
    while True:
        # 如果要插入的值小于當(dāng)前節(jié)點(diǎn)的值，則向左走
        if value < current.value:
            # 如果左子節(jié)點(diǎn)為空，則將新節(jié)點(diǎn)設(shè)為左子節(jié)點(diǎn)
            if current.left is None:
                current.left = new_node
                return
            # 否則繼續(xù)向左走
            else:
                current = current.left
        # 如果要插入的值大于當(dāng)前節(jié)點(diǎn)的值，則向右走
        elif value > current.value:
            # 如果右子節(jié)點(diǎn)為空，則將新節(jié)點(diǎn)設(shè)為右子節(jié)點(diǎn)
            if current.right is None:
                current.right = new_node
                return
            # 否則繼續(xù)向右走
            else:
                current = current.right
        # 如果要插入的值等于當(dāng)前節(jié)點(diǎn)的值，則不做任何操作，并返回
        else:
            return

def search(self, value):
    # 如果樹(shù)為空，則返回False
    if self.root is None:
        return False
    # 否則從根節(jié)點(diǎn)開(kāi)始遍歷
    current = self.root
    while current is not None:
        # 如果要查找的值小于當(dāng)前節(jié)點(diǎn)的值，則向左走
        if value < current.value:
            current = current.left
        # 如果要查找的值大于當(dāng)前節(jié)點(diǎn)的值，則向右走
        elif value > current.value:
            current = current.right
        # 如果要查找的值等于當(dāng)前節(jié)點(diǎn)的值，則返回True
        else:
            return True
    # 如果遍歷完畢還沒(méi)有找到，則返回False
    return False

def delete(self, value):
    # 如果樹(shù)為空，則返回None
    if self.root is None:
        return None
    # 否則從根節(jié)點(diǎn)開(kāi)始遍歷
    current = self.root
    parent = None
    while current is not None and current.value != value:
        # 記錄父節(jié)點(diǎn)
        parent = current
        # 如果要?jiǎng)h除的值小于當(dāng)前節(jié)點(diǎn)的值，則向左走
        if value < current.value:
            current = current.left
        # 如果要?jiǎng)h除的值大于當(dāng)前節(jié)點(diǎn)的值，則向右走
        else:
            current = current.right
    # 如果沒(méi)有找到要?jiǎng)h除的元素，則返回None
    if current is None:
        return None
    # 定義一個(gè)輔助函數(shù)，用來(lái)找到一棵樹(shù)中最?。ɑ蜃畲螅┰厮诘慕Y(jié)點(diǎn)和其父結(jié)點(diǎn)，參數(shù)是根結(jié)點(diǎn)和一個(gè)布爾變量，表示是否尋找最小元素，默認(rèn)為T(mén)rue，如果為False則尋找最大元素
    def find_min_max(node, is_min=True):
        # 初始化最?。ɑ蜃畲螅┙Y(jié)點(diǎn)和其父結(jié)點(diǎn)
        min_max = node
        parent = None
        # 如果尋找最小元素，則一直向左走，否則一直向右走
        if is_min:
            while min_max.left is not None:
                parent = min_max
                min_max = min_max.left
        else:
            while min_max.right is not None:
                parent = min_max
                min_max = min_max.right
        # 返回最小（或最大）結(jié)點(diǎn)和其父結(jié)點(diǎn)
        return min_max, parent
    # 如果當(dāng)前結(jié)點(diǎn)沒(méi)有子結(jié)點(diǎn)，則直接刪除該結(jié)點(diǎn)，并返回None
    if current.left is None and current.right is None:
        # 如果是根結(jié)點(diǎn)，則將根結(jié)點(diǎn)設(shè)為None
        if parent is None:
            self.root = None
        # 否則判斷是父結(jié)點(diǎn)的左子結(jié)點(diǎn)還是右子結(jié)點(diǎn)，并將其設(shè)為None
        else:
            if parent.left == current:
                parent.left = None
            else:
                parent.right = None
        return None
    # 如果當(dāng)前結(jié)點(diǎn)只有一個(gè)子結(jié)點(diǎn)，則直接用該子結(jié)點(diǎn)替換該結(jié)點(diǎn)，并返回該子結(jié)點(diǎn)
    if current.left is None or current.right is None:
        # 找到該子結(jié)點(diǎn)，可以是左子結(jié)點(diǎn)也可以是右子結(jié)點(diǎn)
        child = current.left if current.left is not None else current.right
        # 如果是根結(jié)點(diǎn)，則將根結(jié)點(diǎn)設(shè)為該子結(jié)點(diǎn)
        if parent is None:
            self.root = child
        # 否則判斷是父結(jié)點(diǎn)的左子結(jié)點(diǎn)還是右子結(jié)點(diǎn)，并將其設(shè)為該子結(jié)點(diǎn)
        else:
            if parent.left == current:
                parent.left = child
            else:
                parent.right = child
        return child
    # 如果當(dāng)前結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，則先在其右子樹(shù)中找到最小值（或者在其左子樹(shù)中找到最大值），然后用該最小（或最大）值替換該結(jié)點(diǎn)，并遞歸地在其右（或左）子樹(shù)中刪除該最?。ɑ蜃畲螅┲?，并將刪除后的右（或左）子樹(shù)設(shè)為該結(jié)點(diǎn)的右（或左）子節(jié)點(diǎn)
    # 這里我們選擇在右子樹(shù)中找到最小值，也可以在左子樹(shù)中找到最大值，只要保證替換后的結(jié)點(diǎn)滿足二叉搜索樹(shù)的性質(zhì)即可
    min_node, min_parent = find_min_max(current.right, is_min=True)
    # 用最小值替換當(dāng)前結(jié)點(diǎn)的值
    current.value = min_node.value
    # 遞歸地在右子樹(shù)中刪除最小值，并將刪除后的右子樹(shù)設(shè)為當(dāng)前結(jié)點(diǎn)的右子節(jié)點(diǎn)
    current.right = self.delete(min_node.value)
    return current

def pre_order(self, node):
    # 如果結(jié)點(diǎn)為空，則返回
    if node is None:
        return
    # 先訪問(wèn)根節(jié)點(diǎn)，打印其值
    print(node.value, end=" ")
    # 再訪問(wèn)左子樹(shù)，遞歸調(diào)用前序遍歷函數(shù)
    self.pre_order(node.left)
    # 最后訪問(wèn)右子樹(shù)，遞歸調(diào)用前序遍歷函數(shù)
    self.pre_order(node.right)
def in_order(self, node):
    # 如果結(jié)點(diǎn)為空，則返回
    if node is None:
        return
    # 先訪問(wèn)左子樹(shù)，遞歸調(diào)用中序遍歷函數(shù)
    self.in_order(node.left)
    # 再訪問(wèn)根節(jié)點(diǎn)，打印其值
    print(node.value, end=" ")
    # 最后訪問(wèn)右子樹(shù)，遞歸調(diào)用中序遍歷函數(shù)
    self.in_order(node.right)
def post_order(self, node):
    # 如果結(jié)點(diǎn)為空，則返回
    if node is None:
        return
    # 先訪問(wèn)左子樹(shù)，遞歸調(diào)用后序遍歷函數(shù)
    self.post_order(node.left)
    # 再訪問(wèn)右子樹(shù)，遞歸調(diào)用后序遍歷函數(shù)
    self.post_order(node.right)
    # 最后訪問(wèn)根節(jié)點(diǎn)，打印其值
    print(node.value, end=" ")

def height(self, node):
    # 如果結(jié)點(diǎn)為空，則返回0
    if node is None:
        return 0
    # 否則返回左右子樹(shù)中較大的高度加1
    return max(self.height(node.left), self.height(node.right)) + 1
def size(self, node):
    # 如果結(jié)點(diǎn)為空，則返回0
    if node is None:
        return 0
    # 否則返回左右子樹(shù)的大小之和加1
    return self.size(node.left) + self.size(node.right) + 1
def kth_smallest(self, node, k):
    # 如果結(jié)點(diǎn)為空，則返回None
    if node is None:
        return None
    # 定義一個(gè)輔助函數(shù)，用來(lái)計(jì)算一棵樹(shù)中有多少個(gè)小于等于給定值的元素，參數(shù)是根結(jié)點(diǎn)和給定值
    def count_less_equal(node, value):
        # 如果結(jié)點(diǎn)為空，則返回0
        if node is None:
            return 0
        # 如果結(jié)點(diǎn)的值小于等于給定值，則返回左子樹(shù)的個(gè)數(shù)加右子樹(shù)中小于等于給定值的個(gè)數(shù)加1
        if node.value <= value:
            return count_less_equal(node.left, value) + count_less_equal(node.right, value) + 1
        # 如果結(jié)點(diǎn)的值大于給定值，則返回左子樹(shù)中小于等于給定值的個(gè)數(shù)
        else:
            return count_less_equal(node.left, value)
    # 計(jì)算當(dāng)前結(jié)點(diǎn)左子樹(shù)中有多少個(gè)元素
    left_count = self.size(node.left)
    # 如果左子樹(shù)中有k-1個(gè)元素，則當(dāng)前結(jié)點(diǎn)就是第k小元素，返回其值
    if left_count == k - 1:
        return node.value
    # 如果左子樹(shù)中有超過(guò)k-1個(gè)元素，則第k小元素在左子樹(shù)中，遞歸調(diào)用函數(shù)在左子樹(shù)中查找
    elif left_count > k - 1:
        return self.kth_smallest(node.left, k)
    # 如果左子樹(shù)中有少于k-1個(gè)元素，則第k小元素在右子樹(shù)中，遞歸調(diào)用函數(shù)在右子樹(shù)中查找，注意要更新k的值為k-left_count-1，因?yàn)橐呀?jīng)排除了左子樹(shù)和當(dāng)前結(jié)點(diǎn)
    else:
        return self.kth_smallest(node.right, k - left_count - 1)
def lowest_common_ancestor(self, node, p, q):
    # 如果結(jié)點(diǎn)為空，則返回None
    if node is None:
        return None
    # 如果結(jié)點(diǎn)的值等于p或q中的任意一個(gè)，則返回該結(jié)點(diǎn)，表示找到了其中一個(gè)元素
    if node.value == p or node.value == q:
        return node
    # 否則在左右子樹(shù)中分別查找p和q，得到兩個(gè)結(jié)果
    left_result = self.lowest_common_ancestor(node.left, p, q)
    right_result = self.lowest_common_ancestor(node.right, p, q)
    # 如果兩個(gè)結(jié)果都不為空，則表示p和q分別在當(dāng)前結(jié)點(diǎn)的兩側(cè)，那么當(dāng)前結(jié)點(diǎn)就是最近公共祖先，返回該結(jié)點(diǎn)
    if left_result is not None and right_result is not None:
        return node
    # 如果兩個(gè)結(jié)果中有一個(gè)為空，則表示p和q都在另一個(gè)結(jié)果所在的子樹(shù)中，那么返回非空的結(jié)果作為最近公共祖先
    if left_result is None:
        return right_result
    else:
        return left_result