BST二叉搜索树插入一个节点后检测距离当前节点最近的失衡点，binarytree，Python

迷南。 2023-10-02 16:22 6阅读 0赞

思路：二叉搜索树之所以不平衡，发生在插入新节点后，那么沿着新插入节点，逆向沿着当前节点的父节点，一路检测节点平衡因子，当发现绝对值>1的平衡因子，即为最近的失衡点。

def check_unblance(root, number):
        ret = None
    
        un_blance_node = None
        for n in root.levelorder:
            if n.value == number:
                un_blance_node = n
                break
    
        h = 0
        while h <= root.height:
            h = h + 1
    
            factor = get_blance_factor(un_blance_node)
            print('节点', un_blance_node.value, '平衡因子', factor)
            if abs(factor) > 1:
                print('检测到不平衡', un_blance_node.value, factor)
                ret = (un_blance_node, factor)
                break
            else:
                un_blance_node = get_parent(root, un_blance_node)
    
        return ret
    
    
    def get_blance_factor(node):
        factor = 0
    
        if node.height == 0:
            factor = 0
            return factor
    
        left = node.left
        right = node.right
    
        lh = 0
        rh = 0
        if left is not None:
            lh = node.left.height + 1
    
        if right is not None:
            rh = node.right.height + 1
    
        factor = lh - rh
    
        return factor

最后返回(失衡节点，平衡因子)。