Rechts- und Linksdrehung eines Baumes in Python

Question

Ich benutze die Klasse:

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

und ich habe diesen Baum geschaffen:

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

Ich habe diesen Code ausprobiert:

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

Aber es hat nicht funktioniert, mit dem Wurzelknoten werden n_12einige Knoten gelöscht. Warum es nicht funktioniert hat und ich nicht verstehe, warum ich nicht alle Knoten habe. Wenn ich anrufe rightRotate(n_1), habe ich eine Endlosschleife.

Answer 1

Sie schreiben "Ich habe eine Endlosschleife" , aber Ihr Code hat keine Schleife, so dass dies an anderer Stelle in Ihrem Code geschehen muss.

Ich sehe zwei Probleme:

1) Die Zuordnung sollte unbedingt erfolgen

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

Diese Zuordnung wird auch benötigt, wenn lr is None. Wenn nicht, t.right.leftbleibt gleich, lwas tin diesem Moment ist, und so bleibt Ihnen tatsächlich eine Schleife in Ihrem Baum.

2) Doppelfädeln

Ihr Baum ist doppelt eingefädelt, dh er hat auch parentLinks. Diese werden jedoch in Ihrer rightRotateFunktion nicht aktualisiert . Verzichten Sie also entweder auf parentLinks (was vorzuziehen ist) oder passen Sie Ihren Code so an, dass auch die parentLinks entsprechend der Rotation aktualisiert werden.

Andere Bemerkung:

Der folgende Code könnte vereinfacht werden:

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

Das kann also auf Folgendes reduziert werden:

t.right.left = lr

oder auch:

n.left = lr

Endgültiger Code

Mit den oben genannten Änderungen könnte Ihre Funktion sein:

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

Entfernen Sie einfach die Zeilen mit parent, um die Single-Threaded-Version zu erhalten.