### Python Program to Insert into AVL tree

Description:(Insertion In AVL) 1) Perform standard BST insert for w. 2) Starting from w, travel up and find the first unbalanced node.
Let z be the first unbalanced node, y be the child of z that comes
on the path from w to z and x be the grandchild of z that comes on
the path from w to z. 3) Re-balance the tree by performing appropriate rotations on the subtree
rooted with z. There can be 4 possible cases that needs to be handled
as x, y and z can be arranged in 4 ways. Following are the possible
4 arrangements: a) y is left child of z and x is left child of y
(Left Left Case - LL) b) y is left child of z and x is right child of y
(Left Right Case - LR) c) y is right child of z and x is right child of y
(Right Right Case - RR) d) y is right child of z and x is left child of y
(Right Left Case - RL)
```Eg1 - RR Rotation:
10
/  \
8    15
/ \   /  \
7   9  12  17
/           / \
6           16 18
/
4

(BST)

||
||
\/
10
/  \
8    15
/ \   /  \
6   9  12  17
/ \         / \
4   7       16 18

(AVL)```
```Eg2 - LL Rotation:
10
/  \
8    15
/ \   /  \
7   9  14  17
\
18
\
19

(BST)
||
||
\/

10
/  \
8    15
/ \   / \
7   9 14  18
/ \
17  19

(AVL)
```

```Eg3 - LR Rotation:
10
/  \
7    15
/ \   /  \
4   9  14  16
/
2
\
3

(BST)
||
||
\/
10
/  \
7    15
/ \   /  \
3   9  14  16
/ \
2   4

(AVL)
```

```Eg4 -  RL Rotation:

10
/  \
7    15
/ \   /  \
6   9  14  16
\
18
/
17
(BST)
||
||
\/

10
/  \
7    15
/ \   / \
6   9 14  17
/ \
16  18```
code: class TreeNode(object): def __init__(self,_val): self.val = _val self.left = None self.right = None self.height = 1 class AVL_Tree(object): #steps: # 1)perform simple BST insertion # 2)modify the height # 3)Get the Balancing Factor # 4)Balance The tree using required set of rotation to get balanced binary search tree,ie. AVL def insert(self, root, val): #Simple Bst Insertion: if not root: return TreeNode(val) elif val < root.val: root.left = self.insert(root.left, val) else: root.right = self.insert(root.right, val) # 2)modify the height root.height = 1 + max(self.Height(root.left), self.Height(root.right)) # 3)Get the Balancing Factor balance = self.check_Avl(root) # 4)Balance The tree using required set of rotation #RR Rotation as tree is Left Skewed if balance > 1 and val < root.left.val: return self.RR(root) #LL Rotation as tree is Right Skewed if balance < -1 and val > root.right.val: return self.LL(root) #RL Rotation as tree is Left then Right Skewed if balance > 1 and val > root.left.val: root.left = self.LL(root.left) return self.RR(root) #LR Rotation as tree is Right then Left Skewed if balance < -1 and val < root.right.val: root.right = self.RR(root.right) return self.LL(root) return root #LL Rotation def LL(self, node): p = node.right t = p.left #Rotations: p.left = node node.right = t #modify the heights: node.height = 1 + max(self.Height(node.left), self.Height(node.right)) p.height = 1 + max(self.Height(p.left), self.Height(p.right)) return p #LL Rotation def RR(self, node): p = node.left t = p.right #Rotations: p.right = node node.left = t #modify the heights: node.height = 1 + max(self.Height(node.left), self.Height(node.right)) p.height = 1 + max(self.Height(p.left), self.Height(p.right)) return p #Getting the Height def Height(self, root): if not root: return 0 return root.height #Getting the Balancing Factor def check_Avl(self, root): if not root: return 0 return self.Height(root.left) - self.Height(root.right) def preOrder(self, root): if not root: return print("{0} ".format(root.val), end="") self.preOrder(root.left) self.preOrder(root.right) def insert_data(_data): mytree = AVL_Tree() root = None for i in _data: root = mytree.insert(root,i) print("Preorder Traversal of constructed AVL tree is:") mytree.preOrder(root) print() if __name__ == "__main__": insert_data([10,8,15,7,9,12,17,16,18,6,4]) insert_data([10,8,15,7,9,14,17,18,19]) insert_data([10,7,15,4,9,14,16,2,3]) insert_data([10,7,6,9,15,14,16,17,18]) else: pass Output: Preorder Traversal of constructed AVL tree is: 10 8 6 4 7 9 15 12 17 16 18 Preorder Traversal of constructed AVL tree is: 10 8 7 9 15 14 18 17 19 Preorder Traversal of constructed AVL tree is: 10 7 3 2 4 9 15 14 16 Preorder Traversal of constructed AVL tree is: 10 7 6 9 15 14 17 16 18 %u200B

#### More Articles of Bhumika Makwana:

Name Views Likes
Python program to find largest value in each level of binary tree 1713 19
Python program to convert a given binary tree to a tree that holds logical and property 561 12
Python Program to Insert into AVL tree 3450 24
Python program to print the nodes at odd levels of a tree 670 20
Python program to check if a binary tree is binary search tree or not 1640 19
Python program to find smallest value in each level of binary tree 906 15
Implement A Queue With Two Stacks 603 19
Introduction to Python DeepLearning Library (Keras) 748 20
python program to remove duplicate elements from the binary search tree 2164 18
Python program to find largest subtree sum in a tree 988 22
Python program to find an element into binary search tree 611 21
Python program to check if two nodes are cousins in a binary tree 976 18
Python height of the binary search tree 2022 14
Python program to find averages of levels in binary tree 663 18
Python program to understand Red-Black trees and insert nodes to it 698 16
Python program to check if a given graph is tree or not 1641 17
Python program to find depth of the deepest odd level leaf node 696 26
Python program to delete leaf nodes with value as x 1058 28
Python program to find maximum level sum in binary tree 1238 19
Python Program to Calculate Size of a Tree using Recursion 2619 13
Python program to check if an array represents Inorder of Binary Search tree or not 800 29
Print cousins of a given node in Binary Tree 1329 25
Python program to find all duplicate subtrees 931 14
Python program to find lowest Common Ancestor in a binary search tree 565 16
Python program to check if removing an edge can divide a binary tree in two halves 773 15
Python Hands on Deep Learning with Keras 753 19
Python program to find largest subtree having identical left and right subtrees 863 19
Python program to find the given level order traversal of a binary tree, check if the tree is a min-heap 668 18
Python program to check if two trees are mirror 654 22
Python program to check if a given binary tree is sumtree 1079 27
Python program to find distance between two nodes of a binary search tree 1474 12
Python program to convert a binary tree into its mirror tree 915 17
Python program to find an element into AVL tree 3658 11
Python program to check if given preorder, inorder and postorder traversals are of same tree 980 18
Python program to check if leaf traversal of two binary trees is same? 707 20
Python program to check whether a binary tree is a full binary tree or not using recursion 1161 22
Python Program for Deletion into Avl 671 25
Python program to construct tree from given inorder and preorder traversals 1699 27
Python program to convert a binary search tree into a Min-Heap 898 13
Python program to convert ternary expression to a binary tree 903 13
* Python program to insert an element into AVL tree 13 12
Python program to find a pair with given sum in binary search tree 1096 27
Python program to diagonal sum of a binary tree 671 12
Python program to convert an arbitrary binary tree to a tree that holds children sum property 644 15
Python program to find an element into red black tree 1490 25