Pull to refresh

Comments 10

UFO just landed and posted this here
Я в своё время придумал вариант AVL дерева на два простых случая. Критерий балансировки почти классический: |h1 — h2| <= 1 плюс если разница высот равна 1, то перекос допускается только в стороны, т.е. для левого потомка фактическое правило: 0 <= h1 — h2 <= 1, а для правого потомка: -1 <= h1 — h2 <= 0. Там, правда, вылезает log2(n) сложность из-за того, что после вращений может поменяться ориентация узлов. Но для олимпиад было самое то — всего два случая (на левое и правое вращение) и т.к. алгоритм знал только я, тестов на этот квадрат не было :)
UFO just landed and posted this here
Уровень вершины — это некая вспомогательная величина, которая есть у каждой вершины и листовая вершина получает вначале в качестве 1. Далее уровень меняется при балансировке таким образом, что всегда в АА-дереве две вершины одного уровня связаны только правой связью.

Это и есть определение «уровня вершины», это понятие нельзя выразить в виде высоты или еще как-то.

Это как бы переменная условия-инварианта.

На рисунке после выполнения операции split:

R.level = X.level + 1 = T.level + 1 = A.level + 2 = B.level + 2

То есть разбалансировка (две правые связи) решается добавлением нового уровня и перегруппировкой.

Конечно, +1 за статью. Но вот смущает… .level это то, что уменьшается постоянно?

Эврика. Я увидел Inc. Но только после чтения Википедии. Паскаль, конечно, многим хорош. Присваивания вот в тексте легко искать: вместо =[^=], как в Си ищем :=. Но вот, надо бы этой возможностью документации пользоваться и всё же вместо Inc и Dec писать P^.level :=.

Но это так, бурчание. А по теме. Раз level — это отдельный счётчик, то нужно учитывать, что его нельзя сделать битовым полем в одном из указателей, как это допускают красно-чёрные деревья или деревья AVL. В итоге, получаем накладные расходы на объём хранимой информации в памяти её чтение и запись.

А тут довольно много обращений в память происходит. Плюс ещё есть операция копирования содержимого узлов. А если ключ большой?

AVL-деревья с этой точки зрения, как мне кажется, гораздо симпатичнее. Там и доступы в память оптимальнее и поворот вообще нужен только один.
Накладные расходы на запись/чтение level с лихвой компенсируются простотой кода — то есть малыми размерами — то есть скоростью. Я для интереса нашел реализацию AVL на Delphi и сравнивал, AVL отставал на 10-20%. Понимаю, что утверждение, что АА-дерево всегда быстрее AVL требует более строгих тестов, тем не менее в моих тестах оно было быстрее.

level это дополнительные 4 байта на вершину. Но, вообще говоря, не думаю, что в реальности можно столкнуться с деревьями, глубина которых превышает 256, ведь тогда кол-во элементов будет примерно 2^256 (что довольно много :-) ). Так что можно ограничиться одним байтом.

Что касается копирования узлов — его можно избежать, введя указатель на parent и меняя исходные ссылки на вершины (а не сами вершины).

Я буду рад сравнить скорость Вашей самой быстрой реализации AVL-дерева с AA-деревом.

Ок. Я как раз хочу нечто такое написать на Хабре. Только это будет не скоро. Недели через 3. Но я в todo'шку себе занесу это соревнование.

А ещё мне не кажется, что AA-код сильно проще. AVL-деревья реализуют обычно, описывая 4 разных поворота, но на самом деле их всего 2, с параметром. Что код упрощает существенно.
Sign up to leave a comment.

Articles