Binary Search Tree vs AVL Tree: Data Structure

Difference Between Binary Search Tree and AVL Tree

Binary Search Tree: The binary search tree is a kind of binary tree data structure and it follows the conditions of binary tree. As we know, in binary tree a node has utmost two children so this same condition followed by binary search tree. In addition, a binary search tree has some other properties as follows:

• In binary search tree, the left sub - tree of any node contains only smaller elements than the node element.
• In binary search tree, the right sub - tree of any node contains only greater elements than the node element.
• The left sub-tree and the right sub - tree must also be following the properties of binary search tree.

The Time Complexity of Binary Search Tree: -

If we talk about operations of binary search tree take O (log n) time. The time complexity of these operations could be O(n) if the binary search tree skewed (if the input to the binary search tree comes in an ascending or descending manner).

AVL Tree: -

AVL Tree is referred to as self – balanced or height-balanced binary search tree where the difference between heights of its left sub-tree and right sub-tree (Balance Factor) can't more than one for all nodes covered by a tree.

We can say a tree is balanced if the balance factor of each node of a tree is in between -1 to 1; otherwise, a tree is considered as unbalanced and need to balance.

Balance Factor (node) = height (left (node)) – height (right (node))

• If the balance factor is 1 of any node of the tree, then we can say the height of the left sub - tree is higher than the height of the right sub - tree of the node in the AVL tree.
• If the balance factor is 0 of any node of the tree, then we can say the height of the left sub - tree is equal to the height of the right sub - tree of the node in the AVL tree.
• If the balance factor is -1 of any node of the tree, then we can say the height of the left sub - tree is lower than the height of the right sub - tree of the node in the AVL tree.

AVL Tree Operations: -

As we discussed, the AVL tree is a special type of binary search tree, so the operations of the AVL tree are the same as the binary search tree without violation of AVL property.

• Insertion: -

In this, we add a new node to the AVL tree. Sometimes it may lead to violating the property of AVL, so we need to re-balance the tree by applying the rotation on it.

• Deletion: -

In this, we delete a node from the AVL tree. It may disturb the balance of the AVL tree, so the tree needs to be re-balanced.

Time Complexity of AVL Tree:

The rotations of the AVL tree take constant time. It is a self-balanced tree, so the time complexity of all the operations (e.g., insertion, deletion and searching) is O (log n).

Comparison Table: -

Binary Search Tree	AVL Tree
When application involves less amount of data.	When searching on the higher priority
Insertion and deletion are easy because no rotations are required in binary search tree.	Insertion and deletion are complex in AVL tree as it requires multiple rotations to balance the tree.
Searching in binary search tree is less efficient as compared to AVL tree.	Efficient searching can be done by AVL tree because it is strictly balanced.
All binary search can’t be an AVL tree because either they can be balanced or unbalanced.	AVL tree also be a kind of binary search tree because an AVL tree follows conditions of binary search tree.
In binary search tree, it does not contain any balance factor.	Each node has a balance factor in AVL tree whose value can be 1, 0, or -1. It requires extra space to store the balance factor per node.
The time complexity of binary search tree could be O(n) in worst case if binary search tree is skewed either left or right side.	The time complexity of AVL tree is O(log n) because it is strictly balanced tree.