What tree balancing algorithms are you familiar with?

• AVL trees (Adelson-Velsky and Landis trees): Maintain balance by controlling the height difference between the left and right subtrees of each node (balance factor not more than 1). Balancing is achieved through rotations.
• Red-Black trees: Use an additional color bit for each node (red or black) and a set of rules to maintain balance. More complex to understand and implement than AVL trees, but often have better average performance for insertions and deletions.
• 2-3 trees: Each node has 2-3 children and stores 1-2 keys. All leaves are at the same level. Balancing is achieved through merging and splitting nodes.
• B-trees: Generalization of 2-3 trees, used in file systems and databases. Each node has $M/2 \le K \le M$ keys, where $M$ is the order of the tree. Maintain balance through similar merging and splitting operations.
• Splay trees: Self-optimizing trees that move recently accessed elements to the root using the splay operation. Not strictly balanced, but provide good performance for sequence-of-operations.
• Treap (Tree + Heap): Each node is assigned a random priority. Nodes are arranged so that they form a correct binary search tree with respect to keys and a min-heap (or max-heap) with respect to priorities. Balance is maintained via rotations to satisfy the heap property.

Among these, the most commonly used in standard libraries and widely known are AVL trees and Red-Black trees. B-trees are typically used in scenarios where data is stored externally (on disk).