AVL TREE

 AVL TREE

 

The first type of self-balancing binary search tree to be invented is the AVL tree. The name AVL tree is coined after its inventor's names − Adelson-Velsky and Landis.

In AVL trees, the difference between the heights of left and right subtrees, known as the Balance Factor, must be at most one. Once the difference exceeds one, the tree automatically executes the balancing algorithm until the difference becomes one again.

In an AVL tree, the heights of the two sub-trees of a node may differ by at most one. Due to this  property, the AVL tree is also known as a height-balanced tree.

AVL trees are self-balancing, which means that the tree height is kept to a minimum so that a very fast runtime is guaranteed for searching, inserting and deleting nodes, with time complexity  O(log n).

In its structure, it stores an additional variable called the BalanceFactor. Thus, every node has a balance factor associated with it. 

The balance factor of a node is calculated by subtracting the height of its right sub-tree from the height of its left sub-tree. A binary search tree in which every node has a balance factor of –1, 0, or 1 is said to be height balanced. A node with any other balance factor is considered to be unbalanced and requires rebalancing of the tree.

Balance factor = Height (left sub-tree) – Height (right sub-tree)

• ·   If the balance factor of a node is 1, then it means that the left sub-tree of the tree is one level higher than that of the right sub-tree. Such a tree is therefore called as a left-heavy tree.
• ·  If the balance factor of a node is 0, then it means that the height of the left sub-tree (longest path in the left sub-tree) is equal to the height of the right sub-tree.(balanced AVL tree.
  )
• ·   If the balance factor of a node is –1, then it means that the left sub-tree of the tree is one level lower than that of the right sub-tree. Such a tree is therefore called as a right-heavy tree.

Look at Fig a Left-heavy AVL tree.  Note that the nodes 18, 39, 54, and 72 have no children, so their balance factor = 0. Node 27 has one left child and zero right child. So, the height of left sub-tree = 1, whereas the height of right sub-tree = 0. Thus, its balance factor = 1. Look at node 36, it has a left sub-tree with height = 2, whereas the height of right sub-tree = 1. Thus, its balance factor = 2 – 1 = 1. Similarly, the balance factor of node 45 = 3 – 2 =1; and node 63 has a balance factor of 0 (1 – 1).

Look at Fig b right-heavy AVL tree.  Note that the nodes 70,54,39, and 27 have no children, so their balance factor = 0. Node 72 has one left child and zero right child. So, the height of left sub-tree = 1, whereas the height of right sub-tree = 0. Thus, its balance factor = 1.

 Look at node 63 it has a left sub-tree with height = 1, whereas the height of right sub-tree = 2. Thus, its balance factor = 1 – 2 = -1. Similarly, the balance factor of node 45 = 2 – 3 = -1; and node 36 has a balance factor of 0 (1 – 1).

Look at Fig C. balanced AVL tree.

AVL Rotations

We perform rotation in AVL tree only in case if Balance Factor is other than -1, 0, and 1. There are basically four types of rotations which are as follows:

The Four "out-of-balance" Cases

When the balance factor of just one node is less than -1, or more than 1, the tree is regarded as out of balance, and a rotation is needed to restore balance.

There are four different ways an AVL Tree can be out of balance, and each of these cases require a different rotation operation.

Case	Description	Rotation to Restore Balance
Left-Left (LL)	The unbalanced node and its left child node are both left-heavy.	A single right rotation.
Right-Right (RR)	The unbalanced node and its right child node are both right-heavy.	A single left rotation.
Left-Right (LR)	The unbalanced node is left heavy, and its left child node is right heavy.	First do a left rotation on the left child node, then do a right rotation on the unbalanced node.
Right-Left (RL)	The unbalanced node is right heavy, and its right child node is left heavy.	First do a right rotation on the right child node, then do a left rotation on the unbalanced node.

The first two rotations LL and RR are single rotations and the next two rotations LR and RL are double rotations. For a tree to be unbalanced, minimum height must be at least 2, Let us understand each rotation

1. LL Rotation

When a node is added into the right subtree of the right subtree, if the tree gets out of balance, we do a single left rotation.

