'''
二叉排序樹(shù)的結(jié)點(diǎn)類
'''
class TreeNode():
    def __init__(self, value):
        # 結(jié)點(diǎn)上的值
        self.value = value
        # 左結(jié)點(diǎn)
        self.l_child = None
        # 右結(jié)點(diǎn)
        self.r_child = None

'''
二叉排序樹(shù)類
'''
class BinarySortTree:
    # 初始化樹(shù)
    def __init__(self, value=None):
        pass
    
    '''
    在整棵樹(shù)上查詢是否存在給定的關(guān)鍵字
    '''
    def find(self, key):
        pass
    
    '''
    使用遞歸進(jìn)行查詢
    '''
    def find_dg(self, root, key):
        pass

    '''
    插入新結(jié)點(diǎn)
    '''
    def insert(self, value):
        pass

     '''
    中序遍歷
    '''
    def inorder_traversal(self):
        pass
    '''
    刪除結(jié)點(diǎn)
    '''
    def delete(self, key):
        pass

    '''
    檢查是不是空樹(shù)
    '''
    def is_empty(self):
        return self.root == None

    # 初始化樹(shù)
    def __init__(self, value=None):
        self.root = None
        if value is not None:
            root_node = TreeNode(value)
            self.root = root_node

    '''
    在整棵樹(shù)上查詢是否存在給定的關(guān)鍵字
    key: 給定的關(guān)鍵字
    '''
    def find(self, key):
        # 從根結(jié)點(diǎn)開(kāi)始查找。
        move_node = self.root
        # 用來(lái)保存最后訪問(wèn)過(guò)的結(jié)點(diǎn)
        last_node = None
        while move_node is not None:
            # 保存當(dāng)前結(jié)點(diǎn)
            last_node = move_node
            # 把關(guān)鍵字和當(dāng)前結(jié)點(diǎn)相比較
            if self.root.value == key:
                # 出口一：成功查找
                return move_node
            elif move_node.value > key:
                # 在左結(jié)點(diǎn)查找
                move_node = move_node.l_child
            else:
                # 在右結(jié)點(diǎn)中查找
                move_node = move_node.r_child
        # 出口二：如果沒(méi)有查詢到，則返回最后訪問(wèn)過(guò)的結(jié)點(diǎn)及None（None 表示沒(méi)查詢到）
        return last_node, None

    '''
    使用遞歸進(jìn)行查詢
    '''
    def find_dg(self, root, key):
        # 結(jié)點(diǎn)不存在
        if root is None:
            return None
        # 相等
        if root.value == key:
            return root
        if root.value > key:
            return self.find_dg(root.l_child, key)
        else:
            return self.find_dg(root.r_child, key)

    '''
    插入新結(jié)點(diǎn)
    '''
    def insert(self, value):
        # 查詢是否存在此結(jié)點(diǎn)
        res = self.find(value)
        if type(res) != TreeNode:
            # 沒(méi)找到，獲取查詢時(shí)最后訪問(wèn)過(guò)的結(jié)點(diǎn)
            last_node = res[0]
            # 創(chuàng)建新結(jié)點(diǎn)
            new_node = TreeNode(value)
            # 最后訪問(wèn)的結(jié)點(diǎn)是根結(jié)點(diǎn)
            if last_node is None:
                self.root = new_node
            if value > last_node.value:
                last_node.r_child = new_node
            else:
                last_node.l_child = new_node

if __name__ == "__main__":
    nums = [5, 12, 4, 45, 32, 8, 10, 50, 32, 3]
    tree = BinarySortTree(5)
    for i in range(1, len(nums)):
        tree.insert(nums[i])
    print("測(cè)試根5 -> 左4 ->左3:")
    tmp_node = tree.root
    while tmp_node != None:
        print(tmp_node.value, end=" ->")
        tmp_node = tmp_node.l_child
    print("\n測(cè)試根5 -> 右12 ->右45->右50：")
    tmp_node = tree.root
    while tmp_node != None:
        print(tmp_node.value, end=" ->")
        tmp_node = tmp_node.r_child
    '''
    輸出結(jié)果：
    測(cè)試根5 -> 左4 ->左3:
	5 ->4 ->3 ->
	測(cè)試根5 -> 右12 ->右45->右50：
	5 ->12 ->45 ->50 ->	
    ''' 

    '''
    中序遍歷
    '''
    def inorder_traversal(self, root):
        if root is None:
            return
        self.inorder_traversal(root.l_child)
        print(root.value,end="->")
        self.inorder_traversal(root.r_child)

