Avl and binary tree have same worst and average time complexity for all operations.
Binary Search Tree has the properties:
The left subtree contains only the keys which are lesser than the key of the node.
The right subtree contains only the keys which are greater than the key of the node.
The left and right subtree both should be binary search tree.
Why AVL?
- most of the bst operation take o(h) time
- if the tree is skewed it may become o(n)
- height of AVL is always log n
- since it’s a binary tree the option are reduced by half at every node
- AVL insert time complexity is O(log n)
- how do insertion work in AVL?
- there are four cases:
- left left case
- left right case
- right right case
- right left case
Uses
- BSTs are used for indexing in databases.
- It is used to implement searching algorithms.
- BSTs are used to implement Huffman coding algorithm.
- It is also used to implement dictionaries.
- AVL trees are mostly used for in-memory sorts of sets and dictionaries. AVL trees are also used extensively in database applications in which insertions and deletions are fewer but there are frequent lookups for data required.
AVL trees can be colored red–black, thus are a subset of RB trees. Worst-case height is 0.720 times the worst-case height of RB trees, so AVL trees are more rigidly balanced.