AVL trees are binary search trees in which the node of the tree follows a unique property. It was the first data structure of its kind. In a BST, the tree is subdivided into two sub-trees as left side and right side subtrees. The height difference between the left side sub-tree of any node and the right side sub-tree of any node is either less than or equal to 1 in the AVL tree. Let us know about that the Algorithms AVL Trees.
Adelson, Velski, and Lendis discovered the technique for creating such a node representation of binary search trees, hence the name AVL trees.
AVL trees require a factor of 1 to get balanced. It also gets known as a Balance binary tree because of its unique attribute of keeping the difference equal to or less than 1.
Balance Factor (k) = height (left(k)) – height (right(k))
Need Of The AVL Trees
the performance of the BST is got limited to not letting the height of the tree get skewed and that is because of O(n), AVL allows the tree to get skewed. where it was needed of the BST to perform as linear search algorithms i.e. (worst case scenario).
This brings us to the answer of the need arises to balance out the binary search tree.
AVL Tree Operations
the performance of the BST is limited to not letting the height of the tree get skewed, and that is because of O(n), AVL allows the tree to get skewed. Where it got needed of the BST to perform as linear search algorithms, i.e. (worst case scenario). It brings us to the answer of the need arises to balance out the binary search tree.
Algorithm for various AVL insert operations
Step 1: First, use BST’s (Binary Search Tree) insertion logic to add a new member to the tree.
Step 2: After you’ve inserted all of the parts, you’ll need to check each node’s Balance Factor.
Step 3: The method advances to the next stage when the Balance Factor of each node is discovered to be 0 or 1 or -1.
Step 4: If any node’s balance factor is not one of the three values listed above, the tree is considered to be unbalanced. The algorithm will then proceed to the next operation after performing the appropriate rotation to make it balanced.
Algorithm for various AVL delete operations
Step 1: Locate the node where k is stored.
Step 2: After that, erase the node’s contents (Suppose the node is x)
Step 3: Claim: In an AVL tree, eliminating a leaf can lower the size of a node. Three scenarios could occur:
Case 1 Delete x when it has no children.
Case 2 Let x’ become the kid of x when x has one child.
Because T subtrees can only differ in height by one, x’ cannot have a child:
then remove x’ and replace the contents of x with the contents of x’ (a leaf)
case 3: If x has two children,
locate x’s successor, z (who does not have a left child),
replace x’s contents with z’s contents, and
remove z.
You will have to remove a leaf in each of the three scenarios.
Rotations In The AVL
We rotate the AVL tree only when the Balance Factor is more significant than -1, 0, or 1. Rotations can be divided into four categories, as follows:
The first two rotations below are single rotations, whereas the next two are double rotations.
L L rotation
When BST becomes unbalanced as a result of a node being added into the left subtree of C, we apply LL rotation, which is a clockwise rotation applied to the edge below a node with a balance factor of 2. Because node A is added in the left subtree of C’s left subtree, node C has a balance factor of 2. On the edge below A, we conduct the LL rotation.
R R rotation
When BST becomes unbalanced as a result of a node being added into the right subtree of A’s right subtree, we apply RR rotation, which is an anticlockwise rotation applied to the edge below a node with a balance factor of -2. Because node C is added in the right subtree of A right subtree, node A has a balancing factor of -2. On the edge below A, we conduct the RR rotation.
L R rotation
Double rotations are a more complicated variation of previously explained rotations. Take note of each action performed during rotation to better comprehend them. First, let’s look at how to perform a Left-Right rotation. A combination of left and right rotations is known as a left-right rotation.
R L rotation
LL rotation + RR rotation, i.e., first LL rotation on subtree, then RR rotation on the whole tree, where full tree refers to the first node from the route of the inserted node whose balancing factor is not -1, 0, or 1.
Conclusion
AVL is by default a BST, which makes it mandatory to follow the BST properties, i.e., each node of the tree has a key and an associated value to the key. One can easily distinguish AVL trees mentioned above by counting the keys over the left and right sides of the tree based on their unique property of balance factor.
Frequently Asked Questions
1) Is it possible to construct an AVL tree without rotating it?
Both yes and no. Because of the number of different keys that may be packed into a node, B-trees can be added with more keys or some of the keys can be deleted as per required details.
2) What is the AVL tree’s height?
If the AVL tree has n nodes, the least height is Floor (log2 (n + 1)). The maximum height of an AVL tree with n nodes cannot exceed 1.44*log2n. If the AVL tree’s height is h, the maximum size of the network is 2h+1 – 1.
