АВЛ-дерево

Описание АВЛ-дерева вы можете прочитать в Википедии.

Здесь представлен код реализации рекурсивного АВЛ-дерева. Отличается от обычно бинарного дерева тем, что у узлов есть высота и показатель балансировки. Балансировка может меняться при добавлении или удалении, и восстанавливается с помощью малого левого(правого), или большого левого(правого) поворотов. Как это выглядит можно увидеть в той же Википедии.

Показатель балансировки подсчитывается специальной функцией, как и показатель высоты.

Для возможности бегать по узлам дерева, есть приватные функция getHigherNode, getLowerNode. К которым есть доступ у узлов. К примеру мы в самой левой вершине дерева, либо мы лист, либо у нас есть правое поддерево. Если мы лист, то надо вернуть просто нашего предка. Если же есть правое поддерево. То надо вывести следующую вершину справа. Мы попали в эту вершину. Мы снова либо лист, либо есть правое поддерево, либо есть левое поддерево, либо сразу оба. Если мы лист, то нам надо подняться вверх по дереву, пока мы являемся правым сыном нашего предка, как только мы попадем в наш первоначальный самый маленький узел, мы перестаем быть правым сыном, значит нам пора остановиться, и вернуть отца самого маленького узла. Если же есть только правое поддерево(вернулись к моменту, где мы правый узел от самого маленького), то спускаемся снова вправо и имеем те же ситуации. Если же есть только левое поддерево, то заходим в него и действуем по тем же правилам. Если есть оба, то сначала пойдем в левое поддерево, после того, как мы там побываем и вернемся к узлу, нам надо будет продолжить обходить правое поддерево.

Попробуйте данный алгоритм действия, для этого дерева.

  • Определите следующий элемент для узла 0001.
  • Определите следующий элемент для узла 0003.
  • Определите следующий элемент для узла 0004.
  • Определите следующий элемент для узла 0005.
  • Определите следующий элемент для узла 0007, зная, что предок корня — это null.

Дерево

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

 

 

Ссылка на ideone.

One thought on “АВЛ-дерево

  1. Засчитано. Работа структуры проверена в других постах — т.к. алгоритмы, использующие АВЛ-дерево работают (засчитаны), то и АВЛ-дерево рабочее.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *