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?