Обсуждение:АВЛ-дерево

Не понял про балансы. Как-то так вначале ни члова про них, а потом сразу расстановка балансов при том-то и при том-то. Что это вообще такое, баланс? 213.184.238.84 21:54, 18 марта 2009 (UTC)

Баланс некоторого узла определяется как высота его левого поддерева минус высота его правого поддерева.213.184.238.84 22:01, 19 марта 2009 (UTC)

А еще перепутали левое и правое вращения вроде. 213.184.238.84 21:19, 21 марта 2009 (UTC)

Да, в таблице "Расстановка балансов при двойном повороте" правое и левое местами поменять надо... 95.37.135.166 08:48, 2 июля 2009 (UTC)

Точно, перепутано левое и правое вращение. 178.18.9.171 17:34, 10 июня 2010 (UTC)

В опубликованном ранее алгоритме была ошибка при реализации поворота, когда баланс поднимаемой вершины = 0. Был перепутан расчёт баланса (Высота правого минус высота левого, а не наоборот). Добавил к рекурсивным алгоритмам нерекурсивные со спуском сверху-вниз (рекурсию в последнее время не очень жалуют). Все алгоритмы рабочие, надеюсь кто будет читать эту статью не будут испытывать такие проблемы как я при реализации данных алгоритмов, всё в действительности очень просто, гораздо проще чем с красно-черными деревьями.

Пытался сравнить скорость с красно-черными деревьями (только алгоритмы сверху-вниз без использования указателя на вышестоящую вершину), при вставке - АВЛ-дерево работает быстрее из-за большей сбалансированности подтвердить что АВЛ-деревья медленнее при удалении чем к-ч у меня не получается, может я просто не так запрограммировал красно-черные (но по моему субъективному мнению причиной тут является "жадность" алгоритмов сверху-вниз для красно-черных деревьев) 178.216.69.48 07:55, 22 июля 2012 (UTC)

Статья нуждается в полной переработке!

Для начинающего, Вращения из этой статьи понять очень тяжело, кто не понял сразу - не пытайтесь... смело ищите/берите книжку Вирт Н. Алгоритмы и структуры данных. Глава 4.5 (Страницы 272-286), сам программировал AVL-дерево, использовал ещё статью[1] на английской википедии, там хороший рисунок объясняющий Вращения. --93.120.178.122 15:49, 16 июля 2009 (UTC)

Согласен! На хабре написанно гораздо понятнее и доступнее!

Применение

В статье не хватает раздела о применении АВЛ-деревьев. Зачем они вообще нужны? И вообще, статья никуда не годится.

Ну так вперёд — улучшайте статью! А нужны AVL-деревья затем же, зачем нужны и все другие виды сбалансированных двоичных деревьев — чтобы операции над ними работали за O(log n) времени в худшем случае, а не за O(n). И не забывайте подписывать сообщения. -- X7q 09:14, 23 августа 2009 (UTC)

AVL-деревья, если я не ошибаюсь, исторически были самым первым открытым типом сбалансированных двоичных деревьев. И открыты, причём, советскими учёными. X7q 09:16, 23 августа 2009 (UTC)