What is an AVL Tree?
This lesson is a brief introduction to AVL trees, why they are used, and how efficient they are.
We'll cover the following...
Introduction
AVL trees are a self-balanced special type of Binary Search Tree with just one exception:
For each Node, the maximum height difference between the left and right sub-trees can only be one.
If at any point their difference becomes more than one, then re-balancing is applied to make it a valid AVL tree.
Time Complexity
As we studied earlier, in the case of BST, the Big(O) of all three basic operations (Insertion, Deletion, and Searching) takes ...