ОСТОРОЖНО МОШЕННИКИ! В последнее время в соиальных сетях учстились случаи педложения помощи в написании прогамм от лиц, прикрвающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в псторонних группах ВК. Для связи с нами используйте исключительно эти контакт: vscoderu@yandex.ru, https://vk.com/vscode


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


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

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

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

АВЛ-дерево

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

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

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

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

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


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

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

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

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

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

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

4.5/5 - (8 голосов)



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

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

Ваш адрес email не будет опубликован.