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 O(h)O(h) time, where “h” is the height of a Binary Search Tree.

In the case of Skewed Trees, the complexity becomes O(n)O(n), where “n” is the number of nodes in the tree. Now to improve time complexity, We have to manage the height of the tree to improve time complexity, such that we can bring the time down to O(logn)O(logn) for performing these basic operations.

When to use AVL Trees?

As AVL are strictly balanced, AVL Trees are preferred in those applications where the lookup​ is the​ ​ most vital operation. The following is an example of a valid AVL Tree:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.