CODEWITHSUNDEEP
pythonalgorithmavl-tree
Vinicius Vasconcelos
Vinicius Vasconcelos

Reputation: 140

Rotating the left the subtrees in an AVL Tree in python

A bit of a newbie to computing science.

I have the basics for a binary tree in Python and I was studying some of the applications in an AVL tree:

class TreeBinary:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def show_aux(root):
    if not root:
        return ''
    string = str(root.data)
    if root.left or root.right:
        string += ' (' + show_aux(root.left) + ')'  # Space before '('
    else:
        string += ' ('  # Space before '('
        string += ')'
    if root.right:
        string += ' (' + show_aux(root.right) + ')'  # Space before '('
    else:
        string += ' ('  # Space before '('
        string += ')'
    return string


def show(root):
    print('(' + show_aux(root) + ')')


def rotate_left(root):
    rotated_root = root.right
    try:
        temp = rotated_root.left
    except:
        show(root)

    rotated_root.left = root
    root.right = temp
    return rotated_root


root = TreeBinary('a')
root.left = TreeBinary('b')
root.right = TreeBinary('c')
show(root)
print()
root.left = rotate_left(root.left)
show(root)

One of the challenges I'm trying to solve is to rotate the left side of a tree in a function that takes the root as a parameter, but I'm getting the following error:

root.left = rotate_left(root.left)
  File "rotated_left_binary_tree.py", line 36, in rotate_left
    rotated_root.left = root
AttributeError: 'NoneType' object has no attribute 'left'

I tried to solve, but it only prints the root and the right root

Upvotes: 0

Views: 379

Answers (1)

trincot
trincot

Reputation: 350270

You are rotating the subtree at b, but your function expects the given node to have a right child, which obviously is not the case: there is nothing to rotate at b.

It would have made more sense if your main code would have asked for a rotation at node a:

root = rotate_left(root)

On the other hand, it would be good to protect your rotate functions a bit. Let it return the root unchanged when it has no right child:

def rotate_left(root):
    rotated_root = root.right
    if not rotated_root:
        return root  # cannot rotate here
    try:
        temp = rotated_root.left
    except:
        show(root)

    rotated_root.left = root
    root.right = temp
    return rotated_root

Now your original main code would not trigger an exception, but the tree would also not change -- which is indeed the correct behaviour when you call the rotation function on a leaf node (b).

Upvotes: 2

Related Questions