Home » Binary Search tree vs AVL tree

Binary Search tree vs AVL tree

by Online Tutorials Library

Binary Search tree vs AVL tree

Before knowing about the Binary search tree and AVL tree differences, we should know about the binary search tree and AVL tree separately.

What is a Binary Search Tree?

The binary search tree is a tree data structure that follows the condition of the binary tree. As we know, that tree can have ‘n’ number of children, whereas; the binary tree can contain the utmost two children. So, the constraint of a binary tree is also followed by the binary search tree. Each node in a binary search tree should have the utmost two children; in other words, we can say that the binary search tree is a variant of the binary tree.

The binary search tree also follows the properties of the binary search. In binary search, all the elements in an array must be in sorted order. We calculate the middle element in the binary search in which the left part of the middle element contains the value lesser than the middle value, and the right part of the middle element contains the values greater than the middle value.

In Binary Search Tree, the middle element becomes the root node, the right part becomes the right subtree, and the left part becomes the left subtree. Therefore, we can say that the binary search tree is a combination of a binary tree and binary search.

Note: Binary Search Tree can be defined as the binary tree in which all the elements of the left subtree are less than the root node, and all the elements of the right subtree are greater than the root node.

Time Complexity in Binary Search Tree

If the binary search tree is almost a balanced tree then all the operations will have a time complexity of O(logn) because the search is divided either to the left or the right subtree.

If the binary search tree is either left or right-skewed, then all the operations will have the time complexity of O(n) because we need to traverse till the n elements.

What is the AVL Tree?

An AVL tree is a self-balancing binary search tree where the difference between heights of left and right subtrees cannot be more than one. This difference is known as a balance factor. In the AVL tree, the values of balance factor could be either -1, 0 or 1.

How does the self-balancing of the binary search tree happen?

As we know that AVL tree is a self-balancing binary search tree. If the binary search tree is not balanced, it can be self-balanced with some re-arrangements. These re-arrangements can be done using some rotations.

Let’s understand self-balancing through an example.

Suppose we want to insert 10, 20, 30 in an AVL tree.

The following are the ways of inserting 10, 20, 30 in an AVL tree:

  • If the order of insertion is 30, 20, 10.

Step 1: First, we create a Binary search tree, as shown below:

Binary Search tree vs AVL tree

Step 2: In the above figure, we can observe that tree is unbalanced because the balance factor of node 30 is 2. In order to make it an AVL tree, we need to perform some rotations. If we perform the right rotation on node 20 then the node 30 will move downwards, whereas the node 20 will move upwards, as shown below:

Binary Search tree vs AVL tree

As we can observe, the final tree follows the property of the Binary Search tree and a balanced tree; therefore, it is an AVL tree.

In the case, the tree was left unbalanced tree, so we perform the right rotation on the node.

  • If the order of insertion is 10, 20, 30.

Step 1: First we create a Binary search tree as shown below:

Binary Search tree vs AVL tree

Step 2: In the above figure, we can observe that the tree is unbalanced because the balance factor of node 10 is -2. In order to make it an AVL tree, we need to perform some rotations. It is a right unbalanced tree, so we will perform left rotation. If we perform left rotation on node 20, then the node 20 will move upwards, and node 10 will move downwards, as shown below:

Binary Search tree vs AVL tree

As we can observe, the final tree follows the property of the Binary Search tree and a balanced tree; therefore, it is an AVL tree.

  • If the order of insertion is 30, 10, 20

Step 1: First we create the Binary Search tree as shown below:

Binary Search tree vs AVL tree

Step 2: In the above figure, we can observe that the tree is unbalanced because the balance factor of the root node is 2. In order to make it an AVL tree, we need to perform some rotations. The above scenario is left-right unbalanced as one node is the left of its parent node and another is the right of its parent node. First, we will perform the left rotation, and rotation happens between nodes 10 and 20. After left rotation, 20 will move upwards, and 10 will move downwards as shown below:

Binary Search tree vs AVL tree

Still, the tree is unbalanced, so we perform the right rotation on the tree. Once the right rotation is performed on the tree, then the tree would like, as shown below:

Binary Search tree vs AVL tree

As we can observe in the above tree, the tree follows the property of the Binary Search tree and a balanced tree; therefore, it is an AVL tree.

  • If the order of the insertion is 10, 30, 20

Step 1: First, we create the Binary Search tree, as shown below:

Binary Search tree vs AVL tree

Step 2: In the above figure, we can observe that tree is unbalanced because the balance factor of the root node is 2. In order to make it an AVL tree, we need to perform some rotations. The above scenario is right-left unbalanced as one node is right of its parent node, and another node is left of its parent node. First, we will perform the right rotation that happens between nodes 30 and 20. After right rotation, 20 will move upwards, and 30 will move downwards as shown below:

Binary Search tree vs AVL tree

Still, the above tree is unbalanced, so we need to perform left rotation on the node. Once the left rotation is performed, the node 20 will move upwards, and node 10 will move downwards as shown below:

Binary Search tree vs AVL tree

As we can observe in the above tree, the tree follows the property of the Binary Search tree and a balanced tree; therefore, it is an AVL tree.

Differences between Binary Search tree and AVL tree

Binary Search tree vs AVL tree

Binary Search tree AVL tree
Every binary search tree is a binary tree because both the trees contain the utmost two children. Every AVL tree is also a binary tree because AVL tree also has the utmost two children.
In BST, there is no term exists, such as balance factor. In the AVL tree, each node contains a balance factor, and the value of the balance factor must be either -1, 0, or 1.
Every Binary Search tree is not an AVL tree because BST could be either a balanced or an unbalanced tree. Every AVL tree is a binary search tree because the AVL tree follows the property of the BST.
Each node in the Binary Search tree consists of three fields, i.e., left subtree, node value, and the right subtree. Each node in the AVL tree consists of four fields, i.e., left subtree, node value, right subtree, and the balance factor.
In the case of Binary Search tree, if we want to insert any node in the tree then we compare the node value with the root value; if the value of node is greater than the root node value then the node is inserted to the right subtree otherwise the node is inserted to the left subtree. Once the node is inserted, there is no need of checking the height balance factor for the insertion to be completed. In the case of AVL tree, first, we will find the suitable place to insert the node. Once the node is inserted, we will calculate the balance factor of each node. If the balance factor of each node is satisfied, the insertion is completed. If the balance factor is greater than 1, then we need to perform some rotations to balance the tree.
In Binary Search tree, the height or depth of the tree is O(n) where n is the number of nodes in the Binary Search tree. In AVL tree, the height or depth of the tree is O(logn).
It is simple to implement as we have to follow the Binary Search properties to insert the node. It is complex to implement because in AVL tree, we have to first construct the AVL tree, and then we need to check height balance. If the height is imbalance then we need to perform some rotations to balance the tree.
BST is not a balanced tree because it does not follow the concept of the balance factor. AVL tree is a height balanced tree because it follows the concept of the balance factor.
Searching is inefficient in BST when there are large number of nodes available in the tree because the height is not balanced. Searching is efficient in AVL tree even when there are large number of nodes in the tree because the height is balanced.

You may also like