In above example, node A has balance factor -2 because a node C is inserted in the right subtree of A right subtree. We perform the LL rotation on the edge below A.

2. RR Rotation

If a node is added to the left subtree of the left subtree, the AVL tree may get out of balance, we do a single right rotation

In above example, node C has balance factor 2 because a node A is inserted in the left subtree of C left subtree. We perform the RR rotation on the edge below A.

Left-Right Rotation:

A left-right rotation is a combination in which first left rotation takes place after that right rotation executes.

1. Node B has been inserted into the right subtree of A the left subtree of C, because of which C has become an unbalanced node having balance factor 2. This case is L R rotation where: Inserted node is in the right subtree of left subtree of C
2. As LR rotation = LL+RR rotation, hence LL on subtree rooted at A is performed first. By doing LL rotation, node A, has become the left subtree of B.
3. After performing LL rotation, node C is still unbalanced, i.e., having balance factor 2, as inserted node A is in the left of left of C
4. Now we perform RR rotation on full tree, i.e. on node C. node C has now become the right subtree of node B, A is left subtree of B. 
5. Balance factor of each node is now either -1, 0, or 1, i.e. BST is balanced now.

Right-Left Rotation:

A right-left rotation is a combination in which first right rotation takes place after that left rotation executes.

1. Node B has been inserted into the left subtree of C the right subtree of A, because of which A has become an unbalanced node having balance factor - 2. This case is RL rotation where: Inserted node is in the left subtree of right subtree of A
2. As RL rotation = RR rotation + LL rotation, hence, RR on subtree rooted at C is performed first. By doing RR rotation, node C has become the right subtree of B.
3. After performing RR rotation, node A is still unbalanced, i.e. having balance factor -2, which is because of the right-subtree of the right-subtree node A.
4. Now we perform LL rotation on full tree, i.e. on node A. node C has now become the right subtree of node B, and node A has become the left subtree of B.
5. Balance factor of each node is now either -1, 0, or 1, i.e. BST is balanced now.

Advantages of AVL Tree:

AVL trees can self-balance themselves and therefore provides time complexity as O(Log n) for search, insert and delete.

It is a BST only (with balancing), so items can be traversed in sorted order.

Since the balancing rules are strict compared to Red Black Tree, AVL trees in general have relatively less height and hence the search is faster.

AVL tree is relatively less complex to understand and implement compared to Red Black Trees.

Disadvantages of AVL Tree:

It is difficult to implement compared to normal BST and easier compared to Red Black

Less used compared to Red-Black trees.

Due to its rather strict balance, AVL trees provide complicated insertion and removal operations as more rotations are performed.

Applications of AVL Tree:

AVL Tree is used as a first example self balancing BST in teaching DSA as it is easier to understand and implement compared to Red Black

Applications, where insertions and deletions are less common but frequent data lookups along with other operations of BST like sorted traversal, floor, ceil, min and max.

Red Black tree is more commonly implemented in language libraries like map in C++, set in C++, TreeMap in Java and TreeSet in Java.

AVL Trees can be used in a real time environment where predictable and consistent performance is required.

Operations on an AVL Tree

The following operations are performed on AVL tree...

Search

Insertion

Deletion

Search Operation in AVL Tree

In an AVL tree, the search operation is performed with O(log n) time complexity. The search operation in the AVL tree is similar to the search operation in a Binary search tree. We use the following steps to search an element in AVL tree...

 

Step 1 - Read the search element from the user.

Step 2 - Compare the search element with the value of root node in the tree.

Step 3 - If both are matched, then display "Given node is found!!!" and terminate the function

Step 4 - If both are not matched, then check whether search element is smaller or larger than that node value.

Step 5 - If search element is smaller, then continue the search process in left subtree.

Step 6 - If search element is larger, then continue the search process in right subtree.

Step 7 - Repeat the same until we find the exact element or until the search element is compared with the leaf node.

Step 8 - If we reach to the node having the value equal to the search value, then display "Element is found" and terminate the function.

Step 9 - If we reach to the leaf node and if it is also not matched with the search element, then display "Element is not found" and terminate the function.

