การหมุนขวาและซ้ายของต้นไม้ในหลาม
ฉันใช้คลาส:
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)
ไปฉันจะวนซ้ำไม่สิ้นสุด
คำตอบ
คุณเขียนว่า "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
เพื่อให้ได้เวอร์ชันเธรดเดียว