Select Page

Difference between Binary Search Tree and AVL Tree

Team 1 - Programming
Published: January 8, 2023

Improve Article

Save Article

Like Article

Improve Article

Save Article

Binary Search Tree:

A binary search tree is also called an ordered or sorted binary tree because the in-order traversal of binary search tree is always in sorted order. 

A binary search tree is a binary tree with only two branches in which each node of the left subtree is less than or equal and each node in the right subtree is greater. A binary Search Tree is a node-based binary tree data structure. We can perform preorder, in-order, and post-order traversal using the Binary Search tree.

AVL Tree: 

AVL tree is a self-balancing Binary Search Tree where the difference between heights of left and right subtrees cannot be more than 1 for all nodes. This difference is called the Balance Factor i.e. 0, 1, and -1.

In order to perform this balancing, we perform the following rotations on the unbalanced/imbalanced Binary Search Tree to make it an AVL tree.

  • Left Rotation
  • Right Rotation
  • Left Right Rotation
  • Right Left Rotation

Following are the Difference between Binary Search Tree and AVL Tree

S.NoBinary Search TreeAVL Tree
1.In Binary Search Tree, In AVL Tree, every node does not follow the balance factor.In AVL Tree, every node follows the balance factor i.e. 0, 1, -1.
2.Every Binary Search tree is not an AVL tree.Every AVL tree is a Binary Search tree.
3.Simple to implement.Complex to implement.
4.The height or depth of the tree is O(n).The height or depth of the tree is O(logn)
5.Searching is not efficient when there are a large number of nodes in the Binary Search tree. Searching is efficient because searching for the desired node is faster due to the balancing of height. 
6.The Binary Search tree structure consists of 3 fields left subtree, data, and right subtree. AVL tree structure consists of 4 fields left subtree, data, right subtree, and balancing factor.
7.It is not a balanced tree.It is a balanced tree.
8.In Binary Search tree. Insertion and deletion are easy because no rotations are required. In an AVL tree, Insertion and deletion are complex as it requires multiple rotations to balance the tree.

Source: www.geeksforgeeks.org