AVL balanced binary tree details and implementation

What is a balanced binary tree?

Adelson-velsikii and Landis proposed a binary search tree with relatively balanced nodes in height, also known as AVL tree. Its average and worst-case search times are O(logn). At the same time, the time complexity of insertion and deletion remains O(logn) and remains balanced in height after insertion and deletion. AVL Tree is also called Balanced Binary Tree, namely Balanced Binary Tree or Height Balanced Tree. It is either an empty Binary Tree or Binary search Tree with the following properties: Both the left and right subtrees are highly balanced binary trees, and the absolute value of the height difference between the left and right subtrees is less than 1. If the Balanced Factor (BF) of a node in a binary tree is defined as the difference between the height of the left subtree and the right subtree of the node, according to the definition of AVL tree, the Balanced Factor of any node in AVL tree can only be -1 (the right subtree is higher than the left subtree), 0 or 1 (the left subtree is higher than the right subtree). In some graphs, it can also be expressed as absolute height difference, i.e. 0,1,2. Please pay attention to understanding.

Rebalance

The insertion or deletion of nodes in a balanced binary tree will lead to imbalance, and rotation operation is required to make every node in the tree in a balanced state

LL type: Right rotation

When the newly inserted node is the left subtree of the left child of the root node of the nearest unbalanced subtree, rotate it right to restore balance:

The newly inserted node A leads to the imbalance of node C, and node A is located in the left subtree of the left child of node C, so it rotates right with node C as the axis

A complicated example:

RR: Left rotation

When the newly inserted node is the right subtree of the right child of the root node of the nearest unbalanced subtree, rotate it right to restore balance:

The newly inserted node C leads to the imbalance of node A, and node C is located in the right subtree of the right child of node A, so node A is rotated right

A complicated example:

LR type: first right rotation then left rotation

When the newly inserted node is the right subtree of the left child of the root node of the nearest unbalanced subtree, rotate it left and then right to restore its balance:

The newly inserted node B causes the imbalance of node A, and node B is in the right subtree of the left child of node A:

① : Rotate right with node A as the cycle

Now it becomes LL, and then it rotates to the right around node C

A complicated example:

RL type: first right rotation then left rotation