if __name__ == "__main__":
    nums = [5, 12, 4, 45, 32, 8, 10, 50, 32, 3]
    tree = BinarySortTree(5)
    # res = tree.find(51)
    for i in range(1, len(nums)):
        tree.insert(nums[i])
    tree.inorder_traversal(tree.root)
   '''
   輸出結(jié)果
   3->4->5->8->10->12->32->45->50->
   '''

 	'''
    刪除結(jié)點(diǎn)
    key 為要要?jiǎng)h除的結(jié)點(diǎn)
    '''
    def delete(self, key):
        # 從根結(jié)點(diǎn)開(kāi)始查找，move_node 為搜索指針
        move_node = self.root
        # 要?jiǎng)h除的結(jié)點(diǎn)的父結(jié)點(diǎn),因?yàn)楦Y(jié)點(diǎn)沒(méi)有父結(jié)點(diǎn)，初始值為 None
        parent_node = None
        # 結(jié)點(diǎn)存在且沒(méi)有匹配上要找的關(guān)鍵字
        while move_node is not None and move_node.value != key:
            # 保證當(dāng)前結(jié)點(diǎn)
            parent_node = move_node
            if move_node.value > key:
                # 在左子樹(shù)中繼續(xù)查找
                move_node = move_node.l_child
            else:
                # 在右子樹(shù)中繼續(xù)查找
                move_node = move_node.r_child
        # 如果不存在
        if move_node is None:
            return -1
        # 檢查要?jiǎng)h除的結(jié)點(diǎn)是否存在左子結(jié)點(diǎn)
        if move_node.l_child is None:
            if parent_node is None:
                # 如果要?jiǎng)h除的結(jié)點(diǎn)是根結(jié)點(diǎn)
                self.root = move_node.r_child
            elif parent_node.l_child == move_node:
                # 刪除結(jié)點(diǎn)的右結(jié)點(diǎn)作為父結(jié)點(diǎn)的左結(jié)點(diǎn)
                parent_node.l_child = move_node.r_child
            elif parent_node.r_child == move_node:
                parent_node.r_child = move_node.r_child
            return 1
        else:
            # 如果刪除的結(jié)點(diǎn)存在左子結(jié)點(diǎn),則在左子樹(shù)中查找最大值
            s = move_node.l_child
            q = move_node
            while s.r_child is not None:
                q = s
                s = s.r_child
            if q == move_node:
                move_node.l_child = s.l_child
            else:
                q.r_child = s.l_child
            move_node.value = s.value
            q.r_child = None
            return 1

if __name__ == "__main__":
    nums = [5, 12, 4, 45, 32, 8, 10, 50, 32, 3]
    tree = BinarySortTree(5)
    # res = tree.find(51)
    for i in range(1, len(nums)):
        tree.insert(nums[i])
    tree.delete(12)
    tree.inorder_traversal(tree.root)
    '''
    輸出結(jié)果
    3->4->5->8->10->32->45->50->
    '''

'''
結(jié)點(diǎn)類
'''
class TreeNode:
    def __init__(self,value):
        self.value=value
        self.l_child=None
        self.r_child=None
        self.balance=0

