Self-balancing binary search tree

AVL-Tree

Here we briefly introduce one of the self-balancing binary search tree (AVL-Tree).

Four basic rotations

Note that the red nodes are key pattern in rotations. Whether the blue nodes exist or not doesn’t matter. For the c++ implementation, please check the AVLTree project in VS2017.

The basic left and right rotations:

The left-right rotation and right-left rotation:

The left-right rotation: it just first left rotate 5, 6. And then right rotate 10, 6, 5. Note that the 5.5 could be the right child of 6, and the whole routine is still the same.

The right-left rotation: it just first right rotate 15, 13. And then left rotate 10, 13, 15.