Insertion Operation in AVL Tree

In an AVL tree, the insertion operation is performed with O(log n) time complexity. In AVL Tree, a new node is always inserted as a leaf node. The insertion operation is performed as follows...

 

Step 1 - Insert the new element into the tree using Binary Search Tree insertion logic.

Step 2 - After insertion, check the Balance Factor of every node.

Step 3 - If the Balance Factor of every node is 0 or 1 or -1 then go for next operation.

Step 4 - If the Balance Factor of any node is other than 0 or 1 or -1 then that tree is said to be imbalanced. In this case, perform suitable Rotation to make it balanced and go for next operation.

Deletion Operation in AVL Tree

The deletion operation in AVL Tree is similar to deletion operation in BST. But after every deletion operation, we need to check with the Balance Factor condition. If the tree is balanced after deletion go for next operation otherwise perform suitable rotation to make the tree Balanced.

Example: Construct an AVL Tree by inserting numbers from 1 to 8.

Step-by-Step Construction of the AVL Tree for the given Sequence 21, 26, 30, 9, 4, 14, 28, 18,15,10, 2, 3, 7

Construct an AVL tree having the following elements:  

H, I, J, B, A, E, C, F, D, G, K, L

1.      Insert H, I, J

 

On inserting the above elements, especially in the case of H, the BST becomes unbalanced as the Balance Factor of H is -2. Since the BST is right-skewed, we will perform LL Rotation on node H.

Binary Search Trees(BST)

 Binary Search Trees (BST):

A binary search tree, also known as an ordered binary tree. In a binary search tree, all the nodes in the left sub-tree have a value less than that of the root node. Correspondingly, all the nodes in the right sub-tree have a value either equal to or greater than the root node. The same rule is applicable to every sub-tree in the tree.

In the above figure, we can observe that the root node is 40, and all the nodes of the left subtree are smaller than the root node, and all the nodes of the right subtree are greater than the root node.

Similarly, we can see the left child of root node is greater than its left child and smaller than its right child. So, it also satisfies the property of binary search tree. Therefore, we can say that the tree in the above image is a binary search tree.

In the above tree, the value of root node is 40, which is greater than its left child 30 but smaller than right child of 30, i.e., 55. So, the above tree does not satisfy the property of Binary search tree. Therefore, the above tree is not a binary search tree.

Example of creating a binary search tree

Example : State whether the binary trees in below Fig. are binary search trees or not.

Example : Now, let's see the creation of binary search tree using an example.

Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50

• First, we have to insert 45 into the tree as the root of the tree.
• Then, read the next element; if it is smaller than the root node, insert it as the root of the left subtree, and move to the next element.
• Otherwise, if the element is larger than the root node, then insert it as the root of the right subtree.

Now, let's see the process of creating the Binary search tree using the given data element. The process of creating the BST is shown below 

Example : Create a binary search tree using the following data elements: 45, 39, 56, 12, 34, 78, 32, 10, 89, 54, 67, 81

OPERATIONS ON BINARY SEARCH TREES

Searching for a Node in a Binary Search Tree:

The search function is used to find whether a given value is present in the tree or not. The searching process begins at the root node. 

The function first checks if the binary search tree is empty. If it is empty, then the value we are searching for is not present in the tree. So, the search algorithm terminates by displaying an appropriate message. 

However, if there are nodes in the tree, then the search function checks to see if the key value of the current node is equal to the value to be searched.

If not, it checks if the value to be searched for is less than the value of the current node, in which case it should be recursively called on the left child node. 

In case the value is greater than the value of the current node, it should be recursively called on the right child node.

See the illustration below for a better understanding:

Algorithm to search for a given value in a binary search tree

Insert a value in a Binary Search Tree:

A new key is always inserted at the leaf by maintaining the property of the binary search tree. We start searching for a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node. The below steps are followed while we try to insert a node into a binary search tree:

 

v  Initilize the current node (say, currNode or node) with root node

v  Compare the key with the current node.

v  Move left if the key is less than or equal to the current node value.