'''
樹(shù)類
'''
class Tree:
    def __init__(self, value):
        self.root = None

    '''
    LL型調(diào)整
    '''
    def ll_rotate(self, node):
        pass

    '''
    RR 型調(diào)整
    '''
    def rr_rotate(self, node):
        pass

    '''
    LR型調(diào)整
    '''
    def lr_rotate(self, node):
        pass

    '''
    RL型調(diào)整
    '''
    def rl_rotate(self, node):
        pass

    '''
    插入新結(jié)點(diǎn)
    '''
    def insert(self, value):
        pass
    
    '''
    中序遍歷
    '''
    def inorder_traversal(self, root):
        pass

    def is_empty(self):
        pass

    '''
    LL型調(diào)整
    順時(shí)針對(duì)調(diào)整
    '''
    def ll_rotate(self, p_root):
        # 原父結(jié)點(diǎn)的左子結(jié)點(diǎn)成為新父結(jié)點(diǎn)
        new_p_root = p_root.l_child
        # 新父結(jié)點(diǎn)的右子結(jié)點(diǎn)成為原父結(jié)點(diǎn)的左子結(jié)點(diǎn)
        p_root.l_child = new_p_root.r_child
        # 原父結(jié)點(diǎn)成為新父結(jié)點(diǎn)的右子結(jié)點(diǎn)
        new_p_root.r_child = p_root
        # 重置平衡因子
        p_root.balance = 0
        new_p_root.balance = 0
        return new_p_root

    '''
    RR 型調(diào)整
    '''
    def rr_rotate(self, node):
        # 右子結(jié)點(diǎn)
        new_p_node = p_node.r_child
        p_node.r_child = new_p_node.l_child
        new_p_node.l_child = p_node
        # 重置平衡因子
        p_node.balance = 0
        new_p_node.balance = 0
        return new_p_node

    '''
    LR型調(diào)整
    '''
    def lr_rotate(self, p_node):
        # 左子結(jié)點(diǎn)
        b = p_node.l_child
        new_p_node = b.r_child
        p_node.l_child = new_p_node.r_child
        b.r_child = new_p_node.l_child
        new_p_node.l_child = b
        new_p_node.r_child = p_node
        if new_p_node.balance == 1:
            p_node.balance = -1
            b.balance = 0
        elif new_p_node.balance == -1:
            p_node.balance = 0
            b.balance = 1
        else:
            p_node.balance = 0
            b.balance = 0
        new_p_node.balance = 0
        return new_p_node

    '''
    RL型調(diào)整
    '''
    def rl_rotate(self, p_node):
        b = p_node.r_child
        new_p_node = b.l_child
        p_node.r_child = new_p_node.l_child
        b.l_child = new_p_node.r_child
        new_p_node.l_child = p_node
        new_p_node.r_child = b
        if new_p_node.balance == 1:
            p_node.balance = 0
            b.balance = -1
        elif new_p_node.balance == -1:
            p_node.balance = 1
            b.balance = 0
        else:
            p_node.balance = 0
            b.balance = 0
        new_p_node.balance = 0
        return new_p_node

    '''
    插入新結(jié)點(diǎn)
    '''
    def insert(self, val):
        # 新的結(jié)點(diǎn)
        new_node = TreeNode(val)
        if self.root is None:
            # 空樹(shù)
            self.root = new_node
            return
        # 記錄離 s 最近的平衡因子不為 0 的結(jié)點(diǎn)。
        min_b = self.root
        # f 指向 a 的父結(jié)點(diǎn)
        f_node = None
        move_node = self.root
        f_move_node = None
        while move_node is not None:
            if move_node.value == new_node.value:
                # 結(jié)點(diǎn)已經(jīng)存在
                return
            if move_node.balance != 0:
                # 尋找最小不平衡子樹(shù)
                min_b = move_node
                f_node = f_move_node
            f_move_node = move_node
            if new_node.value < move_node.value:
                move_node = move_node.l_child
            else:
                move_node = move_node.r_child

        if new_node.value < f_move_node.value:
            f_move_node.l_child = new_node
        else:
            f_move_node.r_child = new_node
        move_node = min_b
        # 修改相關(guān)結(jié)點(diǎn)的平衡因子
        while move_node != new_node:
            if new_node.value < move_node.value:
                move_node.balance += 1
                move_node = move_node.l_child
            else:
                move_node.balance -= 1
                move_node = move_node.r_child

        if min_b.balance > -2 and min_b.balance < 2:
            # 插入結(jié)點(diǎn)后沒(méi)有破壞平衡性
            return

        if min_b.balance == 2:
            b = min_b.l_child
            if b.balance == 1:
                move_node = self.ll_rotate(min_b)
            else:
                move_node = self.lr_rotate(min_b)
        else:
            b = min_b.r_child
            if b.balance == 1:
                move_node = self.rl_rotate(min_b)
            else:
                move_node = self.rr_rotate(min_b)
        if f_node is None:
            self.root = move_node
        elif f_node.l_child == min_b:
            f_node.l_child = move_node
        else:
            f_node.r_child = move_node

    '''
    中序遍歷
    '''
    def inorder_traversal(self, root):
        if root is None:
            return
        self.inorder_traversal(root.l_child)
        print(root.value, end="->")
        self.inorder_traversal(root.r_child)

if __name__ == "__main__":
    nums = [3, 12, 8, 10, 9, 1, 7]
    tree = Tree(3)
    for i in range(1, len(nums)):
        tree.inster(nums[i])
    # 中序遍歷    
    tree.inorder_traversal(tree.root)
    '''
    輸出結(jié)果
    1->3->7->8->9->10->12->
    '''