43960

Выбор и обоснование структуры данных для алгоритма построения AVL дерева

Доклад

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

АVL - дерево с такими же значениями, как и в узлах предыдущего дерева можно представить так. Следует заметить, что сбалансированные деревья очень эффективны для поиска.

Русский

2014-03-31

16.14 KB

5 чел.

Выбор и обоснование структуры данных для алгоритма построения AVL дерева Высотой некоторого бинарного дерева является максимальный уровень его листьев. Баланс некоторого узла определяется как высота его левого поддерева минус высота его правого поддерева.

Дерево называется сбалансированным тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1.

АVL - дерево с такими же значениями, как и в узлах предыдущего дерева можно представить так. Следует заметить, что сбалансированные деревья очень эффективны для поиска. Предположим у нас сбалансированное дерево и упорядоченное бинарное дерево, которое вырождено, оба эти дерева содержат 10000 узлов. Так, например, упорядоченном бинарном дереве следует просмотреть 9999 уровней дерева прежде, чем он найдет самый крайний правый узел, а сбалансированном дереве 8 уровней.

Возможны 3 случая:

  1. hL = hR: L и R становятся неравной высоты, но критерий сбалансированности не нарушается
  2. hL < hR: L и R приобретают равную высоту, т.е. сбалансированность даже улучшается
  3. hL > hR: критерий сбалансированности нарушается, и дерево нужно трансформировать, такая перестройка называется поворотом.

Поворот должен удовлетворять следующим требованиям:

  1. Прохождение трансформированного дерева в симметричном порядке должно быть таким же, как и для первоначального дерева (т.е. трансформированное дерево должно оставаться деревом бинарного поиска)
  2. Трансформированное дерево должно быть сбалансированным

Одинарный поворот вправо происходит тогда, когда родительский узел Р и его левый сын LC начинают перевешивать влево после включения узла в позицию X. В результате такого поворота LC замещает своего родителя, который становится правым сыном. Бывая правое поддерево узла LC (ST) присоединяется к Р в качестве левого поддерева. Это сохраняет упорядоченность, так как узлы в ST больше или равны узлу LC, но меньше узла Р. Поворот уравновешивает как родителя, так и его левого сына.

Двойной поворот вправо происходит тогда, когда родительский узел (Р) становится перевешивающим влево, а его левый сын (LC) - перевешивающим вправо. NP - корень правого перевешивающего дерева узла LC. Тогда в результате поворота узел NP замещает родительский узел.

Процесс включения узла состоит из последовательности таких 3 этапов:

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

 

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

33839. Проблема человека и его прав в философии французского просвещения и педагогические воззрения 14.83 KB
  Проблема человека. Основное внимание Вольтер как философ уделяет проблеме человека в обществе. Паскаля 16231662 о ничтожестве человека это ничтожество связано с ограниченностью познавательных способностей подверженностью человека страданиям его порочностью.
33840. Немецкая классическая философия и ее представители 14.34 KB
  Своеобразным пониманием роли философии в истории человечества в развитии мировой культуры. Все представители классической немецкой философии относились к философии как к специальной системе философских дисциплин категорий идей. Классическая немецкая философия подчеркивала роль философии в разработке проблем гуманизма и предприняла попытки осмыслить человеческую жизнедеятельность. Можно определенно сказать что представители классической немецкой философии пошли вслед за просветителями XVIII в.
33841. ФИЛОСОФИЯ И. КАНТА 15 KB
  КАНТА Иммануил Кант 17241804 является родоначальником немецкой классической философии. В критическом периоде наиболее важными произведениями Канта являются Критика чистого разума Критика практического разума Критика способности суждения. Гносеологические взгляды Канта включают в себя анализ трех ступеней познания. В работе Критика практического разума Кант утверждает что объектом познания является материальная вещь находящаяся вне человека и его сознания.
33842. Марксизм. Материалистическая философия жизни 15.08 KB
  и особенно XX столетия явился марксизм. Маркс и Ф. В марксистской философии появилось новое содержание отсутствовавшее в прежних философских системах но выработанное на базе внутренней преемственности в решении ряда кардинальных проблем. Сущность нового внесенного марксизмом в философию можно проследить по следующим линиям: по функциям философии; по соотношению в ней партийности гуманизма и научности; по предмету исследования; по структуре составу и соотношению основных сторон разделов содержания; по соотношению теории и метода; по...
33843. ПРЕДПОСЫЛКИ ФИЛОСОФИИ А. ШОПЕНГАУЭРА 16.61 KB
  НИЦШЕ Французский философ Анри Бергсон 18591941 понимал жизнь в космологическом плане. Для немца Фридриха Ницше 18441900 в основе всего находится не воля к жизни как у Шопенгауэра а воля к власти. Лозунг Ницше: Живи опасно. Ницше прекрасный филолог и музыкальный импровизатор к тому же страдающий от недугов.
33844. ПОЗИТИВИСТСКАЯ КОНЦЕПЦИЯ 14.12 KB
  Последняя уничижительно объявляется позитивистами псевдознанием мимикрией под науку спекулятивным умозрительным теоретизированием не имеющим для современной науки не только никакого позитивного значения а скорее отрицательное так как философский дискурс способен только заразить науку вирусом псевдознания. Ньютон вот формулы позитивистского решения вопроса о соотношении философии и науки. Спенсер методология науки Дж.
33845. ПОНЯТИЕ ГЕРМЕНЕВТИКИ 18.05 KB
  Понимание тогда выступает как непосредственное проникновение в жизнь. Понимание собственного духовного мира достигается в процессе самонаблюдения понимание чужого мира путем вживания сопереживания вчувствования. Именно в стихии языка осуществляется понимание людьми и окружающего мира и самих себя и других.
33846. Философская антропология, Макс Шелер (1874–1928) 15.15 KB
  В центре внимания этого течения проблема человека а основная идея создание интегральной концепции человека. Философская антропология объявив себя основополагающей философской дисциплиной пытается на основе тех или иных особенностей человека найти способы постановки и решения всех философских проблем. В отличие от рационалистических учений философская антропология вовлекает в сферу исследования душевнодуховную жизнь человека эмоции инстинкты влечения что зачастую приводит к иррационализму: представители данного направления...