v  Move right if the key is greater than current node value.

v  Repeat steps 2 and 3 until you reach a leaf node.

v  Attach the new key as a left or right child based on the comparison with the leaf node’s value.

Follow the below illustration for a better understanding:

Algorithm to insert a given value in a binary search tree

Deleting a Node from a Binary Search Tree:

Delete function is used to delete the specified node from a binary search tree. However, we must delete a node from a binary search tree so that the property of the binary search tree doesn't violate. There are three situations in which a node can be deleted from a binary search tree.

Case 1: Deleting a Node that has No Children

It is the simplest case, in this case, replace the leaf node with the NULL and simple free the allocated space.

In the following image, we are deleting the node 85, since the node is a leaf node, therefore the node will be replaced with NULL and allocated space will be freed.

Case 2: Deleting a Node with One Child

In this case, the node’s child is set as the child of the node’s parent (i.e replace the node with its child).

if the node is the left child of its parent, the node’s child becomes the left child of the node’s parent. Correspondingly, if the node is the right child of its parent, the node’s child becomes the right child of the node’s parent.

In the following image, the node 12 is to be deleted. It has only one child. The node will be replaced with its child node and the replaced node 12 (which is now leaf node) will simply be deleted.

Case 3: Deleting a Node with Two Children

this case, replace the node’s value with its in-order predecessor (largest value in the left sub-tree) or in-order successor (smallest value in the right sub-tree).

Deleting node 56 from the given binary search tree  by replacing node 56 with its in-order predecessor

This deletion could also be handled by replacing node 56 with its in-order successor

ex: In the following image, the node 50 is to be deleted which is the root node of the tree. 

The in-order traversal of the tree given below 6, 25, 30, 50, 52, 60, 70, 75.

replace 50 with its in-order successor 52. Now, 50 will be moved to the leaf of the tree, which will simply be deleted.

Delete (TREE, ITEM)

o         Step 1: IF TREE = NULL

   Write "item not found in the tree" ELSE IF ITEM < TREE -> DATA

  Delete(TREE->LEFT, ITEM)

  ELSE IF ITEM > TREE -> DATA

   Delete(TREE -> RIGHT, ITEM)

  ELSE IF TREE -> LEFT AND TREE -> RIGHT

  SET TEMP = findLargestNode(TREE -> LEFT)

  SET TREE -> DATA = TEMP -> DATA

   Delete(TREE -> LEFT, TEMP -> DATA)

                 ELSE

   SET TEMP = TREE

   IF TREE -> LEFT = NULL AND TREE -> RIGHT = NULL

   SET TREE = NULL

  ELSE IF TREE -> LEFT != NULL

  SET TREE = TREE -> LEFT

  ELSE

    SET TREE = TREE -> RIGHT

  [END OF IF]

  FREE TEMP

[END OF IF]

o             Step 2: END

EXPRESSION TREE

 EXPRESSION TREE:

Expression Trees

Binary trees are widely used to store algebraic expressions. For example,

consider the algebraic expression given as:

The expression tree is a tree used to represent the various expressions. The tree data structure is used to represent the expressional statements. In this tree, the internal node always denotes the operators.

• The leaf nodes always denote the operands.
• The operations are always performed on these operands.
• The operator present in the depth of the tree is always at the highest priority.i.e least priority operator will on top.
• The operator, which is not much at the depth in the tree, is always at the lowest priority compared to the operators lying at the depth.
• The operand will always present at a depth of the tree; hence it is considered the highest priority among all the operators.

Associativity for operators

• ʌ (power)                                           : Right to Left
• * (multiplication), / (Divison)            :Left to Right
• - (sub), +(Add)                                   : Left to Right

Ex:  Exp = (a – b) + (c * d)

Ex: Given an expression, Exp = ((a + b) – (c * d)) % ((e ^f) / (g – h)), construct the corresponding binary tree.

Ex: Given the binary tree, write down the expression that it represents.

Expression for the above binary tree is 

                 [{(a/b) + (c*d)} ^ {(f % g)/(h – i)}]

solve the expression  a*b /c + e/f  * g + k - x * y