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

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

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

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

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


 

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

3574. Особистість вчителя в реалізації науково – методичного проекту для успішного розвитку творчої особистості учня 24.65 KB
  Особистість вчителя в реалізації науково – методичного проекту для успішного розвитку творчої особистості учня Як удосконалити себе як вчителя, як готувати учня до життя, яка особистість потрібна суспільству сьогодні та як вчити, виховувати. За...
3575. Наші друзі – дельфіни. Виконання композиції аквареллю з використанням нетрадиційних методів малювання. 49 KB
  Наші друзі – дельфіни. Виконання композиції аквареллю з використанням нетрадиційних методів малювання. Мета: учити спостерігати характерні риси тварин; формувати вміння вибирати формат, виконувати динамічну і статичну композиції, компонувати фі...
3576. Звук в. Позначення його буквою ве. Читання складів, слів, речень 43 KB
  Звук в. Позначення його буквою ве. Читання складів, слів, речень Мета: Ознайомити учнів з артикуляцією звука [в], позначенням його буквою «ве», вчити читати склади, слова з нею, удосконалювати навички складання речень та їх читання. Збагачувати слов...
3577. Закріплення букви і. Звуко-буквений аналіз слів. Читання речень 41.5 KB
  Закріплення букви «і». Звуко-буквений аналіз слів. Читання речень. Мета: Закріпити звукове значення букви «і», удосконалювати навички звуко-буквеного аналізу слів, вміння читати склади, слова з буквою «і». Продовжувати вчити складати та читати речен...
3578. Цей день без куріння. Виховний захід 138.5 KB
  Показати негативний вплив куріння на стан здоров’я підлітків; формувати активну життєву позицію учнів, допомагати підліткам зробити правильний вибір відносно тютюнокуріння. Перший етап – цілеспрямування (постановка мети і задач). Вчи...
3579. Розвиток комунікативних умінь і навичок педагогів 68 KB
  Розвиток комунікативних умінь і навичок педагогів Протягом останніх років психологічні служби області набули більш високого професійного рівня. Це пояснюється великою потребою знань про закономірності та особливості розвитку дітей, необхідністю орга...
3580. Психологічний аспект використання основних методів і прийомів тренування пам’яті, спостережливості, розумової активності 52.5 KB
  Психологічний аспект використання основних методів і прийомів тренування пам’яті, спостережливості, розумової активності Проведення заняття з учнями Мета: ознайомити учнів із поняттями «візуаліст», «аудіаліст» та «кінестетик», які визначають тр...
3581. У математиці своя мова – це формули 55.5 KB
  У математиці своя мова – це формули Мета: забезпечити творче застосування знань, умінь, навичок учнів у нестандартних умовах; розвивати логічне мислення, формувати самостійність, творчу активність, ініціативу, вміння швидко приймати рішення, ви...