AVL Trees

What is an AVL Tree

AVL Trees is a data structure which allows efficient value lookups, insertions and deletions by implementing a self balancing binary search tree. The most important property of an AVL Tree is its invariant, i.e. the absolute difference in heights of the left and right subtree of a node can be atmost 1

• Since it is a BST at its core, all values in left subtree are less than parent node value , and all values in right subtree are greater than parent node value, with equalities depending upon the tree implementation
• In the worst case scenario, for every node in the tree, the absolute difference b/w heights of left and right children is always 1
• Height : O(logN), where N is the number of nodes in the tree

Time complexity of an AVL Tree

1. Insertion : O(logN)
2. Deletion : O(logN)
3. Lookup : O(logN)

When to use AVL Trees

There exist many efficient data structures for similar purposes, like Red Black Trees, B-Trees, etc

So, the question arises which DS should one use

The answer depends upon the scenario and the context in which we need to apply the DS

If we have fewer insertions and deletions, and more lookups, we would prefer an AVL tree. Since during insertions, we have to check all nodes on the path from root to leaf where a new node was inserted to fix any height imbalances. The number of nodes on the path from root to leaf is O(logN). The lookups however are really efficient since height imbalance b/w the child subtrees is atmost 1

If we have more insertions and deletions, but less lookups, then we would prefer RBTs. This is because RBTs can have paths with all black nodes and some paths with alternating black and red nodes, leading to the possibility of some paths having length 2x the length of other paths. However, insertion and deletion require a lot fewer rotations when compared to AVL Trees, and hence RBTs are better suited for this task

B-Trees are prefered when we want to reduce the number of calls maded to main memory for access to data