在 python 中向左旋转 AVL 树中的子树

Question

计算科学的新手。

我在 Python 中掌握了二叉树的基础知识，并且正在研究 AVL 树中的一些应用程序：

class TreeBinary:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def show_aux(root):
    if not root:
        return ''
    string = str(root.data)
    if root.left or root.right:
        string += ' (' + show_aux(root.left) + ')'  # Space before '('
    else:
        string += ' ('  # Space before '('
        string += ')'
    if root.right:
        string += ' (' + show_aux(root.right) + ')'  # Space before '('
    else:
        string += ' ('  # Space before '('
        string += ')'
    return string


def show(root):
    print('(' + show_aux(root) + ')')


def rotate_left(root):
    rotated_root = root.right
    try:
        temp = rotated_root.left
    except:
        show(root)

    rotated_root.left = root
    root.right = temp
    return rotated_root


root = TreeBinary('a')
root.left = TreeBinary('b')
root.right = TreeBinary('c')
show(root)
print()
root.left = rotate_left(root.left)
show(root)

我要解决的挑战之一是在将根作为参数的函数中旋转树的左侧，但出现以下错误：

root.left = rotate_left(root.left)
  File "rotated_left_binary_tree.py", line 36, in rotate_left
    rotated_root.left = root
AttributeError: 'NoneType' object has no attribute 'left'

我试图解决，但它只打印根和右根

Answer 1

您正在 b 处旋转子树，但您的函数期望给定节点具有正确的 child，显然情况并非如此：在 [=12] 处没有可旋转的东西=].

如果您的主代码要求在节点 a:

处进行轮换，那就更有意义了

root = rotate_left(root)

另一方面，稍微保护一下旋转函数会很好。让它return没有权限时根不变child:

def rotate_left(root):
    rotated_root = root.right
    if not rotated_root:
        return root  # cannot rotate here
    try:
        temp = rotated_root.left
    except:
        show(root)

    rotated_root.left = root
    root.right = temp
    return rotated_root

现在你原来的主代码不会触发异常，但树也不会改变——当你在叶节点 (b) 上调用旋转函数时，这确实是正确的行为。

在 python 中向左旋转 AVL 树中的子树

Rotating the left the subtrees in an AVL Tree in python

python

algorithm

avl-tree