问题

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])

有任何问题请回复提出。然后欢迎关注微信公众号格物致愚：

格物致愚