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.
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
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
Comments