Insertion in AVL tree
Tags: algorithms, python, programming, computerscience
Published: 2021-07-02 20:49:22

Hi, I'm Aya Bouchiha and today I'm going to talk about the insertion in AVL tree, but if you're not familiar with AVL trees, check these posts below :

+ [introduction to AVL trees](https://dev.to/ayabouchiha/introduction-to-avl-tree-fbk) 

+ [rotation in AVL trees](https://dev.to/ayabouchiha/rotation-in-avl-tree-376o)

Before we get started, I want to mention that Balance Factor
 of a balanced node should be always {-1,0,1} <br/>
`BalanceFactor=height(left sub-tree)-height(right sub-tree)`

## Insertion implementation in python from [geeksforgeeks](https://www.geeksforgeeks.org/avl-tree-set-1-insertion/)

```python
"""
    this insertion implementation is from geeksforgeeks
    https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
    (This code is contributed by Ajitesh Pathak)
"""
class TreeNode(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1
 
# AVL tree class which supports the
# Insert operation
class AVL_Tree(object):
 
    # Recursive function to insert key in
    # subtree rooted with node and returns
    # new root of subtree.
    def insert(self, root, key):
     
        # Step 1 - Perform normal BST
        if not root:
            return TreeNode(key)
        elif key < root.val:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)
 
        # Step 2 - Update the height of the
        # ancestor node
        root.height = 1 + max(self.getHeight(root.left),
                           self.getHeight(root.right))
 
        # Step 3 - Get the balance factor
        balance = self.getBalance(root)
 
        # Step 4 - If the node is unbalanced,
        # then try out the 4 cases
        # Case 1 - Left Left
        if balance > 1 and key < root.left.val:
            return self.rightRotate(root)
 
        # Case 2 - Right Right
        if balance < -1 and key > root.right.val:
            return self.leftRotate(root)
 
        # Case 3 - Left Right
        if balance > 1 and key > root.left.val:
            root.left = self.leftRotate(root.left)
            return self.rightRotate(root)
 
        # Case 4 - Right Left
        if balance < -1 and key < root.right.val:
            root.right = self.rightRotate(root.right)
            return self.leftRotate(root)
 
        return root
 
    def leftRotate(self, z):
 
        y = z.right
        T2 = y.left

        # Perform rotation
        y.left = z
        z.right = T2
 
        # Update heights
        z.height = 1 + max(self.getHeight(z.left),
                         self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left),
                         self.getHeight(y.right))
 
        # Return the new root
        return y
 
    def rightRotate(self, z):
 
        y = z.left
        T3 = y.right
 
        # Perform rotation
        y.right = z
        z.left = T3
 
        # Update heights
        z.height = 1 + max(self.getHeight(z.left),
                        self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left),
                        self.getHeight(y.right))
 
        # Return the new root
        return y
 
    def getHeight(self, root):
        if not root:
            return 0
 
        return root.height
 
    def getBalance(self, root):
        if not root:
            return 0
 
        return self.getHeight(root.left) - self.getHeight(root.right)


    def preOrder(self, root):
        if not root:
            return
        print(root.val, end="\t")
        self.preOrder(root.left)
        self.preOrder(root.right)



# Driver program to test above function
myTree = AVL_Tree()
root = None
root = myTree.insert(root, 10)
root = myTree.insert(root, 20)
root = myTree.insert(root, 30)
root = myTree.insert(root, 40)
root = myTree.insert(root, 50)
root = myTree.insert(root, 25)
"""
     30
    /  \
  20   40
 /  \     \
10  25    50
"""
# Preorder Traversal
print("Preorder traversal of the","constructed AVL tree is")
myTree.preOrder(root)
```
for more details check this [article](https://www.geeksforgeeks.org/avl-tree-set-1-insertion/)

## References and useful resources

+ [https://www.programiz.com/dsa/avl-tree](https://www.programiz.com/dsa/avl-tree)
+ [https://www.geeksforgeeks.org/avl-tree-set-1-insertion/](https://www.geeksforgeeks.org/avl-tree-set-1-insertion/)
+ [https://www.geeksforgeeks.org/program-to-calculate-height-and-depth-of-a-node-in-a-binary-tree/](https://www.geeksforgeeks.org/program-to-calculate-height-and-depth-of-a-node-in-a-binary-tree/)
+ [https://www.youtube.com/watch?v=_8qqlVH5NC0](https://www.youtube.com/watch?v=_8qqlVH5NC0)

\#day_20

Happy coding!