AVL деревья и широта их применения

Решил немного описать на мой взгляд самую полезную древовидную структуру. AVL дерево это бинарное дерево (у каждой вершины не более 2 сыновей), в котором каждой вершине присвоен идентификатор (как раз его и хранит дерево), идентификаторы подчиняются следующему правилу: ID левого сына<ID родителя<ID правого сына.
Т.е. если обходить дерево рекурсивно слева направо получим отсортированный по возрастанию список ID, справа налево – по убыванию.
Причем дерево максимально сбалансировано: высота левого поддерева отличается от высоты правого максимум на 1.

Интересно в нем то, что тогда на проверку существования элемента в дереве уходит log(N) N – количество ID. Ведь надо пройти от корня вниз, а поскольку дерево максимально симметрично то его высота — log(N)+1
Хорошая новость – нам никто не запрещает прикрепить к вершине еще какие-то полезные данные и тогда выборка произвольных данных по ID будет занимать log(N) времени
Плохая новость – одинаковые ID как следует из определения в нем существовать не могут. Придется делать финт ушами, один способ сделать вместо каждой вершины список вершин с одинаковым ID, другой – изменить алгоритм балансировки.

Еще одно свойство – можно быстро находить элементы массива ближайшие к заданному, но меньше его, или больше – для некоторых задач очень актуально.

Интересно вот что: очевидно такое дерево из списка идентификаторов можно построить, но так же, оказывается, в него можно быстро добавлять и быстро удалять элементы за очень короткое время <= log(N) (добавление)

Таким образом для сортировки массива из N элементов можно его просто добавить в дерево – N*log(N) а потом обойти слева направо – N т.е. суммарное время N*log(N) – и мы сделали очередной очень быстрый метод сортировки массива

Кстати еще несколько операций для удобства – раз мы быстро ищем вершину с нужным ID, то сделаем операции Set и Get для изменения поля DATA в вершине. Таким образом обновление данных соответствующих заданному ID в памяти мы делаем тоже за <=log(N)

Я применяю AVL дерево очень часто: даже в стандартном хеше по CRC я храню группы CRC в дереве, сортирую массивы и списки, использую для проверки существования элементов в массиве, храню индексы БД, сортирую им результаты поиска (как описано выше), в конце концов, его даже можно напрямую писать в файл и считывать для еще большего ускорения.
Вообще эта структура не сильно больше чем список, а позволяет делать в сотни раз больше операций, т.е. хорошая альтернатива 1-2 связному списку.

Теперь немного про то, как же добавлять в дерево, полных описаний очень много в свободном доступе, поэтому кратенько:
Введем в каждую вершину число balance которое показывает, какое из поддеревьев выше – левое или правое.
При добавлении вершины в дерево оно иногда становится не сбалансированным. Процедура добавления проста – спускаемся по дереву до самого низа, используя правило
ID левого сына<ID родителя<ID правого сына, т.е. если новый ID < ID вершины идем влево, иначе вправо. Добавив сына к нижней вершине мы должны обновить показатель balance по нашему пути которым мы шли – можем это делать по ходу спуска, можем пройтись вверх обратно – если пришли из левого поддерева то balance--, иначе balance++
Если на каком-то уровне мы получили balance=0 – то поддерево сбалансировано и можно закончить добавление (все дерево вверху не надо пересчитывать т.к. высота поддерева не изменилась – было balance=-1 стало 0 – левое поддерево перевешивало, добавили в правое и выровняли, или balance=1 стало 0 — правое поддерево перевешивало, добавили в левое и выровняли)

Ну и самое интересное это балансировка поддерева если на каком-то шаге по обратному пути мы получили balance=-2 или 2, это значит что одна половина дерева перевесила сильно, и надо сделать некий поворот – поднять на 1 звено, к примеру, правое, а левое удлинить. Весь поворот сводится к проверке условий и переставлению ссылок, лично я его понимал для себя на бумажке – возможны всего 3 варианта, чего и вам советую для лучшего осознавания – специально не буду здесь расписывать словами то, что можно нарисовать, а если совсем лень, то найти в инете готовые решения.

Полное содержание и список моих статей по поисковой машине будет обновлятся вот здесь: http://habrahabr.ru/blogs/search_engines/123671/