Существует замечательный универсальный алгоритм балансировки АВЛ-дерева (AVL), который охватывает сразу все возможные случаи нарушения сбалансированности дерева. Данный алгоритм называется трехузловая реструктуризация (англ. Trinode Restructuring) и в российской литературе почему-то практически не встречается.
