Python Data Structures and Algorithms

Balancing trees

Earlier, we mentioned that if nodes are inserted into the tree in a sequential order, then the tree behaves more or less like a list, that is, each node has exactly one child node. We normally would like to reduce the height of the tree as much as possible, by filling up each row in the tree. This process is called balancing the tree.

There are a number of types of self-balancing trees, such as red-black trees, AA trees, and scapegoat trees. These balance the tree during each operation that modifies the tree, such as insert or delete.

There are also external algorithms that balance a tree. The benefit of these is that you wouldn't need to balance the tree on every single operation, but could rather leave balancing to the point ...