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_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

我试过这段代码：

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 rif lr != None:    t.right.left = lr   # see above. should not be behind a conditionif 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 = Nonedef 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 treen_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# rotate the rootroot = n_12root = rightRotate(root) # returns the node that took the place of n_12只需删除带有的行parent即可获得单线程版本。