Балансировка АВЛ-дерева

Существует замечательный универсальный алгоритм балансировки АВЛ-дерева (AVL), который охватывает сразу все возможные случаи нарушения сбалансированности дерева. Данный алгоритм называется трехузловая реструктуризация (англ. Trinode Restructuring) и в российской литературе почему-то практически не встречается.

Что такое АВЛ-дерево

АВЛ-дерево – это сбалансированное двоичное дерева поиска. Сбалансированность выражается в том, что высота левого и правого поддеревьев каждой вершины отличается не более чем на единицу.

АВЛ-дерево

Каждая вершина AVL-дерева характеризуется показателем под названием balance factor (разница между высотой правого и левого поддерева). У узлов сбалансированного дерева он равен -1, 0 или 1.

Если при добавлении новой вершины или удалении существующей balance factor становится равным -2 или 2, то требуется балансировка дерева.

Алгоритм балансировки АВЛ-дерева

Всего существует четыре варианта разбалансировки AVL-дерева. Вариант 1:

Балансировка АВЛ-дерева

Варианты 2, 3 и 4:

Балансировка АВЛ-дерева

Во всех четырех вариантах используется один и тот же алгоритм балансировки АВЛ-дерева, под названием трехузловая реструктуризация (англ. Trinode Restructuring).

Для узлов x, y, z:

  • Выбираем из трех вершин ту, которая имеет медианное значение ключа. Данная вершина будет новым узлом-родителем.
  • Узел с наименьшим значением ключа будет его левым потомком.
  • Узел с наибольшим значением ключа будет его правым потомком.
  • Прежних потомков нового узла-родителя нужно разместить так:
    Левое поддерево (если оно было и не равно связи с новыми потомками) становится правым поддеревом нового левого узла.
    Правое поддерево (если оно было и не равно связи с новыми потомками) становится левым поддеревом нового правого узла.

Процедура балансировки начинается из глубины дерева и продолжается до тех пор, пока все AVL-дерево не станет сбалансированным.

Балансировка АВЛ-дерева
5 (100%) 2 votes

Поделиться в соц. сетях:

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

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

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">