BST插值建树re-balance再平衡构建AVL(Adelson-Velskii & Landis)平衡二叉搜索树，基于networkx、binarytree，implement by Python

拼搏现实的明天。 2023-10-02 17:09 0阅读 0赞

### **BST插值建树re-balance再平衡构建AVL(Adelson-Velskii & Landis)平衡二叉搜索树，基于networkx、binarytree，implement by Python** ###

networkx提供了完善的节点和树的边线功能，但没有根据给定的值创建平衡AVL树的能力，借助于networkx构建BST二叉搜索树，在插入新值过程中，导致二叉树失衡，再平衡它。binarytree虽然有方便的树的节点打印管理和维护能力，但binarytree在BST失衡时候的再平衡过程中，binarytree的节点几乎不可能完成对树的再平衡形成AVL。所以基于networkx建树-平衡，然后把networkx的节点提取出来导入到binarytree再构建树，检测是否是平衡的AVL树。

import random
    
    import binarytree
    from matplotlib import pyplot as plt
    import networkx as nx
    
    """
    BST二叉搜索树插值建树re-balance再平衡构建AVL(Adelson-Velskii & Landis)平衡二叉搜索树
    """
    
    LEFT = 'left'
    RIGHT = 'right'
    
    
    def app():
        SIZE = 20  # 测试数据数量
        data = []
        for i in range(SIZE):
            data.append(i)
        random.shuffle(data)  # 随机打乱。
        print('data', data)
    
        G = nx.DiGraph()
        plt.figure(figsize=(10, 8), dpi=100)
    
        rows = 2
        cols = int(SIZE / 2) + 1
        index = 1
    
        while len(data) > 0:
            print('-----')
            d = data.pop(0)
            insert(G, d)
    
            unblance_node = check_blance(G, d)
            if unblance_node is not None:
                print('找到失衡点', unblance_node)
                print('失衡', 'nodes', G.nodes(data=True))
                if unblance_node[1] > 1:
                    if get_blance_factor(G, unblance_node[0][1][LEFT]) < 0:
                        #     x               x
                        #    / \             / \
                        #   y   D           z   D
                        #  / \        ->   / \
                        # A   z           y   C
                        #    / \         / \
                        #   B   C       A   B
                        rotate_left(G, unblance_node[0][1][LEFT])
    
                    #       x                 z
                    #      / \              /   \
                    #     z   D            y     x
                    #    / \         ->   / \   / \
                    #   y   C            A   B C   D
                    #  / \
                    # A   B
                    rotate_right(G, unblance_node[0][0])
                if unblance_node[1] < -1:
                    if get_blance_factor(G, unblance_node[0][1][RIGHT]) > 0:
                        #     y               y
                        #    / \             / \
                        #   A   x           A   z
                        #      / \    ->       / \
                        #     z   D           B   x
                        #    / \                 / \
                        #   B   C               C   D
                        rotate_right(G, unblance_node[0][1][RIGHT])
                        
                    #       y                 z
                    #      / \              /   \
                    #     A   z            y     x
                    #        / \     ->   / \   / \
                    #       B   x        A   B C   D 
                    #          / \ 
                    #         C   D
                    rotate_left(G, unblance_node[0][0])
    
            pos = nx.shell_layout(G)
            plt.subplot(rows, cols, index)
            nx.draw(G, pos, node_color='red', node_size=300, font_size=10, font_color='green', with_labels=True)
    
            index = index + 1
    
        print('---')
        print('nodes', G.nodes(data=True))
        print('edges', G.edges(data=True))
    
        print('=====')
        # 借助另外一个Python库binarytree检查通过networkx构建的二叉搜索树是否平衡。双盲检查。
        bst_tree = build_bst_tree(G)
        print(bst_tree)
        print('是平衡的AVL树吗?', bst_tree.is_bst)
    
        plt.show()
    
    
    # 把networkx构建的树的节点转换，构建成binarytree的树。
    # 基于BFS广度遍历思想。
    def build_bst_tree(G):
        root_node = get_root_node(G)
        root = binarytree.Node(root_node[0])
        Q = [root]
        while True:
            node = Q.pop()
            l = get_node_by_value(G, node.value)[1][LEFT]
            r = get_node_by_value(G, node.value)[1][RIGHT]
    
            if l is not None:
                l_node = binarytree.Node(l)
                node.left = l_node
                Q.append(l_node)
    
            if r is not None:
                r_node = binarytree.Node(r)
                node.right = r_node
                Q.append(r_node)
    
            if len(Q) == 0:
                break
    
        return root
    
    
    # 获得networkx的根节点
    def get_root_node(G):
        node = None
        for n in G.nodes(data=True):
            predecessors = G.predecessors(n[0])
            if len(list(predecessors)) == 0:
                node = n
                break
        return node
    
    
    # 右旋
    def rotate_right(G, node_value):
        print('rotate_right', node_value)
        parent = get_parent(G, node_value)
        print(node_value, '父节点', parent)
        l_child = get_node_by_value(G, node_value)[1][LEFT]
        l_child_right = get_node_by_value(G, l_child)[1][RIGHT]
    
        if parent is not None:
            G.remove_edge(parent, node_value)
            if node_value > parent:
                G.nodes[parent][RIGHT] = None
            else:
                G.nodes[parent][LEFT] = None
    
        G.remove_edge(node_value, l_child)
        G.nodes[node_value][LEFT] = None
        if l_child_right is not None:
            G.remove_edge(l_child, l_child_right)
            G.nodes[l_child][RIGHT] = None
            G.add_edge(node_value, l_child_right)
            G.nodes[node_value][LEFT] = l_child_right
    
        G.add_edge(l_child, node_value)
        G.nodes[l_child][RIGHT] = node_value
    
        if parent is not None:
            G.add_edge(parent, l_child)
            if l_child > parent:
                G.nodes[parent][RIGHT] = l_child
            else:
                G.nodes[parent][LEFT] = l_child
    
    
    # 左旋
    def rotate_left(G, node_value):
        print('rotate_left', node_value)
        parent = get_parent(G, node_value)
        print(node_value, '父节点', parent)
    
        r_child = get_node_by_value(G, node_value)[1][RIGHT]
        r_child_left = get_node_by_value(G, r_child)[1][LEFT]
    
        if parent is not None:
            G.remove_edge(parent, node_value)
            if node_value > parent:
                G.nodes[parent][RIGHT] = None
            else:
                G.nodes[parent][LEFT] = None
    
        G.remove_edge(node_value, r_child)
        G.nodes[node_value][RIGHT] = None
    
        if r_child_left is not None:
            G.remove_edge(r_child, r_child_left)
            G.nodes[r_child][LEFT] = None
            G.add_edge(node_value, r_child_left)
            G.nodes[node_value][RIGHT] = r_child_left
        G.add_edge(r_child, node_value)
        G.nodes[r_child][LEFT] = node_value
    
        if parent is not None:
            G.add_edge(parent, r_child)
            if r_child > parent:
                G.nodes[parent][RIGHT] = r_child
            else:
                G.nodes[parent][LEFT] = r_child
    
    
    # 根据一个节点的值，获得该节点的父节点
    def get_parent(G, n):
        predecessors = G.predecessors(n)
        ps = list(predecessors)
        parent = None
        if len(ps) != 0:
            parent = ps.pop()
        return parent
    
    
    # 给定一个节点的值，检测距离该节点最近的失衡的点
    # 一般来说，当在树中插上一个新值后，导致树失衡，如果树很高时候，失衡点会很多，
    # 该函数搜索出距离插入点d最近的那个失衡点（距离d最近）
    def check_blance(G, d):
        unblance_nodes = []
        for n in G.nodes(data=True):
            f = get_blance_factor(G, n[0])
            if abs(f) > 1:
                node = (n, f)
                unblance_nodes.append(node)
    
        min_len = float('inf')
        node = None
        for n in unblance_nodes:
            lenght = nx.shortest_path_length(G, source=n[0][0], target=d)
            if lenght < min_len:
                min_len = lenght
                node = n
    
        return node
    
    
    # 获得该节点的平衡因子
    def get_blance_factor(G, number):
        factor = 0
        if get_node_height(G, number) == 0:
            factor = 0
            # print(number, '平衡因子', factor)
            return factor
    
        left = G.nodes[number][LEFT]
        right = G.nodes[number][RIGHT]
    
        lh = 0
        rh = 0
        if left is not None:
            lh = get_node_height(G, left) + 1
    
        if right is not None:
            rh = get_node_height(G, right) + 1
    
        factor = lh - rh
        # print(number, '平衡因子', factor)
        return factor
    
    
    # 给定一个节点的值，获得该节点的树高度
    def get_node_height(G, number):
        height = 0
        successors = G.successors(number)
        if len(list(successors)) == 0:
            height = 0
            # print(number, '高度', height)
            return height
    
        bfs = nx.bfs_tree(G, number)
        node_v = list(bfs).pop()
        # print(number, '最远的点', node_v)
        while True:
            predecessors = G.predecessors(node_v)
            ps = list(predecessors)
            # print(node_v, '前继', ps)
            if len(ps) == 0:
                break
            else:
                p_node_v = ps.pop()
                height = height + 1
                if p_node_v == number:
                    break
                else:
                    node_v = p_node_v
    
        # print(number, '高度', height)
        return height
    
    
    # 根据一个节点的值，获取该节点的完整节点信息
    def get_node_by_value(G, v):
        node = None
        for n in G.nodes(data=True):
            if n[0] == v:
                node = n
                break
        return node
    
    
    # 输入一个值，根据这个值构建节点，并插入到树中
    def insert(G, d):
        if G.number_of_nodes() == 0:
            G.add_node(d)
            G.nodes[d][RIGHT] = None
            G.nodes[d][LEFT] = None
            return
    
        print('开始插入', d)
        root_node = get_root_node(G)
        print('根节点', root_node)
    
        while True:
            left = root_node[1][LEFT]
            right = root_node[1][RIGHT]
    
            if right is None:
                if d > root_node[0]:
                    root_node[1][RIGHT] = d
                    G.add_node(d)
                    G.nodes[d][LEFT] = None
                    G.nodes[d][RIGHT] = None
                    G.add_edge(root_node[0], d)
                    break
    
            if left is None:
                if d < root_node[0]:
                    root_node[1][LEFT] = d
                    G.add_node(d)
                    G.nodes[d][LEFT] = None
                    G.nodes[d][RIGHT] = None
                    G.add_edge(root_node[0], d)
                    break
    
            if d > root_node[0]:
                val = root_node[1][RIGHT]
                root_node = get_node_by_value(G, val)
            else:
                val = root_node[1][LEFT]
                root_node = get_node_by_value(G, val)
    
    
    if __name__ == '__main__':
        app()

