AVL insertion

avl_insert.py

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1

class Tree(object):
    def __init__(self):
        self.root = None

    def preOrder(self, root):

        if not root:
            return

        print("{0} ".format(root.value), end="") 
        self.preOrder(root.left) 
        self.preOrder(root.right)

    def insert(self, value):
        self.root = self.__insert(value, self.root)

    def __insert(self, value, node):
        if not node:
            return Node(value)
        elif value < node.value:
            node.left = self.__insert(value, node.left)
        else:
            node.right = self.__insert(value, node.right)

        node.height = 1 + max(self.__get_height(node.left), self.__get_height(node.right))
        balance = self.__get_balance(node)

        if balance > 1 and value < node.left.value:
            return self.__rotate_right(node)

        if balance < -1 and value > node.right.value:
            return self.__rotate_left(node)

        if balance > 1 and value > node.left.value:
            node.left = self.__rotate_left(node.left)
            return self.__rotate_right(node)

        if balance < -1 and value < node.right.value:
            node.right = self.__rotate_right(node.right)
            return self.__rotate_left(node)

        return node

    def __rotate_left(self, node):
        right_child = node.right
        right_left_grandchild = right_child.left

        right_child.left = node
        node.right = right_left_grandchild

        node.height = 1 + max(self.__get_height(node.left), self.__get_height(node.right))
        right_child.height = 1 + max(self.__get_height(right_child.left), self.__get_height(right_child.right))

        return right_child

    def __rotate_right(self, node):
        left_child = node.left
        left_right_grandchild = left_child.right

        left_child.right = node
        node.left = left_right_grandchild

        node.height = 1 + max(self.__get_height(node.left), self.__get_height(node.right))
        left_child.height = 1 + max(self.__get_height(left_child.left), self.__get_height(left_child.right))

        return left_child

    def __get_balance(self, node):
        return self.__get_height(node.left) - self.__get_height(node.right)

    def __get_height(self, node):
        if not node: return 0
        return node.height

t = Tree()
t.insert(10)
t.insert(20)
t.insert(30)
t.insert(40)
t.insert(50)
t.insert(25)
t.preOrder(t.root)