Those data structures can not learn from Leetcode — AVL

Another Self-Balancing BST explained step by step

Continuing with advanced DSA topic: Skip list, B Tree Step by Step, Treap, Red-Black Tree

In this post, I will go over the process of building AVL tree.

If you walked through the earlier Red-Black Post, I promise you this one only takes you 5 mins to digest (it’s much simpler) 🙂

Let’s start.

Definition

the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. from wiki

Let’s start with the Insertion process.

Insert: 9

This is the first and only node. nothing to do.

Insert 10

2 nodes on the tree. root node left and right tree height difference is 1, it is still balanced.

Of course, the same as other auto-balance binary search trees, the insertion position is done by binary search.

Insert 11

Oops, the problem happens. the tree is not balanced anymore. right tree height=3 however left tree height=1. left rotation(center node=2) happens (will explain details below). for now, let’s call this as “Case #1”

Insert 12