Рядом идеальное самобалансированное двоичное дерево поиска?

Question

Я понимаю, что AVL и Red Black являются реализациями балансировки деревьев. Но мне любопытно, как сложно было бы создать практически максимально возможное самобалансирующееся дерево. До такой степени, что высота может быть только с моего единственного узла не более чем на одну ветвь. Вероятно, это связано с большим количеством поворотов. Это было сделано/реализовано?

Answer 1

Я считаю, что деревья AVL действительно удовлетворяют вашему состоянию. В дереве AVL высоты двух дочерних поддеревьев любого узла отличаются не более чем одним; если в любое время они отличаются друг от друга более чем одним, выполняется перебалансировка, чтобы восстановить это свойство.

http://en.m.wikipedia.org/wiki/AVL_tree