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 :
Before we get started, I want to mention that Balance Factor
of a balanced node should be always {-1,0,1}
BalanceFactor=height(left sub-tree)-height(right sub-tree)
Insertion implementation in python from geeksforgeeks
"""
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
References and useful resources
- https://www.programiz.com/dsa/avl-tree
- 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.youtube.com/watch?v=_8qqlVH5NC0
#day_20
Happy coding!
Top comments (0)