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Поворачиваем ребро, связывающее кореньи его правый дочерний узел, влево.

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

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

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

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


 

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

82538. Мышление, его виды и мыслительные операции 35 KB
  В зависимости от характера деятельности и ее конечных целей доминирует тот или иной вид мышления. Однако по степени своей сложности по требованиям которые они предъявляют к интеллектуальным и другим способностям человека все виды мышления не уступают друг другу. Виды мышления: Нагляднодейственное мышление представляет собой совокупность способов и процесс решения практических задач в условиях зрительного наблюдения за ситуацией и выполнения действий с представленными в ней предметами. Необходимые для мышления образы представлены в...
82539. Особенности мышления у детей с нарушениями речи 30 KB
  Одним из самых трудных является вопрос о первичности речи и мышления об оценке структуры мышления у лиц с речевыми расстройствами. Практика и экспериментальные исследования показывают что мышление страдает в наибольшей степени при системных нарушениях речи алалии препятствующей его развитию и афазии затрудняющей его проявление. Важное практическое значение имеют достаточно часто встречающиеся особенно в последнее время сочетания расстройств речи и мышления.
82540. Особенности мышления у детей с ДЦП 32.5 KB
  Зачастую нагляднообразное и словеснологическое мышление начинает развиваться практически без фундамента нагляднодейственного мышления. Недостаточность нагляднодейственного мышления приводит к недостаточности в формировании других более сложных форм мыслительной деятельности. Нагляднообразное мышление обычно формируется на основе нагляднодейственного мышления и чувственного опыта ощущения и восприятие.
82541. Особенности мышления у детей с нарушениями интеллекта 29 KB
  Современные исследования показали что у умственно отсталых имеются довольно грубые нарушения в условно рефлекторной деятельности нарушения взаимодействия процессов возбуждения и торможения а также нарушения взаимодействия сигнальных систем. Для умственно отсталых характерно недоразвитие познавательных интересов которое выражается в том что они меньше чем их нормальные сверстники испытывают потребность в познании. Все эти операции у умственно отсталых недостаточно сформированы и имеют своеобразные черты.
82542. Особенности мышления у детей с нарушениями слуха 33.5 KB
  У глухих детей обнаруживаются значительные индивидуальные различия в развитии их мышления. Около одной четвертой части всех глухих детей имеют уровень развития наглядного мышления соответствующий уровню развития этого вида мышления у слышащих сверстников. Кроме того небольшое число глухих детей около 15 каждой возрастной группе по уровню развития словесно логического мышления приближается к средним показателям слышащих сверстников.
82544. Общие недостатки мыслительной деятельности детей с ЗПР 51.5 KB
  Дети стремятся избежать любых интеллектуальных усилий. Дети не заинтересованы в результате выполнения задания. Эта особенность мышления проявляется в школе когда дети очень быстро теряют интерес к новым предметам. Дети с ЗПР начинают действовать сразу с ходу.
82545. Рекомендации по развитию памяти у детей с ЗПР 45 KB
  Для развития зрительномоторной и зрительной памяти используется поэтапная работа ребенка с образцами по которым необходимо конструировать определенные фигуры из палочек: сначала ребенок работает с постоянной зрительной опорой на образец: затем время рассматривания образца сокращается до 15 20 секунд в зависимости от сложности предлагаемой работы но так чтобы ребенок успел рассмотреть и запечатлеть образец. Похожие упражнения легко придумать самим варьируя условия материал и сюжеты игр на развитие зрительномоторной и зрительной...
82546. Задания, направленные на развитие памяти у детей младшего школьного возраста с ЗПР 24 KB
  Развитие визуальной памяти Точки. Детям поочередно предъявляется несколько предметных картинок от 3 до 7 которые они затем воспроизводят по памяти в тетради. Детям предлагается по памяти подробно описать внешность одноклассника интерьер какоголибо помещения подробности пути в школу и т.