问题
Root of AVL Tree
代码
def adjust(A, tree):
nodeA = tree[A]
if nodeA[3] == 2:
B = nodeA[1]
nodeB = tree[B]
if nodeB[3] == 1:
tree[A][1] = nodeB[2]
tree[B][2] = A
if tree[0] == A:
tree[0] = B
elif nodeB[3] == -1:
C = nodeB[2]
nodeC = tree[C]
tree[C][1] = B
tree[C][2] = A
tree[B][2] = nodeC[1]
tree[A][1] = nodeC[2]
if tree[0] == A:
tree[0] = C
tree[B][3] = 0
elif nodeA[3] == -2:
B = nodeA[2]
nodeB = tree[B]
if nodeB[3] == -1:
tree[A][2] = nodeB[1]
tree[B][1] = A
if tree[0] == A:
tree[0] = B
elif nodeB[3] == 1:
C = nodeB[1]
nodeC = tree[C]
tree[C][2] = B
tree[C][1] = A
tree[B][1] = nodeC[2]
tree[A][2] = nodeC[1]
if tree[0] == A:
tree[0] = C
tree[B][3] = 0
tree[A][3] = 0
def insert(i, tree):
i = [int(i), '-', '-', 0]
tree.append(i)
p = [-1]
j = tree[tree[0]]
while True:
if j[0] == i[0]:
break
elif j[0] > i[0]:
j[3] += 1
if j[3] == 2:
p.append(tree.index(j))
if j[1] == '-':
j[1] = len(tree) - 1
break
j = tree[j[1]]
elif j[0] < i[0]:
j[3] -= 1
if j[3] == -2:
p.append(tree.index(j))
if j[2] == '-':
j[2] = len(tree) - 1
break
j = tree[j[2]]
if p[-1] >= 0:
for node in p[1:-1]:
if tree[node][3] == 2:
tree[node][3] = 1
elif tree[node][3] == -2:
tree[node][3] = -1
adjust(p[-1], tree)
def buildAVL(nodes):
tree = [1]
for i in nodes:
insert(i, tree)
return tree
n = int(input())
nodes = input().split(' ')
tree = buildAVL(nodes)
root = tree[0]
print(tree[root][0])
有任何问题请回复提出。然后欢迎关注微信公众号格物致愚：
格物致愚
