CODEWITHSUNDEEP
pythontreerotation
Ele975
Ele975

Reputation: 372

Right and left rotation of a tree in python

I use the class:

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

and I have created this 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

I tried this code:

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

But it didn't work, using the root node n_12 it deletes some nodes. Why it didn't work and I don't understand why I don't have all the nodes. If I call rightRotate(n_1), I have an infinite loop.

Upvotes: 1

Views: 3748

Answers (1)

trincot
trincot

Reputation: 350147

You write "I have an infinite loop", but your code has no loop, so that must be happening elsewhere in your code.

I see two issues:

1) Assignment should be unconditional

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

This assignment is also needed when lr is None. If not, t.right.left will stay equal to l which is t at that moment, and so you indeed are left with a loop in your tree.

2) Double threading

Your tree is double threaded, i.e., it also has parent links. But these are not updated in your rightRotate function. So either do without parent links (which is preferable), or adapt your code so that also the parent links are updated according to the rotation.

Other Remark:

The following piece of code could be simplified:

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

So that can be reduced to just:

t.right.left = lr

or even:

n.left = lr

Final Code

With above mentioned changes, your function could be:

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

Just remove the lines with parent to get the single-threaded version.

Upvotes: 1

Related Questions