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
