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

转x33g5p2x  于2021-12-30 转载在 Python  
字(16.6k)|赞(0)|评价(0)|浏览(242)

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树。

  1. import random
  3. import binarytree
  4. from matplotlib import pyplot as plt
  5. import networkx as nx
  7. """
  8. BST二叉搜索树插值建树re-balance再平衡构建AVL(Adelson-Velskii & Landis)平衡二叉搜索树
  9. """
  11. LEFT = 'left'
  12. RIGHT = 'right'
  14. def app():
  15.     SIZE = 20  # 测试数据数量
  16.     data = []
  17.     for i in range(SIZE):
  18.         data.append(i)
  19.     random.shuffle(data)  # 随机打乱。
  20.     print('data', data)
  22.     G = nx.DiGraph()
  23.     plt.figure(figsize=(10, 8), dpi=100)
  25.     rows = 2
  26.     cols = int(SIZE / 2) + 1
  27.     index = 1
  29.     while len(data) > 0:
  30.         print('-----')
  31.         d = data.pop(0)
  32.         insert(G, d)
  34.         unblance_node = check_blance(G, d)
  35.         if unblance_node is not None:
  36.             print('找到失衡点', unblance_node)
  37.             print('失衡', 'nodes', G.nodes(data=True))
  38.             if unblance_node[1] > 1:
  39.                 if get_blance_factor(G, unblance_node[0][1][LEFT]) < 0:
  40.                     #     x               x
  41.                     #    / \             / \
  42.                     #   y   D           z   D
  43.                     #  / \        ->   / \
  44.                     # A   z           y   C
  45.                     #    / \         / \
  46.                     #   B   C       A   B
  47.                     rotate_left(G, unblance_node[0][1][LEFT])
  49.                 #       x                 z
  50.                 #      / \              /   \
  51.                 #     z   D            y     x
  52.                 #    / \         ->   / \   / \
  53.                 #   y   C            A   B C   D
  54.                 #  / \
  55.                 # A   B
  56.                 rotate_right(G, unblance_node[0][0])
  57.             if unblance_node[1] < -1:
  58.                 if get_blance_factor(G, unblance_node[0][1][RIGHT]) > 0:
  59.                     #     y               y
  60.                     #    / \             / \
  61.                     #   A   x           A   z
  62.                     #      / \    ->       / \
  63.                     #     z   D           B   x
  64.                     #    / \                 / \
  65.                     #   B   C               C   D
  66.                     rotate_right(G, unblance_node[0][1][RIGHT])
  67.                     
  68.                 #       y                 z
  69.                 #      / \              /   \
  70.                 #     A   z            y     x
  71.                 #        / \     ->   / \   / \
  72.                 #       B   x        A   B C   D 
  73.                 #          / \ 
  74.                 #         C   D
  75.                 rotate_left(G, unblance_node[0][0])
  77.         pos = nx.shell_layout(G)
  78.         plt.subplot(rows, cols, index)
  79.         nx.draw(G, pos, node_color='red', node_size=300, font_size=10, font_color='green', with_labels=True)
  81.         index = index + 1
  83.     print('---')
  84.     print('nodes', G.nodes(data=True))
  85.     print('edges', G.edges(data=True))
  87.     print('=====')
  88.     # 借助另外一个Python库binarytree检查通过networkx构建的二叉搜索树是否平衡。双盲检查。
  89.     bst_tree = build_bst_tree(G)
  90.     print(bst_tree)
  91.     print('是平衡的AVL树吗?', bst_tree.is_bst)
  93.     plt.show()
  95. # 把networkx构建的树的节点转换，构建成binarytree的树。
  96. # 基于BFS广度遍历思想。
  97. def build_bst_tree(G):
  98.     root_node = get_root_node(G)
  99.     root = binarytree.Node(root_node[0])
  100.     Q = [root]
  101.     while True:
  102.         node = Q.pop()
  103.         l = get_node_by_value(G, node.value)[1][LEFT]
  104.         r = get_node_by_value(G, node.value)[1][RIGHT]
  106.         if l is not None:
  107.             l_node = binarytree.Node(l)
  108.             node.left = l_node
  109.             Q.append(l_node)
  111.         if r is not None:
  112.             r_node = binarytree.Node(r)
  113.             node.right = r_node
  114.             Q.append(r_node)
  116.         if len(Q) == 0:
  117.             break
  119.     return root
  121. # 获得networkx的根节点
  122. def get_root_node(G):
  123.     node = None
  124.     for n in G.nodes(data=True):
  125.         predecessors = G.predecessors(n[0])
  126.         if len(list(predecessors)) == 0:
  127.             node = n
  128.             break
  129.     return node
  131. # 右旋
  132. def rotate_right(G, node_value):
  133.     print('rotate_right', node_value)
  134.     parent = get_parent(G, node_value)
  135.     print(node_value, '父节点', parent)
  136.     l_child = get_node_by_value(G, node_value)[1][LEFT]
  137.     l_child_right = get_node_by_value(G, l_child)[1][RIGHT]
  139.     if parent is not None:
  140.         G.remove_edge(parent, node_value)
  141.         if node_value > parent:
  142.             G.nodes[parent][RIGHT] = None
  143.         else:
  144.             G.nodes[parent][LEFT] = None
  146.     G.remove_edge(node_value, l_child)
  147.     G.nodes[node_value][LEFT] = None
  148.     if l_child_right is not None:
  149.         G.remove_edge(l_child, l_child_right)
  150.         G.nodes[l_child][RIGHT] = None
  151.         G.add_edge(node_value, l_child_right)
  152.         G.nodes[node_value][LEFT] = l_child_right
  154.     G.add_edge(l_child, node_value)
  155.     G.nodes[l_child][RIGHT] = node_value
  157.     if parent is not None:
  158.         G.add_edge(parent, l_child)
  159.         if l_child > parent:
  160.             G.nodes[parent][RIGHT] = l_child
  161.         else:
  162.             G.nodes[parent][LEFT] = l_child
  164. # 左旋
  165. def rotate_left(G, node_value):
  166.     print('rotate_left', node_value)
  167.     parent = get_parent(G, node_value)
  168.     print(node_value, '父节点', parent)
  170.     r_child = get_node_by_value(G, node_value)[1][RIGHT]
  171.     r_child_left = get_node_by_value(G, r_child)[1][LEFT]
  173.     if parent is not None:
  174.         G.remove_edge(parent, node_value)
  175.         if node_value > parent:
  176.             G.nodes[parent][RIGHT] = None
  177.         else:
  178.             G.nodes[parent][LEFT] = None
  180.     G.remove_edge(node_value, r_child)
  181.     G.nodes[node_value][RIGHT] = None
  183.     if r_child_left is not None:
  184.         G.remove_edge(r_child, r_child_left)
  185.         G.nodes[r_child][LEFT] = None
  186.         G.add_edge(node_value, r_child_left)
  187.         G.nodes[node_value][RIGHT] = r_child_left
  188.     G.add_edge(r_child, node_value)
  189.     G.nodes[r_child][LEFT] = node_value
  191.     if parent is not None:
  192.         G.add_edge(parent, r_child)
  193.         if r_child > parent:
  194.             G.nodes[parent][RIGHT] = r_child
  195.         else:
  196.             G.nodes[parent][LEFT] = r_child
  198. # 根据一个节点的值，获得该节点的父节点
  199. def get_parent(G, n):
  200.     predecessors = G.predecessors(n)
  201.     ps = list(predecessors)
  202.     parent = None
  203.     if len(ps) != 0:
  204.         parent = ps.pop()
  205.     return parent
  207. # 给定一个节点的值，检测距离该节点最近的失衡的点
  208. # 一般来说，当在树中插上一个新值后，导致树失衡，如果树很高时候，失衡点会很多，
  209. # 该函数搜索出距离插入点d最近的那个失衡点（距离d最近）
  210. def check_blance(G, d):
  211.     unblance_nodes = []
  212.     for n in G.nodes(data=True):
  213.         f = get_blance_factor(G, n[0])
  214.         if abs(f) > 1:
  215.             node = (n, f)
  216.             unblance_nodes.append(node)
  218.     min_len = float('inf')
  219.     node = None
  220.     for n in unblance_nodes:
  221.         lenght = nx.shortest_path_length(G, source=n[0][0], target=d)
  222.         if lenght < min_len:
  223.             min_len = lenght
  224.             node = n
  226.     return node
  228. # 获得该节点的平衡因子
  229. def get_blance_factor(G, number):
  230.     factor = 0
  231.     if get_node_height(G, number) == 0:
  232.         factor = 0
  233.         # print(number, '平衡因子', factor)
  234.         return factor
  236.     left = G.nodes[number][LEFT]
  237.     right = G.nodes[number][RIGHT]
  239.     lh = 0
  240.     rh = 0
  241.     if left is not None:
  242.         lh = get_node_height(G, left) + 1
  244.     if right is not None:
  245.         rh = get_node_height(G, right) + 1
  247.     factor = lh - rh
  248.     # print(number, '平衡因子', factor)
  249.     return factor
  251. # 给定一个节点的值，获得该节点的树高度
  252. def get_node_height(G, number):
  253.     height = 0
  254.     successors = G.successors(number)
  255.     if len(list(successors)) == 0:
  256.         height = 0
  257.         # print(number, '高度', height)
  258.         return height
  260.     bfs = nx.bfs_tree(G, number)
  261.     node_v = list(bfs).pop()
  262.     # print(number, '最远的点', node_v)
  263.     while True:
  264.         predecessors = G.predecessors(node_v)
  265.         ps = list(predecessors)
  266.         # print(node_v, '前继', ps)
  267.         if len(ps) == 0:
  268.             break
  269.         else:
  270.             p_node_v = ps.pop()
  271.             height = height + 1
  272.             if p_node_v == number:
  273.                 break
  274.             else:
  275.                 node_v = p_node_v
  277.     # print(number, '高度', height)
  278.     return height
  280. # 根据一个节点的值，获取该节点的完整节点信息
  281. def get_node_by_value(G, v):
  282.     node = None
  283.     for n in G.nodes(data=True):
  284.         if n[0] == v:
  285.             node = n
  286.             break
  287.     return node
  289. # 输入一个值，根据这个值构建节点，并插入到树中
  290. def insert(G, d):
  291.     if G.number_of_nodes() == 0:
  292.         G.add_node(d)
  293.         G.nodes[d][RIGHT] = None
  294.         G.nodes[d][LEFT] = None
  295.         return
  297.     print('开始插入', d)
  298.     root_node = get_root_node(G)
  299.     print('根节点', root_node)
  301.     while True:
  302.         left = root_node[1][LEFT]
  303.         right = root_node[1][RIGHT]
  305.         if right is None:
  306.             if d > root_node[0]:
  307.                 root_node[1][RIGHT] = d
  308.                 G.add_node(d)
  309.                 G.nodes[d][LEFT] = None
  310.                 G.nodes[d][RIGHT] = None
  311.                 G.add_edge(root_node[0], d)
  312.                 break
  314.         if left is None:
  315.             if d < root_node[0]:
  316.                 root_node[1][LEFT] = d
  317.                 G.add_node(d)
  318.                 G.nodes[d][LEFT] = None
  319.                 G.nodes[d][RIGHT] = None
  320.                 G.add_edge(root_node[0], d)
  321.                 break
  323.         if d > root_node[0]:
  324.             val = root_node[1][RIGHT]
  325.             root_node = get_node_by_value(G, val)
  326.         else:
  327.             val = root_node[1][LEFT]
  328.             root_node = get_node_by_value(G, val)
  330. if __name__ == '__main__':
  331.     app()

