การหมุนขวาและซ้ายของต้นไม้ในหลาม

Aug 19 2020

ฉันใช้คลาส:

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)ไปฉันจะวนซ้ำไม่สิ้นสุด

คำตอบ

trincot Aug 19 2020 at 18:59

คุณเขียนว่า "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เพื่อให้ได้เวอร์ชันเธรดเดียว