43966

Оптимизация алгоритма построения AVL дерева

Доклад

Информатика, кибернетика и программирование

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

Русский

2014-03-31

63.34 KB

5 чел.

Оптимизация алгоритма построения AVL дерева.

АВЛ-деревья

По определению идеально сбалансированное дерево это дерево, все уровни которого, за исключением, может быть, последнего, полностью заполнены. (В бинарном дереве полностью заполненный уровень n содержит 2n узлов). При соблюдении данного условия бинарное дерево предоставляет оптимальнейшие условия для поиска в нем. Однако на практике поддерживать идеальную балансировку дерева вряд ли выгодно, поскольку процедура ее восстановления после случайного включения – довольно сложная операция, поэтому вводится понятие АВЛ-сбалансированных деревьев (АВЛ – аббревиатура фамилий создателей: Адельсон-Вельский и Ландис), в которых критерий сбалансированности несколько упрощен. Дерево называется АВЛ-сбалансированным тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1 Балансировка выполняется с помощью действий, называемых поворотами узлов. При включении узлов повороты выполняются для ближайшего узла с нарушенной балансировкой к включенному. То есть, если после включения узла в дереве образуется несколько узлов с нарушенной балансировкой, поворот выполняется для того, который находится ниже (то есть ближе к включенному). После балансировки этого узла восстанавливается баланс и выше расположенных узлов. Нарушенный путь обозначается аббревиатурами LL, RR (при данном типе разбалансировки выполняется одинарный поворот), RL, LR (требуется двойной поворот), в зависимости от пути от разбалансированного узла к узлу, вызвавшему эту разбалансировку. Причем, стоит отметить, что при LL и RR, и при RL и LR выполняемые действия являются симметричными относительно узлов, что удобно при реализации алгоритма.Правый поворот

 

В левое поддерево добавили элемент 1Дерево не сбалансированноH(Left)=1 > H(Right)=-1Необходимо увеличить высоту правого поддерева

Поворачиваем ребро, связывающее кореньи его левыйдочерний узел, вправо

Левый поворот(L-rotation)В правое поддерево вставлен элемент3Поворачиваем ребро, связывающее кореньи его правый дочерний узел, влево

 

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

При реализации изложенных выше алгоритмов полезно учесть следующие соображения:

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

Для хранения ссылок на «потомков» используйте массив указателей: так будет проще организовать симметрию поворотов.

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


 

А также другие работы, которые могут Вас заинтересовать

46270. Electricity Basics 13.06 KB
  Electricity is mde by converting some form of energy into flowing electrons t the power plnt. The type of power plnt depends on the source of energy used: therml power col oil gs nucle r underground stem solr power photovoltic kinetic power wter wind nd chemicl power fuel cell. This system enbles power plnts I nd end users to be connected together. Wtt W is unit mesure of electric power tht depends on mps nd volts.
46271. Языковая просодия, уровни изучения. Суперсегментные звуковые единства. Словесное ударение основные виды 13.05 KB
  Словесное ударение основные виды. Уровни изучения: словесное ударение и фразовая интонация Ударение в слове выделение фонетическими средствами одного слога в составе группы слогов. Виды ударений: экспираторное выдыхательное динамическое силовое ударение за счёт силы выдоха долготное тоновое ударение за счёт восходящего нисходящего комбинированного языкового тона на фоне нейтрального или др. prosodi припев ударение наслаиваются на цепочку сегментов слогов слов фраз предложений.
46272. Понятие субъекта в концепции Ж.Пиаже 13.02 KB
  Понятие субъекта в концепции Ж. Первоначально ребенок воспринимает мир как индивид который не знает себя в качестве субъекта не понимает своих собственных действий и поэтому приписывает реальности свои субъективные ощущения даже не подозревая об этом. По Пиаже ребенок на ранних стадиях развития воспринимает мир как солипсист он игнорирует себя в качестве субъекта и не понимает собственных действий. Конструкция представления об окружающем мире о реальности у ребенка в первые годы...
46273. Ж.Пиаже Как дети образуют математические понятия 13.01 KB
  Пиаже Как дети образуют математические понятия. Младшие дети думают что число изменилось. Но дети в возрасте около 7 лет уже понимают что перемещение не меняет число бусинок. Дети должны уловить принцип сохранения количества прежде чем они могут образовывать понятия числа.
46275. The category of mood 12.83 KB
  There re three moods in English the indictive mood the impertive mood nd the subjunctive mood.The indictive mood form shows tht wht is sid must be regrded s fct s something which hs occurred or is occurring t the moment of speking or will occur in the future. Therefore the indictive mood hs wide vriety of tense nd spect forms in the ctive nd pssive voice.
46276. Кризис семи лет 12.81 KB
  Основная симптоматика кризиса:Потеря непосредственности: между желанием и действием вклинивается переживание того какое значение это действие будет иметь для самого ребенка;Манерничание: ребенок чтото из себя стоит чтото скрывает уже душа закрыта;Симптом горькой конфеты: ребенку плохо но он старается этого не показывать;Трудности воспитания: ребенок начинает замыкаться и становится неуправляемым. Переживания приобретают смысл сердящийся ребенок понимает что он сердит благодаря этому у ребенка возникают такие новые отношения к...
46277. Эльконин Д.Б. «К проблеме периодизации психического развития в детском возрасте» 12.75 KB
  Некоторые считали что в этом возрасте важно развитие сенсомоторноманипулятивной деятельности. Однако решили что речь используется ребенком в данный период возраста для налаживания сотрудничества с взрослыми в предметной деятельности. В игровой деятельности ребенок моделирует отношения между людьми. Большие трудности представляло выделение ведущей деятельности у подростков.
46278. Особенности формального мышления в подростковом возрасте 12.74 KB
  Они завершают линию развития начавшуюся в младенчестве формированием сенсомоторных структур и продолжавшуюся в детстве вплоть до предпубертатного периода становлением конкретных умственных операций. На ранней фазе взросления этот процесс идет тремя путями: 1 развитие комбинаторики; 2 развитие пропозициональных операций; 3 появление гипотетикодедуктивного мышления. Если на стадии конкретных операций ребенок сортирует предметы только по признаку тождества или сходства теперь становится возможной классификация неоднородных объектов в...