运行日志输出：

  1. data [10, 7, 16, 17, 1, 0, 6, 15, 3, 12, 18, 14, 2, 5, 19, 8, 13, 11, 9, 4]
  2. -----
  3. -----
  4. 开始插入 7
  5. 根节点 (10, {'right': None, 'left': None})
  6. -----
  7. 开始插入 16
  8. 根节点 (10, {'right': None, 'left': 7})
  9. -----
  10. 开始插入 17
  11. 根节点 (10, {'right': 16, 'left': 7})
  12. -----
  13. 开始插入 1
  14. 根节点 (10, {'right': 16, 'left': 7})
  15. -----
  16. 开始插入 0
  17. 根节点 (10, {'right': 16, 'left': 7})
  18. 找到失衡点 ((7, {'left': 1, 'right': None}), 2)
  19. 失衡 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})]
  20. rotate_right 7
  21. 7 父节点 10
  22. -----
  23. 开始插入 6
  24. 根节点 (10, {'right': 16, 'left': 1})
  25. -----
  26. 开始插入 15
  27. 根节点 (10, {'right': 16, 'left': 1})
  28. -----
  29. 开始插入 3
  30. 根节点 (10, {'right': 16, 'left': 1})
  31. 找到失衡点 ((7, {'left': 6, 'right': None}), 2)
  32. 失衡 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})]
  33. rotate_right 7
  34. 7 父节点 1
  35. -----
  36. 开始插入 12
  37. 根节点 (10, {'right': 16, 'left': 1})
  38. -----
  39. 开始插入 18
  40. 根节点 (10, {'right': 16, 'left': 1})
  41. -----
  42. 开始插入 14
  43. 根节点 (10, {'right': 16, 'left': 1})
  44. 找到失衡点 ((15, {'left': 12, 'right': None}), 2)
  45. 失衡 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})]
  46. rotate_left 12
  47. 12 父节点 15
  48. rotate_right 15
  49. 15 父节点 16
  50. -----
  51. 开始插入 2
  52. 根节点 (10, {'right': 16, 'left': 1})
  53. 找到失衡点 ((1, {'left': 0, 'right': 6}), -2)
  54. 失衡 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})]
  55. rotate_right 6
  56. 6 父节点 1
  57. rotate_left 1
  58. 1 父节点 10
  59. -----
  60. 开始插入 5
  61. 根节点 (10, {'right': 16, 'left': 3})
  62. -----
  63. 开始插入 19
  64. 根节点 (10, {'right': 16, 'left': 3})
  65. 找到失衡点 ((17, {'left': None, 'right': 18}), -2)
  66. 失衡 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})]
  67. rotate_left 17
  68. 17 父节点 16
  69. -----
  70. 开始插入 8
  71. 根节点 (10, {'right': 16, 'left': 3})
  72. -----
  73. 开始插入 13
  74. 根节点 (10, {'right': 16, 'left': 3})
  75. -----
  76. 开始插入 11
  77. 根节点 (10, {'right': 16, 'left': 3})
  78. -----
  79. 开始插入 9
  80. 根节点 (10, {'right': 16, 'left': 3})
  81. 找到失衡点 ((7, {'left': None, 'right': 8}), -2)
  82. 失衡 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})]
  83. rotate_left 7
  84. 7 父节点 6
  85. -----
  86. 开始插入 4
  87. 根节点 (10, {'right': 16, 'left': 3})
  88. ---
  89. 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})]
  90. 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, {})]
  91. =====
  93.         ____________10_______________
  94.        /                             \
  95.     __3____                       ____16___
  96.    /       \                     /         \
  97.   1         6__             ____14         _18
  98.  / \       /   \           /      \       /   \
  99. 0   2     5     8        _12       15    17    19
  100.          /     / \      /   \
  101.         4     7   9    11    13
  103. 是平衡的AVL树吗? True