运行日志输出：

data [10, 7, 16, 17, 1, 0, 6, 15, 3, 12, 18, 14, 2, 5, 19, 8, 13, 11, 9, 4]
    -----
    -----
    开始插入 7
    根节点 (10, {'right': None, 'left': None})
    -----
    开始插入 16
    根节点 (10, {'right': None, 'left': 7})
    -----
    开始插入 17
    根节点 (10, {'right': 16, 'left': 7})
    -----
    开始插入 1
    根节点 (10, {'right': 16, 'left': 7})
    -----
    开始插入 0
    根节点 (10, {'right': 16, 'left': 7})
    找到失衡点 ((7, {'left': 1, 'right': None}), 2)
    失衡 nodes [(10, {'right': 16, 'left': 7}), (7, {'left': 1, 'right': None}), (16, {'left': None, 'right': 17}), (17, {'left': None, 'right': None}), (1, {'left': 0, 'right': None}), (0, {'left': None, 'right': None})]
    rotate_right 7
    7 父节点 10
    -----
    开始插入 6
    根节点 (10, {'right': 16, 'left': 1})
    -----
    开始插入 15
    根节点 (10, {'right': 16, 'left': 1})
    -----
    开始插入 3
    根节点 (10, {'right': 16, 'left': 1})
    找到失衡点 ((7, {'left': 6, 'right': None}), 2)
    失衡 nodes [(10, {'right': 16, 'left': 1}), (7, {'left': 6, 'right': None}), (16, {'left': 15, 'right': 17}), (17, {'left': None, 'right': None}), (1, {'left': 0, 'right': 7}), (0, {'left': None, 'right': None}), (6, {'left': 3, 'right': None}), (15, {'left': None, 'right': None}), (3, {'left': None, 'right': None})]
    rotate_right 7
    7 父节点 1
    -----
    开始插入 12
    根节点 (10, {'right': 16, 'left': 1})
    -----
    开始插入 18
    根节点 (10, {'right': 16, 'left': 1})
    -----
    开始插入 14
    根节点 (10, {'right': 16, 'left': 1})
    找到失衡点 ((15, {'left': 12, 'right': None}), 2)
    失衡 nodes [(10, {'right': 16, 'left': 1}), (7, {'left': None, 'right': None}), (16, {'left': 15, 'right': 17}), (17, {'left': None, 'right': 18}), (1, {'left': 0, 'right': 6}), (0, {'left': None, 'right': None}), (6, {'left': 3, 'right': 7}), (15, {'left': 12, 'right': None}), (3, {'left': None, 'right': None}), (12, {'left': None, 'right': 14}), (18, {'left': None, 'right': None}), (14, {'left': None, 'right': None})]
    rotate_left 12
    12 父节点 15
    rotate_right 15
    15 父节点 16
    -----
    开始插入 2
    根节点 (10, {'right': 16, 'left': 1})
    找到失衡点 ((1, {'left': 0, 'right': 6}), -2)
    失衡 nodes [(10, {'right': 16, 'left': 1}), (7, {'left': None, 'right': None}), (16, {'left': 14, 'right': 17}), (17, {'left': None, 'right': 18}), (1, {'left': 0, 'right': 6}), (0, {'left': None, 'right': None}), (6, {'left': 3, 'right': 7}), (15, {'left': None, 'right': None}), (3, {'left': 2, 'right': None}), (12, {'left': None, 'right': None}), (18, {'left': None, 'right': None}), (14, {'left': 12, 'right': 15}), (2, {'left': None, 'right': None})]
    rotate_right 6
    6 父节点 1
    rotate_left 1
    1 父节点 10
    -----
    开始插入 5
    根节点 (10, {'right': 16, 'left': 3})
    -----
    开始插入 19
    根节点 (10, {'right': 16, 'left': 3})
    找到失衡点 ((17, {'left': None, 'right': 18}), -2)
    失衡 nodes [(10, {'right': 16, 'left': 3}), (7, {'left': None, 'right': None}), (16, {'left': 14, 'right': 17}), (17, {'left': None, 'right': 18}), (1, {'left': 0, 'right': 2}), (0, {'left': None, 'right': None}), (6, {'left': 5, 'right': 7}), (15, {'left': None, 'right': None}), (3, {'left': 1, 'right': 6}), (12, {'left': None, 'right': None}), (18, {'left': None, 'right': 19}), (14, {'left': 12, 'right': 15}), (2, {'left': None, 'right': None}), (5, {'left': None, 'right': None}), (19, {'left': None, 'right': None})]
    rotate_left 17
    17 父节点 16
    -----
    开始插入 8
    根节点 (10, {'right': 16, 'left': 3})
    -----
    开始插入 13
    根节点 (10, {'right': 16, 'left': 3})
    -----
    开始插入 11
    根节点 (10, {'right': 16, 'left': 3})
    -----
    开始插入 9
    根节点 (10, {'right': 16, 'left': 3})
    找到失衡点 ((7, {'left': None, 'right': 8}), -2)
    失衡 nodes [(10, {'right': 16, 'left': 3}), (7, {'left': None, 'right': 8}), (16, {'left': 14, 'right': 18}), (17, {'left': None, 'right': None}), (1, {'left': 0, 'right': 2}), (0, {'left': None, 'right': None}), (6, {'left': 5, 'right': 7}), (15, {'left': None, 'right': None}), (3, {'left': 1, 'right': 6}), (12, {'left': 11, 'right': 13}), (18, {'left': 17, 'right': 19}), (14, {'left': 12, 'right': 15}), (2, {'left': None, 'right': None}), (5, {'left': None, 'right': None}), (19, {'left': None, 'right': None}), (8, {'left': None, 'right': 9}), (13, {'left': None, 'right': None}), (11, {'left': None, 'right': None}), (9, {'left': None, 'right': None})]
    rotate_left 7
    7 父节点 6
    -----
    开始插入 4
    根节点 (10, {'right': 16, 'left': 3})
    ---
    nodes [(10, {'right': 16, 'left': 3}), (7, {'left': None, 'right': None}), (16, {'left': 14, 'right': 18}), (17, {'left': None, 'right': None}), (1, {'left': 0, 'right': 2}), (0, {'left': None, 'right': None}), (6, {'left': 5, 'right': 8}), (15, {'left': None, 'right': None}), (3, {'left': 1, 'right': 6}), (12, {'left': 11, 'right': 13}), (18, {'left': 17, 'right': 19}), (14, {'left': 12, 'right': 15}), (2, {'left': None, 'right': None}), (5, {'left': 4, 'right': None}), (19, {'left': None, 'right': None}), (8, {'left': 7, 'right': 9}), (13, {'left': None, 'right': None}), (11, {'left': None, 'right': None}), (9, {'left': None, 'right': None}), (4, {'left': None, 'right': None})]
    edges [(10, 16, {}), (10, 3, {}), (16, 14, {}), (16, 18, {}), (1, 0, {}), (1, 2, {}), (6, 5, {}), (6, 8, {}), (3, 6, {}), (3, 1, {}), (12, 13, {}), (12, 11, {}), (18, 19, {}), (18, 17, {}), (14, 12, {}), (14, 15, {}), (5, 4, {}), (8, 9, {}), (8, 7, {})]
    =====
    
            ____________10_______________
           /                             \
        __3____                       ____16___
       /       \                     /         \
      1         6__             ____14         _18
     / \       /   \           /      \       /   \
    0   2     5     8        _12       15    17    19
             /     / \      /   \
            4     7   9    11    13
    
    是平衡的AVL树吗? True

