2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ As you said, AVL tree is a kind of Balanced Binary Search Tree. I think that maybe you are getting confused with the concepts, don't you? What is your source for this Balanced BST that you are talking about? $\endgroup$ Oct 14, 2020 at 22:46
  • $\begingroup$ @davidbuzatto Yes, I'm getting a bit confused with the concepts. The source for the Balanced BSt is geeksforgeeks.org/sorted-array-to-balanced-bst . You will notice they have an implementation of it in the link. However, the output it different when compared to an AVL implementaion $\endgroup$
    – nTuply
    Oct 14, 2020 at 23:08

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.