What is tree balancing?

Tree balancing is the process of restructuring a tree so that its height stays minimal and its elements are distributed evenly.

#Why it's needed

In an unbalanced tree (for example, when all elements are inserted in increasing order), the structure becomes similar to a list, and search, insertion, and deletion slow down from O(log n) to O(n).

#Goal of balancing

Make sure that for every node, the difference between the heights of its left and right subtree is small (usually ≤ 1). Then the tree stays "dense", and search works quickly again.

#Example

Unbalanced tree (all to the right):

After balancing:

#Types of balanced trees

• AVL tree - strict height balance (difference ≤ 1).
• Red-black tree - a more flexible balance based on node-coloring rules.
• B-tree, B+ tree - balancing for storing data on disk (for example, in databases).

#Summary

Tree balancing means keeping the tree in a shape where search, insertion, and deletion run as fast as possible (≈ O(log n)), regardless of the order elements were added in.