Python'da bir ağacın sağa ve sola dönüşü

Question

Sınıfı kullanıyorum:

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

ve ben bu ağacı yarattım:

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

Bu kodu denedim:

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

Ancak işe yaramadı, kök düğümü kullanarak n_12bazı düğümleri siler. Neden işe yaramadı ve neden tüm düğümlere sahip olmadığımı anlamıyorum. Ben ararsam rightRotate(n_1), ben sonsuz döngü var.

Answer 1

"Sonsuz bir döngüm var" yazarsınız , ancak kodunuzun bir döngüsü yoktur, bu nedenle bu kodunuzun başka bir yerinde gerçekleşiyor olmalıdır.

İki sorun görüyorum:

1) Ödev koşulsuz olmalıdır

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

Bu atama da ne zaman gereklidir lr is None. Değil, Eğer t.right.lefteşit kalacak kadar lhangi to anda, ve sizin bu nedenle aslında senin ağacında bir döngü ile bırakılır.

2) Çift diş çekme

Ağacınız çift dişli, yani parentbağlantıları da var . Ancak bunlar rightRotateişlevinizde güncellenmez . Bu nedenle ya parentbağlantı olmadan yapın (tercih edilir) ya da kodunuzu, parentbağlantılar da rotasyona göre güncellenecek şekilde uyarlayın .

Diğer Açıklama:

Aşağıdaki kod parçası basitleştirilebilir:

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

Bu, şu şekilde azaltılabilir:

t.right.left = lr

ya da:

n.left = lr

Nihai Kod

Yukarıda belirtilen değişikliklerle, işleviniz şunlar olabilir:

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

parentTek iş parçacıklı sürümü almak için ile satırları kaldırmanız yeterlidir.