Rotación derecha e izquierda de un árbol en Python

Aug 19 2020

Yo uso la clase:

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

y he creado este árbol:

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

Probé este código:

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

Pero no funcionó, usando el nodo raíz n_12elimina algunos nodos. Por qué no funcionó y no entiendo por qué no tengo todos los nodos. Si llamo rightRotate(n_1), tengo un bucle infinito.

Respuestas

trincot Aug 19 2020 at 18:59

Escribe "Tengo un bucle infinito" , pero su código no tiene bucle, por lo que debe estar sucediendo en otra parte de su código.

Veo dos problemas:

1) La cesión debe ser incondicional

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

Esta asignación también es necesaria cuando lr is None. Si no, t.right.leftse mantendrá igual a lo lque está ten ese momento, por lo que de hecho te queda un bucle en tu árbol.

2) Doble roscado

Su árbol es de doble hilo, es decir, también tiene parentenlaces. Pero estos no se actualizan en su rightRotatefunción. Así que prescindir de los parentenlaces (lo que es preferible) o adaptar tu código para que también los parentenlaces se actualicen de acuerdo con la rotación.

Otra observación:

El siguiente fragmento de código podría simplificarse:

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

Entonces eso se puede reducir a solo:

t.right.left = lr

o incluso:

n.left = lr

Código final

Con los cambios mencionados anteriormente, su función podría ser:

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

Simplemente elimine las líneas con parentpara obtener la versión de un solo subproceso.