1
$\begingroup$

I was going through the concepts of AVL tree and came across the definition of AVL tree from the wiki.

In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree

even most of the definition claims that AVL tree is BST, but is every AVL tree needs to be BST can't it be just BT?

In my point of view, AVL follows an algorithm that balances the Binary Tree, as BST is the subset of the binary tree, then this balancing algorithm can be applied on it.

is there anything that I am missing? Any contradictory example will be highly appreciated.

$\endgroup$
  • $\begingroup$ There is no need to rotate if it's not a BST. Rotations are only needed because ordering matters. $\endgroup$ – xuq01 Jul 27 '18 at 9:02
5
$\begingroup$

Yes every AVL tree is a BST

also note that every binary search tree itself is a binary tree (binary tree is basically a tree that each node has at most two child) so therefore every AVL is a binary tree as well.

AVL tree is just a binary search tree that tries to do rotations when its needed (when the tree becomes unbalanced) in order to stay balanced, and therefore the search time would be O(logn)

the reason behind using AVL instead of BST is to make sure the search time is O(logn) because if we use BST and insert the values in a decreasing or increasing order then the BST would be one sided and the search time will be O(n), but if we do that using AVL then the tree will balance itself using rotations.

i suggest you to read the definitions of all of them so you can understand better.

$\endgroup$
  • $\begingroup$ So concepts that are being used in AVL to balances itself(Different type of imbalance LL, RR, LR, RL) can also be applied to any Binary Tree, not necessarily BST so that it can be balanced. $\endgroup$ – Thinker Jul 27 '18 at 7:09
  • $\begingroup$ @Thinker yes you can write a code that does the same thing with BT but its basically something useless to do because even if you make it balanced the search time is still O(n) and our entire struggle is to make the search time shorter. if you want your BT to be balanced you can just use a complete Binary Tree which is already balanced. and if you are ok with search time of O(n) why not just use a queue with linked list instead? $\endgroup$ – John P Jul 27 '18 at 8:02
  • $\begingroup$ @JohnP a binary tree is not necessarily balanced. The AVL rotations preserve in-order traversal. A BST is a binary tree where the in-order traversal is sorted, but doing search is not the only reason one might want to preserve in-order traversal. $\endgroup$ – Max Jul 27 '18 at 10:09
  • $\begingroup$ @max but i didn't say binary tree is balanced? i said AVL is balanced and also the complete binary tree(where we insert values left to right). $\endgroup$ – John P Jul 27 '18 at 10:59
  • $\begingroup$ @JohnP I guess I missed the word "complete", sorry. $\endgroup$ – Max Jul 27 '18 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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