![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Включение в сбалансированное дерево
Преимущество AVL -деревьев состоит в их сбалансированности, которая поддерживается соответствующими алгоритмами вставки-удаления. Процесс включения является почти таким же, как и для бинарного дерева поиска. Осуществляется рекурсивный спуск по левым и правым наследникам, пока не встретится пустое поддерево, а затем производится пробное включение нового узла в этом месте. 1. Следовать по пути поиска, пока не окажется, что ключа нет в дереве. 2. Включить новый узел и определить новый показатель сбалансированности. 3. Пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла. Возможны три ситуации: в первых двух узел сохраняет сбалансированность и реорганизация поддеревьев не требуется, а нужно лишь скорректировать показатель сбалансированности данного узла. В третьем случае разбалансировка дерева требует одинарного или двойного поворотов узлов. Случай 1. Узел на поисковом маршруте изначально является сбалансированным (balance равен 0). После включения в поддерево нового элемента узел стал перевешивать влево или вправо, в зависимости от того, в какое поддерево было произведено включение. Если элемент был включен в левое поддерево, показателю сбалансированности присваивается -1, а если в правое, - то 1.
Случай 2. Одно из поддеревьев узла перевешивает, и новый узел включается в более легкое поддерево. Узел становится сбалансированным.
Случай 3. Одно из поддеревьев узла перевешивает, и новый узел включается в более тяжелое поддерево. Тем самым нарушается условие сбалансированности, так как balance выходит за пределы -1... 1. Чтобы восстановить равновесие, нужно выполнить поворот.
Повороты Повороты необходимы, когда родительский узел P становится разбалансированным. Фактически ссылки обмениваются значениями по кругу, что приводит к однократному или двукратному повороту двух или трех узлов. Кроме вращения ссылок, следует также изменить соответствующие показатели сбалансированности узлов. Одинарный поворот вправо происходит тогда, когда родительский узел P и его левый потомок LC начинают перевешивать влево после включения узла в позицию X. В результате такого поворота LC замещает своего родителя, который становится правым наследником. Бывшее правое поддерево узла LC (ST) присоединяется к P в качестве левого поддерева. Это сохраняет упорядоченность, так как узлы в ST больше или равны узлу LC, но меньше узла P. Поворот уравновешивает как родителя, так и его левого потомка.
Пример:
Двойной поворот вправо происходит тогда, когда родительский узел (P) становится перевешивающим влево, а его левый потомок (LC) - перевешивающим вправо. NP - корень правого перевешивающего поддерева узла LC. Тогда в результате поворота узел NP замещает родительский узел. Возможны два варианта:
Пример: Попытка включить узел 25 разбалансирует корневой узел 50. В этом случае узел 20 (LC) приобретает слишком высокое правое поддерево и требует двойной поворот. Новым родительским узлом (NP) становится узел 40. Старый родительский узел становится его правым наследником и присоединяет к себе узел 45, который также переходит с левой стороны дерева.
|