python中树的左右旋转

Question

我使用类：class Node:    def __init__(self, value):        self.key = value        self.left = None        self.right = None        self.parent = None我创建了这棵树：n_12 = Node(12)n_15 = Node(15)n_3 = Node(3)n_7 = Node(7)n_1 = Node(1)n_2 = Node(2)n_not1 = Node(-1)n_12.right = n_15n_12.left = n_3n_3.right = n_7n_3.left = n_1n_1.right = n_2n_1.left = n_not1n_12.parent = Nonen_15.parent = n_12n_3.parent = n_12n_7.parent = n_3n_1.parent = n_3n_2.parent = n_1n_not1.parent = n_1我试过这段代码：def rightRotate(t):     if t == None or t.left == None:        return None    n = t    l = t.left    r = t.right    lr = t.left.right    ll = t.left.left    t = t.left    t.right = n    if r != None:        t.right.right = r    if lr != None:        t.right.left = lr    if ll != None:        t.left = ll但它没有用，它使用根节点n_12删除了一些节点。为什么它不起作用，我不明白为什么我没有所有节点。如果我打电话rightRotate(n_1)，我有一个无限循环。

Answer 1

你写了"I have an infinite loop"，但你的代码没有循环，所以这一定发生在你代码的其他地方。

我看到两个问题：

1) 赋值应该是无条件的

if lr != None:

    t.right.left = lr

时也需要这个赋值lr is None。如果不是，t.right.left将保持等于那一刻l的那个t，所以你确实在你的树中留下了一个循环。

2）双线程

您的树是双线程的，即它也有parent链接。但是这些不会在您的rightRotate功能中更新。因此，要么不使用parent链接（这是更可取的），要么调整您的代码，以便链接也parent根据轮换进行更新。

其他备注：

可以简化以下代码：

if r != None:

    t.right.right = r   # was already equal to r

if lr != None:

    t.right.left = lr   # see above. should not be behind a condition

if ll != None:

    t.left = ll         # was already equal to ll

这样就可以简化为：

t.right.left = lr

甚至：

n.left = lr

最终代码

通过上述更改，您的功能可以是：

class Node:

    def __init__(self, value):

        self.key = value

        self.left = None

        self.right = None

        self.parent = None

def rightRotate(node):

    if node is None or node.left is None:

        return node

    parent = node.parent

    left = node.left

    left_right = left.right

    # change edge 1

    if parent: # find out if node is a left or right child of node

        if parent.left == node:

            parent.left = left

        else:

            parent.right = left

    left.parent = parent

    # change edge 2

    left.right = node

    node.parent = left

    # change edge 3

    node.left = left_right

    if left_right:

        left_right.parent = node

    return left  # the node that took the position of node

# your code to build the tree

n_12 = Node(12)

n_15 = Node(15)

n_3 = Node(3)

n_7 = Node(7)

n_1 = Node(1)

n_2 = Node(2)

n_not1 = Node(-1)

n_12.right = n_15

n_12.left = n_3

n_3.right = n_7

n_3.left = n_1

n_1.right = n_2

n_1.left = n_not1

n_12.parent = None

n_15.parent = n_12

n_3.parent = n_12

n_7.parent = n_3

n_1.parent = n_3

n_2.parent = n_1

n_not1.parent = n_1

# rotate the root

root = n_12

root = rightRotate(root) # returns the node that took the place of n_12

只需删除带有的行parent即可获得单线程版本。