What exactly is the difference between a Balanced Binary Search Tree and an AVL tree?

Question

I'm learning some Data Structures and I cannot figure out the difference between the Balanced BST and the AVL Tree. From my understanding, an AVL tree is a balanced tree with the height difference <= 1.

But then what about the Balanced Binary Search Tree? What's the difference here?

Let's take an example:

I have a sorted array X = {1,2,3,4,5} and if I insert each of the values in X into a Balanced Binary Search Tree, I get the PreOrder output as 3 1 2 4 5. However, if I insert each of the values of X in an AVL tree, I get the PreOrder output as 2 1 4 3 5.

I notice that an AVL is always self-balancing, but it seems that a balanced BST is not necessarily an AVL.

I am quite confused about this. Is there something I am missing here?

Answer 1

There are some implementations of Balanced Binary Search Trees, also known as Self-balancing Binary Search Trees. One of the aspects that can be considered when balancing a tree is it's subtrees height difference. This height aspect aims to keep the tree as flat as possible. The more flat the tree is, the less levels it will have and the search will be faster.

The implementation that you mentioned reconstructs the entire tree when a new node is inserted, from the root to the leaves. The AVL tree will reorganize (balance) only the subtrees needed to meet its invariant, i.e., the height difference less or equal to one, when a new node is inserted or a existing node is removed.

The pre-order traversal will be different, since these two BBSTs have different implementations! If you test, maybe a red-black tree (another BBST), the preorder will be different too!

The main thing to keep in mind is that the reason of the BBSTs to exist is that they will keep them more flat as possible to speed up the search for nodes. The only traversal that will be equal among them (if they are search trees) is the in-order traversal, that can be also used to sort data.