Балансировка двоичного дерева (AVL)

StackOverflow https://stackoverflow.com/questions/133610

Вопрос

Ладно, это еще один урок из области теории для парней из CS.

В 90-е годы я довольно хорошо преуспел в внедрении BST.Единственное, что у меня никак не укладывалось в голове, это сложность алгоритма балансировки двоичного дерева (AVL).

Ребята, вы можете мне в этом помочь?

Это было полезно?

Решение

Дерево козлов отпущения, возможно, имеет самый простой алгоритм определения баланса для понимания.Если какая-либо вставка приводит к тому, что новый узел становится слишком глубоким, он находит узел, вокруг которого нужно восстановить баланс, рассматривая баланс веса, а не роста.Правило, определяющее, следует ли выполнять перебалансировку при удалении, также простое.Он не хранит никакой тайной информации в узлах.Сложнее доказать, что это правильно, но вам это не нужно, чтобы понять алгоритм...

Однако, в отличие от AVL, он не всегда сбалансирован по высоте.Как и у red-black, его дисбаланс ограничен, но, в отличие от red-black, его можно настроить с помощью параметра, поэтому для большинства практических целей он выглядит настолько сбалансированным, насколько вам нужно.Я подозреваю, что если вы настроите его слишком туго, это закончится так же плохо или хуже, чем AVL для наихудших вставок.

Ответ на вопросправить

Я расскажу о своем личном пути к пониманию деревьев AVL.

Сначала вы должны понять, что такое вращение дерева, поэтому игнорируйте все остальное, что вы когда-либо слышали об алгоритмах AVL, и поймите это.Четко запомните, что такое поворот вправо, а что такое поворот влево, и что каждый из них делает с деревом, иначе описания точных методов просто собьют вас с толку.

Далее, поймите, что хитрость балансировки деревьев AVL заключается в том, что каждый узел записывает в нем разницу между высотой своего левого и правого поддеревьев.Определение "сбалансированной высоты" заключается в том, что она находится в диапазоне от -1 до 1 включительно для каждого узла в дереве.

Далее, поймите, что если вы добавили или удалили узел, возможно, вы разбалансировали дерево.Но вы могли изменить баланс узлов, которые являются предками добавленного или удаленного вами узла.Итак, что вы собираетесь сделать, так это проделать обратный путь вверх по дереву, используя вращения для балансировки любых найденных вами несбалансированных узлов и обновляя их оценку баланса, пока дерево снова не будет сбалансировано.

Заключительная часть понимания этого - найти в приличном справочнике конкретные вращения, используемые для перебалансировки каждого найденного вами узла:это его "техника" в противоположность высокой концепции.Вам нужно запоминать детали только при изменении древовидного кода AVL или, возможно, во время проверки структур данных.Прошли годы с тех пор, как у меня в последний раз был открыт древовидный код AVL в отладчике - реализации, как правило, доходят до точки, где они работают, а затем продолжают работать.Так что я действительно ничего не помню.Вы можете вроде как решить это за столом, используя несколько покерных фишек, но трудно быть уверенным, что у вас действительно есть все кейсы (их не так уж много).Лучше всего просто посмотреть на это.

Затем возникает необходимость перевести все это в код.

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

Другие советы

Я не думаю, что стоит публиковать здесь полные коды для алгоритмов балансировки узлов, поскольку они становятся довольно большими.Однако статья в Википедии о красно-черные деревья содержит полную реализацию алгоритма на языке Си и статью о Деревья AVL также содержит несколько ссылок на высококачественные реализации.

Этих двух реализаций достаточно для большинства сценариев общего назначения.

В последнее время я немного поработал с деревьями AVL.

Лучшая справка о том, как их сбалансировать, которую я смог найти, была через поиск в Google.

Я просто закодировал этот псевдокод (если вы понимаете, как выполнять вращения, это довольно легко реализовать).

IF tree is right heavy
{
  IF tree's right subtree is left heavy
  {
     Perform Double Left rotation 
  }
  ELSE
  {
     Perform Single Left rotation
  }
}
ELSE IF tree is left heavy
{
  IF tree's left subtree is right heavy
  {
     Perform Double Right rotation
  }
  ELSE
  {
     Perform Single Right rotation
  }
}

Я согласен, полная программа была бы неуместна.

В то время как классические AVL и RB tree используют детерминированный подход, я бы предложил взглянуть на "Рандомизированные бинарные деревья поиска" поддержание баланса обходится дешевле и гарантирует хорошую балансировку независимо от статистического распределения ключей.

Дерево AVL неэффективно, потому что вам приходится выполнять потенциально много поворотов для каждой вставки / удаления.

Красно-черное дерево, вероятно, является лучшей альтернативой, потому что вставки / удаления намного эффективнее.Такая структура гарантирует, что самый длинный путь к листу не более чем в два раза превышает самый короткий путь.Таким образом, хотя он менее сбалансирован, чем дерево AVL, наихудших несбалансированных случаев удается избежать.

Если ваше дерево будет прочитано много раз и не будет изменено после его создания, это может стоить дополнительных затрат на создание полностью сбалансированного дерева AVL.Кроме того, красно-черному дереву требуется один дополнительный бит памяти для каждого узла, который придает узлу "цвет".

Для балансировки дерева AVL я только что написал кучу функций, которыми я думал поделиться со всеми здесь присутствующими.Я предполагаю, что эта реализация безупречна.Запросы / вопросики / критика, конечно, приветствуются:

http://uploading.com/files/5883f1c7/AVL_Balance.cpp/

Будучи новичком в Stackoverflow, я попытался опубликовать свой код здесь, но застрял из-за проблем с форматированием.Итак, загрузил файл по приведенной выше ссылке.

Ваше здоровье.

существует полная реализация самобалансирующегося дерева avl @ http://code.google.com/p/self-balancing-avl-tree/ .он также реализует операции объединения и разделения по логарифмическому времени, а также коллекции map / multimap

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top