Introduction to AVL Tree Python
A balanced binary tree is an example of an Adelson-Velskii and Landis (AVL) tree, which is a kind of tree that may be created in Python. There is a possibility that the AVL tree is a self-balancing binary search tree. If this is the case, then each node in the tree maintains a balance problem, which may take on the values -1, 0, or 1. The balancing problem of a given node in an AVL tree may be thought of as the difference in height that exists between a node’s left and right subtrees. (Height of Left Subtree minus Height of Right Subtree) (Height of Right Subtree – Height of Left Subtree).
Syntax or Algorithm
Since this is a data structure idea, we do not have a specific syntax; instead, we will follow certain rules or steps that will be supplied as an algorithm for locating or adding or removing any member in this AVL tree. Such rules and processes will be given below. Hence, let us examine the procedures for adding new elements and removing existing ones in the AVL tree, which are as follows:
Insertion:
-
Step 1:
initial, use BST’s (Binary Search Tree) insertion logic to feature a replacement member to the tree. -
Step 2:
once you’ve got inserted all of the components, you will need to visualize every node’s Balance issue. -
Step 3:
once the Balance issue of every node is discovered to be zero or one or -1, the algorithmic program moves on to a successive step. -
Step 4:
If any node’s balance issue isn’t one in every one of the 3 values listed higher than, the tree is taken into account to be unbalanced. The algorithmic program can then proceed to successive operation once performing arts the suitable Rotation to form it balanced.
Deletion:
-
Step 1:
find the node wherever k is held on. -
Step 2:
at the moment, erase the node’s contents (Suppose the node is x) -
Step 3:
create a claim: Delete a leaf to lower the scale of a node in the Associate in Nursing AVL tree. There are a unit 3 eventualities that might occur: - Delete x once it’s no youngsters.
- Let x’ become child the child} of x once x has one kid.
- Because T subtrees will solely take issue tall by one, x’ cannot have a child:
- then take away x’ and replace the contents of x with the contents of x’ (a leaf)
-
Step 4:
If x has 2 youngsters, find x’s successor, z (who doesn’t have a left child), replace x’s contents with z’s contents, and take away z.
How to Implement the AVL Tree in Python?
In Python, an AVL tree is referred to as a self-balancing tree. This kind of tree makes use of a balance factor, the value of which may be -1, 0, or +1, and it has four distinct operations. An explanation of this type of tree can be found below: The equation for calculating the balance factor for an AVL tree is as follows: Balance Factor = (Height of Left Subtree – Height of Right Subtree) or (height of Right Subtree – Height of Left Subtree)
The following are some of the operations that may be performed on the AVL tree in addition to the other trees:
1. Rotation to the Left (LL)
After we have rotated to the left around node x, node y will take its place as the root of the new subtree. Because of this, node x will now be the left child of node y, while subtree b will be the right child of node x.
2. Right Rotation (RR)
Whenever we do a right rotation with respect to node y, node x will replace node y as the parent of the subtree. Subtree b is promoted to the position of left child of node y, while node y is elevated to the position of right child of subtree b.
3. Left Right Rotation (LR Rotation)
According to what the name suggests, this kind of rotation consists of both a left rotation and a right rotation.
4. Right Left Rotation (RL Rotation)
A rotation of this kind involves first rotating to the right, and then rotating to the left.
Examples of AVL Tree Python
In the following example, we will write Python code to demonstrate both the insertion and deletion of nodes in an AVL tree. Code:
import sys Output:
class treeroot(object):
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
class avl(object):
def insrtnode(self, root, key):
if not root:
return treeroot(key)
elif key < root.key: root.left = self.insrtnode(root.left, key) else: root.right = self.insrtnode(root.right, key) root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right)) balanceFactor = self.getBalance(root) if balanceFactor > 1:
if key < root.left.key:
return self.RR(root)
else:
root.left = self.LR(root.left)
return self.RR(root)
if balanceFactor < -1: if key > root.right.key:
return self.LR(root)
else:
root.right = self.RR(root.right)
return self.LR(root)
return root
def delnode(self, root, key):
if not root:
return root
elif key < root.key: root.left = self.delnode(root.left, key) elif key > root.key:
root.right = self.delnode(root.right, key)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = self.getMinValueNode(root.right)
root.key = temp.key
root.right = self.delnode(root.right,
temp.key)
if root is None:
return root
root.height = 1 + max(self.getHeight(root.left),
self.getHeight(root.right))
bf = self.getBalance(root)
if bf > 1:
if self.getBalance(root.left) >= 0:
return self.RR(root)
else:
root.left = self.LR(root.left)
return self.RR(root)
if bf < -1:
if self.getBalance(root.right) <= 0:
return self.LR(root)
else:
root.right = self.RR(root.right)
return self.LR(root)
return root
def LR(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
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 y
def RR(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
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 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 getMinValueNode(self, root):
if root is None or root.left is None:
return root
return self.getMinValueNode(root.left)
def preOrder(self, root):
if not root:
return
print("{0} ".format(root.key), end="")
self.preOrder(root.left)
self.preOrder(root.right)
def printHelper(self, currPtr, indent, last):
if currPtr != None:
sys.stdout.write(indent)
if last:
sys.stdout.write("R----")
indent += " "
else:
sys.stdout.write("L----")
indent += "| "
print(currPtr.key)
self.printHelper(currPtr.left, indent, False)
self.printHelper(currPtr.right, indent, True)
myTree = avl()
root = None
nums = [95, 45, 27, 19, 71, 10, 68, 34]
for num in nums:
root = myTree.insrtnode(root, num)
print("After insertion: ")
myTree.printHelper(root, "", True)
key = 45
root = myTree.delnode(root, key)
print("After Deletion: ")
myTree.printHelper(root, "", True)
In the example that was just shown, we can see that we have written code on adding and removing the members in the AVL tree, and that in order to implement this in Python, we first imported the sys file. After that, we went ahead and created the classes treeroot and AVL. In treeroot, we are just using it to describe the key, left, and right factors, and even the height factor, so that we may use it in subsequent balancing factor and other rotation operation. We are specifying how to insert and remove using distinct functions in the AVL class, and the main function is the place where these methods are invoked. The result looks exactly like the screenshot that was displayed before.