我使用類：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)，我有一個無限循環。
1 回答
MMTTMM
TA貢獻1869條經驗 獲得超4個贊
你寫了"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即可獲得單線程版本。
添加回答
舉報
0/150
提交
取消