Table of contents
- What is AVL tree?
- Common operations on AVL tree
- Insert a node in AVL (Left Left condition)
- Insert a node in AVL (Left Right condition)
- Insert a node in AVL (Right Right condition)
- Insert a node in AVL (Right Left condition)
- Insert a node in AVL (All together)
- Insert a node in AVL (method)
- Delete a node from AVL (method)
- Delete entire AVL
- Time Space complexity of AVL tree
- End
What is AVL tree?
An AVL tree is a self-balancing binary search tree (BST) where the difference between heights of left and right subtree cannot be more that one for all nodes.
AVL tree is also a type of binary tree. Hence, all properties of binary tree are applicable in the case of AVL tree too! But an AVL tree must be balanced. AVL tree keep a binary search tree balanced. AVL tree boosts performance, specially time complexity.
If at any time heights of left and right subtrees differ by more than one, the rebalancing is done to restore AVL property, this process is called rotation.
Balanced binary tree:
Not balanced:
*diff 2 means imbalanced
*last leaf is balanced, so while counting last leaf is excluded.
Common operations on AVL tree
Creation and traversal is same as binary tree structure.
Full explanation: Binary tree DSA
import QueueLinkedList as queue
class AVLNode:
self.data = data
self.leftChild = None
self.rightChild = None
self.height = 1
def preOrderTraversal(rootNode): #O(N)
if not rootNode:
return
print(rootNode)
preOrderTraversal(rootNode.leftChild)
preOrderTraversal(rootNode.rightChild)
def inOrderTraversal(rootNode): #O(N)
if not rootNode: #O(1)
return
inOrderTraversal(rootNode.leftChild) #O(N/2)
print(rootNode.data) #O(1)
inOrderTraversal(rootNode.rightChild) #O(N/2)
def postOrderTraversal(rootNode): #O(N)
if not rootNode: #O(1)
return
postOrderTraversal(rootNode.leftChild) #O(N/2)
postOrderTraversal(rootNode.rightChild) #O(N/2)
print(rootNode.data) #O(1)
def levelOrderTraversal(rootNode): #O(N)
if not rootNode: #checking the rootnode #O(1)
return
else:
customQueue = queue.Queue() #O(1)
customQueue.enqueue(rootNode) #O(1)
while not (customQueue.isEmpty()): #O(n)
root = customQueue.dequeue() #O(1)
print(root.value.data)
if (root.value.leftChild is not None): #O(1)
customQueue.enqueue(root.value.leftChild)
if (root.value.leftChild is not None): #O(1)
customQueue.enqueue(root.value.rightChild)
def searchNode(rootNode, nodeValue):
if rootNode.data == nodeValue: #O(1)
print("The value is found")
elif nodeValue < rootNode.data: #O(1)
if rootNode.leftChild.data == nodeValue:
print("The value is found")
else: #O(N/2)
searchNode(rootNode.leftChild, nodeValue)
else:
if rootNode.rightChild.data == nodeValue: #O(1)
print("The value is found")
else: #O(N/2)
searchNode(rootNode.rightChild, nodeValue)
newAVL = AVLNode(10)
Insertion:
Case 1: Rotation is not required (follows binary insertion process)
Case 2: Rotation is required (LL, RL, LR, RR)
Insert a node in AVL (Left Left condition)
You will find every node in left-left position whether looking for a node or, inserting a node - position will be always in the left side.
Steps:
Find the disbalanced node
Search for a grandchild of disbalanced node which causes disbalance.
In case of Left-Left condition, the right rotation is required.
This rotation solves the problem of disbalance. In right notation, the disbalanced root node goes down, and the left subtrees goes up.
In case of selecting grand child, we will select the one which's height is more.
Algorithm of Left Left (LL) Condition:
rotateRight(disbalancedNode):
newRoot = disbalancedNode.leftChild
disbalancedNode.leftChild = disbalancedNode.leftChild.rightChild
newRoot.rightChild = disbalancedNode
# update height of disbalancedNode and newRoot
return newRoot
Time complexity: O(1), Space complexity: O(1)
Insert a node in AVL (Left Right condition)
As the name suggest, we will first do a left rotation than a right rotation. When we do the left rotation, we move right child to the place of its parent and the parent moved to the left child of the moved node.
When we do the right rotation, the parent node becomes the right child of its left child.
Algorithm :
rotateLeft(disbalancedNode):
newRoot = disbalancedNode.rightChild
disbalancedNode.rightChild = disbalancedNode.rightChild.leftChild
newRoot.leftChild = disbalancedNode
#update height of disbalancedNode and newRoot
return newRoot
rotateRight(disbalancedNode):
newRoot = disbalancedNode.leftChild
disbalancedNode.leftChild = disbalancedNode.leftChild.rightChild
newRoot.rightChild = disbalancedNode
#update height of disbalancedNode and newRoot
return newRoot
Time complexity: O(1), Space complexity: O(1)
Insert a node in AVL (Right Right condition)
As the name implies, it's the opposite of Left-Left condition.
Whenever we see a right right condition, to make it balanced we need to do left rotation.
Algorithm:
rotateLeft(disbalancedNode):
newRoot = disbalancedNode.rightChild
disbalancedNode.rightChild = disbalancedNode.rightChild.leftChild
newRoot.leftChild = disbalancedNode
# update height of disbalancedNode and newRoot
return newRoot
Time complexity: O(1), Space complexity: O(1)
Insert a node in AVL (Right Left condition)
First we'll do right rotation, then we'll do left rotation.
Now we will perform right rotation.
Algorithm:
rotateRight(disbalancedNode):
newRoot = disbalancedNode.leftChild
disbalancedNode.leftChild = disbalancedNode.leftChild.rightChild
newRoot.rightChild = disbalancedNode
#update height of disbalancedNode and newRoot
return newRoot
rotateLeft(disbalancedNode):
newRoot = disbalancedNode.rightChild
disbalancedNode.rightChild = disbalancedNode.rightChild.leftChild
newRoot.leftChild = disbalancedNode
#update height of disbalancedNode and newRoot
return newRoot
Insert a node in AVL (All together)
Putting all together, supposes you have given a list 30, 25, 35, 20, 15, 5, 10, 50, 60, 70, 65 and you have to make an AVL out of it. The rule is, you take the first value as root node and gradually place the other values. You're gonna put it left or right based on their values. And, don't forget to check balance each and every time
Insert a node in AVL (method)
Now we will see the code implement. We know, for insertion we need a helper function. Then, we'll need another function for right rotation.
import QueueLinkedList as queue
class AVLNode:
self.data = data
self.leftChild = None
self.rightChild = None
self.height = 1
def preOrderTraversal(rootNode): #O(N)
if not rootNode:
return
print(rootNode)
preOrderTraversal(rootNode.leftChild)
preOrderTraversal(rootNode.rightChild)
def inOrderTraversal(rootNode): #O(N)
if not rootNode: #O(1)
return
inOrderTraversal(rootNode.leftChild) #O(N/2)
print(rootNode.data) #O(1)
inOrderTraversal(rootNode.rightChild) #O(N/2)
def postOrderTraversal(rootNode): #O(N)
if not rootNode: #O(1)
return
postOrderTraversal(rootNode.leftChild) #O(N/2)
postOrderTraversal(rootNode.rightChild) #O(N/2)
print(rootNode.data) #O(1)
def levelOrderTraversal(rootNode): #O(N)
if not rootNode: #checking the rootnode #O(1)
return
else:
customQueue = queue.Queue() #O(1)
customQueue.enqueue(rootNode) #O(1)
while not (customQueue.isEmpty()): #O(n)
root = customQueue.dequeue() #O(1)
print(root.value.data)
if (root.value.leftChild is not None): #O(1)
customQueue.enqueue(root.value.leftChild)
if (root.value.leftChild is not None): #O(1)
customQueue.enqueue(root.value.rightChild)
def searchNode(rootNode, nodeValue):
if rootNode.data == nodeValue: #O(1)
print("The value is found")
elif nodeValue < rootNode.data: #O(1)
if rootNode.leftChild.data == nodeValue:
print("The value is found")
else: #O(N/2)
searchNode(rootNode.leftChild, nodeValue)
else:
if rootNode.rightChild.data == nodeValue: #O(1)
print("The value is found")
else: #O(N/2)
searchNode(rootNode.rightChild, nodeValue)
#helper function
def getHeight(rootNode):
if not rootNode:
return 0
return rootNode.height
#right roation function
def rightRotate(disbalanceNode) :
newRoot = disbalanceNode.leftChild
disbalanceNode.leftChild = disbalanceNode.leftChild.rightChild
newRoot.rightChild = disbalanceNode
disbalanceNode.height = 1+ max(getHeight(disbalanceNode, leftChild), getHeight(disbalanceNode, rightChild))
newRoot.height = 1+ max(getHeight(newRoot, leftChild), getHeight(newRoot, rightChild))
return newRoot
def leftRotate(disbalanceNode):
newRoot = disbalanceNode.rightChild
disbalanceNode.rightChild = disbalanceNode.rightChild.leftChild
newRoot.leftChild = disbalanceNode
disbalanceNode.height = 1+ max(getHeight(disbalanceNode, leftChild), getHeight(disbalanceNode, rightChild))
newRoot.height = 1+ max(getHeight(newRoot, leftChild), getHeight(newRoot, rightChild))
return newRoot
def getBalance(rootNode): #o(1)
if not rootNode:
return 0
return getHeigh(rootNode.leftChild) - getHeight(rootNode.rightChild)
# insert method
def insertNode(rootNode, nodeValue):
if not rootNode:
return AVLNode(nodeValue)
elif nodeValue < rootNode.data:
rootNode.leftChild = insertNode(rootNode.leftChild, nodeValue)
else:
rootNode.rightChild = insertNode(rootNode.rightChild, nodeValue)
rootNode.height = 1+ max(getHeight(rootNode, leftChild), getHeight(rootNode, rightChild))
balance = getBalance(rootNode)
if balance > 1 and nodeValue < rootNode.leftChild.data: #LL condition
return rightRotate(rootNode)
if balance > 1 and nodeValue > rootNode.leftChild.data: #LR condition
rootNode.leftChild = leftRotate(rootNode.leftChild)
return rightRotate(rootNode)
if balance < -1 and nodeValue > rootNode.rightChild.data: #RR coldition
return leftRotate(rootNode)
if balance < -1 and nodeValue < rootNode.rightChild.data: #RL condition
rootNode.rightChild = rightRotate(rootNode.rightChild)
leftRotate(rootNode)
return rootNode
newAVL = AVLNode(10)
newAVL = insertNode(newAVL, 10)
newAVL = insertNode(newAVL, 20)
newAVL = insertNode(newAVL, 30)
levelOrderTraversal(newAVL)
Time and Space complexity: O(log N)
Delete a node from AVL (method)
Before deleting our method, we need to create a helper function.
continuing..
def getMinValueNode(rootNode):
if rootNode is None or rootNode.leftChild is None:
return rootNode
return getMinValueNode(rootNode, leftChild)
def deleteNode(rootNode, nodeValue):
if not rootNode:
return rootNode
elif nodeValue < rootNode.data:
rootNode.leftChild = deleteNode(rootNode.leftChild, nodeValue)
elif nodeValue > rootNode.data:
rootNode.rightChild = deleteNode(rootNode.rightChild, nodeValue)
else:
if rootNode.leftChild is None:
temp = rootNode.rightChild
rootNode = None
return temp
elif rootNode.rightChild is None:
temp = rootNode.leftChild
rootNode = None
return temp
temp = getMinValueNode(rootNode.rightChild)
rootNode.data = temp.data
rootNode.rightChild = deleteNode(rootNode.rightChild, temp.data)
balance = getBalance(rootNode)
if balance > 1 and getBalance(rootNode.leftChild) >= 0: #LL condition
return rightRotate(rootNode)
if balance < -1 and getBalance(rootNode.rightChild) <= 0: #RR condition
return leftRotate(rootNode)
if balance > 1 and getBalance(rootNode.leftChild) < 0) : #LR condition
rootNode.leftChild = leftRotate(rootNode.leftChild)
return rightRotate(rootNode)
if balance < -1 and getBalance(rootNode.rightChild) > 0) : #RL condition
rootNode.rightChild = rightRotate(rootNode.rightChild)
return leftRotate(rootNode)
return rootNode
newAVL = AVLNode(5)
newAVL = insertNode(newAVL, 10)
newAVL = insertNode(newAVL, 15)
newAVL = insertNode(newAVL, 20)
newAVL = deleteNode(newAVL, 15)
levelOrderTraversal(newAVL)
Time and Space complexity: O(log N)
Delete entire AVL
under the previous code....
def deleteAVL(rootNode):
rootNode.data = None
rootNode.leftChild = None
rootNode.rightChild = None
return "The AVL has been successfully deleted"
newAVL = AVLNode(5)
newAVL = insertNode(newAVL, 10)
newAVL = insertNode(newAVL, 15)
newAVL = insertNode(newAVL, 20)
deleteAVL(newAVL)
levelOrderTraversal(newAVL)
Time and Space complexity: O(1)
Time Space complexity of AVL tree
Time complexity | Space complexity | |
Create AVL | O(1) | O(1) |
Insert a node AVL | O(logN) | O(logN) |
Traverse AVL | O(n) | O(n) |
Search for a node AVL | O(logN) | O(logN) |
Delete node from AVL | O(logN) | O(logN) |
Delete entire AVL | O(1) | O(1) |