再跑一轮测试：

data [18, 14, 10, 5, 15, 9, 19, 1, 2, 11, 17, 16, 8, 6, 4, 0, 12, 7, 13, 3]
    -----
    -----
    开始插入 14
    根节点 (18, {'right': None, 'left': None})
    -----
    开始插入 10
    根节点 (18, {'right': None, 'left': 14})
    找到失衡点 ((18, {'right': None, 'left': 14}), 2)
    失衡 nodes [(18, {'right': None, 'left': 14}), (14, {'left': 10, 'right': None}), (10, {'left': None, 'right': None})]
    rotate_right 18
    18 父节点 None
    -----
    开始插入 5
    根节点 (14, {'left': 10, 'right': 18})
    -----
    开始插入 15
    根节点 (14, {'left': 10, 'right': 18})
    -----
    开始插入 9
    根节点 (14, {'left': 10, 'right': 18})
    找到失衡点 ((10, {'left': 5, 'right': None}), 2)
    失衡 nodes [(18, {'right': None, 'left': 15}), (14, {'left': 10, 'right': 18}), (10, {'left': 5, 'right': None}), (5, {'left': None, 'right': 9}), (15, {'left': None, 'right': None}), (9, {'left': None, 'right': None})]
    rotate_left 5
    5 父节点 10
    rotate_right 10
    10 父节点 14
    -----
    开始插入 19
    根节点 (14, {'left': 9, 'right': 18})
    -----
    开始插入 1
    根节点 (14, {'left': 9, 'right': 18})
    -----
    开始插入 2
    根节点 (14, {'left': 9, 'right': 18})
    找到失衡点 ((5, {'left': 1, 'right': None}), 2)
    失衡 nodes [(18, {'right': 19, 'left': 15}), (14, {'left': 9, 'right': 18}), (10, {'left': None, 'right': None}), (5, {'left': 1, 'right': None}), (15, {'left': None, 'right': None}), (9, {'left': 5, 'right': 10}), (19, {'left': None, 'right': None}), (1, {'left': None, 'right': 2}), (2, {'left': None, 'right': None})]
    rotate_left 1
    1 父节点 5
    rotate_right 5
    5 父节点 9
    -----
    开始插入 11
    根节点 (14, {'left': 9, 'right': 18})
    -----
    开始插入 17
    根节点 (14, {'left': 9, 'right': 18})
    -----
    开始插入 16
    根节点 (14, {'left': 9, 'right': 18})
    找到失衡点 ((15, {'left': None, 'right': 17}), -2)
    失衡 nodes [(18, {'right': 19, 'left': 15}), (14, {'left': 9, 'right': 18}), (10, {'left': None, 'right': 11}), (5, {'left': None, 'right': None}), (15, {'left': None, 'right': 17}), (9, {'left': 2, 'right': 10}), (19, {'left': None, 'right': None}), (1, {'left': None, 'right': None}), (2, {'left': 1, 'right': 5}), (11, {'left': None, 'right': None}), (17, {'left': 16, 'right': None}), (16, {'left': None, 'right': None})]
    rotate_right 17
    17 父节点 15
    rotate_left 15
    15 父节点 18
    -----
    开始插入 8
    根节点 (14, {'left': 9, 'right': 18})
    -----
    开始插入 6
    根节点 (14, {'left': 9, 'right': 18})
    找到失衡点 ((5, {'left': None, 'right': 8}), -2)
    失衡 nodes [(18, {'right': 19, 'left': 16}), (14, {'left': 9, 'right': 18}), (10, {'left': None, 'right': 11}), (5, {'left': None, 'right': 8}), (15, {'left': None, 'right': None}), (9, {'left': 2, 'right': 10}), (19, {'left': None, 'right': None}), (1, {'left': None, 'right': None}), (2, {'left': 1, 'right': 5}), (11, {'left': None, 'right': None}), (17, {'left': None, 'right': None}), (16, {'left': 15, 'right': 17}), (8, {'left': 6, 'right': None}), (6, {'left': None, 'right': None})]
    rotate_right 8
    8 父节点 5
    rotate_left 5
    5 父节点 2
    -----
    开始插入 4
    根节点 (14, {'left': 9, 'right': 18})
    找到失衡点 ((2, {'left': 1, 'right': 6}), -2)
    失衡 nodes [(18, {'right': 19, 'left': 16}), (14, {'left': 9, 'right': 18}), (10, {'left': None, 'right': 11}), (5, {'left': 4, 'right': None}), (15, {'left': None, 'right': None}), (9, {'left': 2, 'right': 10}), (19, {'left': None, 'right': None}), (1, {'left': None, 'right': None}), (2, {'left': 1, 'right': 6}), (11, {'left': None, 'right': None}), (17, {'left': None, 'right': None}), (16, {'left': 15, 'right': 17}), (8, {'left': None, 'right': None}), (6, {'left': 5, 'right': 8}), (4, {'left': None, 'right': None})]
    rotate_right 6
    6 父节点 2
    rotate_left 2
    2 父节点 9
    -----
    开始插入 0
    根节点 (14, {'left': 9, 'right': 18})
    找到失衡点 ((9, {'left': 5, 'right': 10}), 2)
    失衡 nodes [(18, {'right': 19, 'left': 16}), (14, {'left': 9, 'right': 18}), (10, {'left': None, 'right': 11}), (5, {'left': 2, 'right': 6}), (15, {'left': None, 'right': None}), (9, {'left': 5, 'right': 10}), (19, {'left': None, 'right': None}), (1, {'left': 0, 'right': None}), (2, {'left': 1, 'right': 4}), (11, {'left': None, 'right': None}), (17, {'left': None, 'right': None}), (16, {'left': 15, 'right': 17}), (8, {'left': None, 'right': None}), (6, {'left': None, 'right': 8}), (4, {'left': None, 'right': None}), (0, {'left': None, 'right': None})]
    rotate_right 9
    9 父节点 14
    -----
    开始插入 12
    根节点 (14, {'left': 5, 'right': 18})
    找到失衡点 ((10, {'left': None, 'right': 11}), -2)
    失衡 nodes [(18, {'right': 19, 'left': 16}), (14, {'left': 5, 'right': 18}), (10, {'left': None, 'right': 11}), (5, {'left': 2, 'right': 9}), (15, {'left': None, 'right': None}), (9, {'left': 6, 'right': 10}), (19, {'left': None, 'right': None}), (1, {'left': 0, 'right': None}), (2, {'left': 1, 'right': 4}), (11, {'left': None, 'right': 12}), (17, {'left': None, 'right': None}), (16, {'left': 15, 'right': 17}), (8, {'left': None, 'right': None}), (6, {'left': None, 'right': 8}), (4, {'left': None, 'right': None}), (0, {'left': None, 'right': None}), (12, {'left': None, 'right': None})]
    rotate_left 10
    10 父节点 9
    -----
    开始插入 7
    根节点 (14, {'left': 5, 'right': 18})
    找到失衡点 ((6, {'left': None, 'right': 8}), -2)
    失衡 nodes [(18, {'right': 19, 'left': 16}), (14, {'left': 5, 'right': 18}), (10, {'left': None, 'right': None}), (5, {'left': 2, 'right': 9}), (15, {'left': None, 'right': None}), (9, {'left': 6, 'right': 11}), (19, {'left': None, 'right': None}), (1, {'left': 0, 'right': None}), (2, {'left': 1, 'right': 4}), (11, {'left': 10, 'right': 12}), (17, {'left': None, 'right': None}), (16, {'left': 15, 'right': 17}), (8, {'left': 7, 'right': None}), (6, {'left': None, 'right': 8}), (4, {'left': None, 'right': None}), (0, {'left': None, 'right': None}), (12, {'left': None, 'right': None}), (7, {'left': None, 'right': None})]
    rotate_right 8
    8 父节点 6
    rotate_left 6
    6 父节点 9
    -----
    开始插入 13
    根节点 (14, {'left': 5, 'right': 18})
    找到失衡点 ((14, {'left': 5, 'right': 18}), 2)
    失衡 nodes [(18, {'right': 19, 'left': 16}), (14, {'left': 5, 'right': 18}), (10, {'left': None, 'right': None}), (5, {'left': 2, 'right': 9}), (15, {'left': None, 'right': None}), (9, {'left': 7, 'right': 11}), (19, {'left': None, 'right': None}), (1, {'left': 0, 'right': None}), (2, {'left': 1, 'right': 4}), (11, {'left': 10, 'right': 12}), (17, {'left': None, 'right': None}), (16, {'left': 15, 'right': 17}), (8, {'left': None, 'right': None}), (6, {'left': None, 'right': None}), (4, {'left': None, 'right': None}), (0, {'left': None, 'right': None}), (12, {'left': None, 'right': 13}), (7, {'left': 6, 'right': 8}), (13, {'left': None, 'right': None})]
    rotate_left 5
    5 父节点 14
    rotate_right 14
    14 父节点 None
    -----
    开始插入 3
    根节点 (9, {'left': 5, 'right': 14})
    ---
    nodes [(18, {'right': 19, 'left': 16}), (14, {'left': 11, 'right': 18}), (10, {'left': None, 'right': None}), (5, {'left': 2, 'right': 7}), (15, {'left': None, 'right': None}), (9, {'left': 5, 'right': 14}), (19, {'left': None, 'right': None}), (1, {'left': 0, 'right': None}), (2, {'left': 1, 'right': 4}), (11, {'left': 10, 'right': 12}), (17, {'left': None, 'right': None}), (16, {'left': 15, 'right': 17}), (8, {'left': None, 'right': None}), (6, {'left': None, 'right': None}), (4, {'left': 3, 'right': None}), (0, {'left': None, 'right': None}), (12, {'left': None, 'right': 13}), (7, {'left': 6, 'right': 8}), (13, {'left': None, 'right': None}), (3, {'left': None, 'right': None})]
    edges [(18, 19, {}), (18, 16, {}), (14, 18, {}), (14, 11, {}), (5, 2, {}), (5, 7, {}), (9, 5, {}), (9, 14, {}), (1, 0, {}), (2, 1, {}), (2, 4, {}), (11, 12, {}), (11, 10, {}), (16, 17, {}), (16, 15, {}), (4, 3, {}), (12, 13, {}), (7, 8, {}), (7, 6, {})]
    =====
    
                ______9____________
               /                   \
          ____5__            _______14_________
         /       \          /                  \
        2__       7       _11               ____18
       /   \     / \     /   \             /      \
      1     4   6   8   10    12         _16       19
     /     /                    \       /   \
    0     3                      13    15    17
    
    是平衡的AVL树吗? True