再跑一轮测试：

  1. data [18, 14, 10, 5, 15, 9, 19, 1, 2, 11, 17, 16, 8, 6, 4, 0, 12, 7, 13, 3]
  2. -----
  3. -----
  4. 开始插入 14
  5. 根节点 (18, {'right': None, 'left': None})
  6. -----
  7. 开始插入 10
  8. 根节点 (18, {'right': None, 'left': 14})
  9. 找到失衡点 ((18, {'right': None, 'left': 14}), 2)
  10. 失衡 nodes [(18, {'right': None, 'left': 14}), (14, {'left': 10, 'right': None}), (10, {'left': None, 'right': None})]
  11. rotate_right 18
  12. 18 父节点 None
  13. -----
  14. 开始插入 5
  15. 根节点 (14, {'left': 10, 'right': 18})
  16. -----
  17. 开始插入 15
  18. 根节点 (14, {'left': 10, 'right': 18})
  19. -----
  20. 开始插入 9
  21. 根节点 (14, {'left': 10, 'right': 18})
  22. 找到失衡点 ((10, {'left': 5, 'right': None}), 2)
  23. 失衡 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})]
  24. rotate_left 5
  25. 5 父节点 10
  26. rotate_right 10
  27. 10 父节点 14
  28. -----
  29. 开始插入 19
  30. 根节点 (14, {'left': 9, 'right': 18})
  31. -----
  32. 开始插入 1
  33. 根节点 (14, {'left': 9, 'right': 18})
  34. -----
  35. 开始插入 2
  36. 根节点 (14, {'left': 9, 'right': 18})
  37. 找到失衡点 ((5, {'left': 1, 'right': None}), 2)
  38. 失衡 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})]
  39. rotate_left 1
  40. 1 父节点 5
  41. rotate_right 5
  42. 5 父节点 9
  43. -----
  44. 开始插入 11
  45. 根节点 (14, {'left': 9, 'right': 18})
  46. -----
  47. 开始插入 17
  48. 根节点 (14, {'left': 9, 'right': 18})
  49. -----
  50. 开始插入 16
  51. 根节点 (14, {'left': 9, 'right': 18})
  52. 找到失衡点 ((15, {'left': None, 'right': 17}), -2)
  53. 失衡 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})]
  54. rotate_right 17
  55. 17 父节点 15
  56. rotate_left 15
  57. 15 父节点 18
  58. -----
  59. 开始插入 8
  60. 根节点 (14, {'left': 9, 'right': 18})
  61. -----
  62. 开始插入 6
  63. 根节点 (14, {'left': 9, 'right': 18})
  64. 找到失衡点 ((5, {'left': None, 'right': 8}), -2)
  65. 失衡 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})]
  66. rotate_right 8
  67. 8 父节点 5
  68. rotate_left 5
  69. 5 父节点 2
  70. -----
  71. 开始插入 4
  72. 根节点 (14, {'left': 9, 'right': 18})
  73. 找到失衡点 ((2, {'left': 1, 'right': 6}), -2)
  74. 失衡 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})]
  75. rotate_right 6
  76. 6 父节点 2
  77. rotate_left 2
  78. 2 父节点 9
  79. -----
  80. 开始插入 0
  81. 根节点 (14, {'left': 9, 'right': 18})
  82. 找到失衡点 ((9, {'left': 5, 'right': 10}), 2)
  83. 失衡 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})]
  84. rotate_right 9
  85. 9 父节点 14
  86. -----
  87. 开始插入 12
  88. 根节点 (14, {'left': 5, 'right': 18})
  89. 找到失衡点 ((10, {'left': None, 'right': 11}), -2)
  90. 失衡 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})]
  91. rotate_left 10
  92. 10 父节点 9
  93. -----
  94. 开始插入 7
  95. 根节点 (14, {'left': 5, 'right': 18})
  96. 找到失衡点 ((6, {'left': None, 'right': 8}), -2)
  97. 失衡 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})]
  98. rotate_right 8
  99. 8 父节点 6
  100. rotate_left 6
  101. 6 父节点 9
  102. -----
  103. 开始插入 13
  104. 根节点 (14, {'left': 5, 'right': 18})
  105. 找到失衡点 ((14, {'left': 5, 'right': 18}), 2)
  106. 失衡 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})]
  107. rotate_left 5
  108. 5 父节点 14
  109. rotate_right 14
  110. 14 父节点 None
  111. -----
  112. 开始插入 3
  113. 根节点 (9, {'left': 5, 'right': 14})
  114. ---
  115. 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})]
  116. 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, {})]
  117. =====
  119.             ______9____________
  120.            /                   \
  121.       ____5__            _______14_________
  122.      /       \          /                  \
  123.     2__       7       _11               ____18
  124.    /   \     / \     /   \             /      \
  125.   1     4   6   8   10    12         _16       19
  126.  /     /                    \       /   \
  127. 0     3                      13    15    17
  129. 是平衡的AVL树吗? True

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://zhangphil.blog.csdn.net/article/details/121634111

内容来源于网络，如有侵权，请联系作者删除！

python算法

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com