Xoay phải và trái của một cái cây trong python

Question

Tôi sử dụng lớp học:

class Node:
    def __init__(self, value):
        self.key = value
        self.left = None
        self.right = None
        self.parent = None

và tôi đã tạo ra cây này:

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

Tôi đã thử mã này:

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

Nhưng nó không hoạt động, bằng cách sử dụng nút gốc, n_12nó sẽ xóa một số nút. Tại sao nó không hoạt động và tôi không hiểu tại sao tôi không có tất cả các nút. Nếu tôi gọi rightRotate(n_1), tôi có một vòng lặp vô hạn.

Answer 1

Bạn viết "Tôi có một vòng lặp vô hạn" , nhưng mã của bạn không có vòng lặp, vì vậy điều đó phải xảy ra ở nơi khác trong mã của bạn.

Tôi thấy hai vấn đề:

1) Việc chuyển nhượng phải là vô điều kiện

if lr != None:
    t.right.left = lr

Sự phân công này cũng cần thiết khi lr is None. Nếu không, t.right.leftsẽ ở lại bằng lđó là tvào thời điểm đó, và do đó bạn thực sự là trái với một vòng lặp trong cây của bạn.

2) Luồng đôi

Cây của bạn là hai luồng, tức là, nó cũng có parentcác liên kết. Nhưng những điều này không được cập nhật trong rightRotatechức năng của bạn . Vì vậy, hoặc làm mà không có parentliên kết (tốt hơn) hoặc điều chỉnh mã của bạn để các parentliên kết cũng được cập nhật theo vòng quay.

Nhận xét khác:

Đoạn mã sau có thể được đơn giản hóa:

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

Vì vậy, điều đó có thể được giảm xuống chỉ:

t.right.left = lr

hoặc thậm chí:

n.left = lr

Mã cuối cùng

Với những thay đổi đã đề cập ở trên, chức năng của bạn có thể là:

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

Chỉ cần loại bỏ các dòng với parentđể có được phiên bản đơn luồng.