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. Пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла

 

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

83802. Виды налоговых правонарушений и ответственность за их совершение. Характеристика налоговых правонарушений 42.44 KB
  Нарушение срока постановки на учет в налоговом органе установленного НК РФ срока подачи заявления о постановке на учет в налоговом органе при отсутствии признаков налогового правонарушения влечет взыскание штрафа в размере 5 тыс. Ведение деятельности организацией или индивидуальным предпринимателем без постановки на учет в налоговом органе влечет взыскание штрафа в размере 10 от доходов полученных в течение указанного времени в результате такой деятельности но не менее 20 тыс. Нарушение срока представления сведений об открытии и закрытии...
83803. Характеристика иных видов нарушения законодательства о налогах и сборах. Соотношение налоговых правонарушений с административными проступками и преступлениями 41.46 KB
  Ответственность за налоговые правонарушения предусмотрена не только налоговым законодательством но и в Кодексе РФ об административных нарушениях в Таможенном и Уголовном кодексах РФ. Данный кодекс ввел ответственность организаций должностных лиц и граждан за правонарушения в сферах производства и оборота алкогольной продукции наличноденежного обращения государственной регистрации юридических лиц и индивидуальных предпринимателей за неприменение контрольнокассовой техники; а также дополнительно к Налоговому кодексу ответственности...
83804. Виды нарушений банком обязанностей, предусмотренных законодательством о налогах и сборах, и ответственность за их совершение 40.85 KB
  Открытие банком счета организации индивидуальному предпринимателю нотариусу занимающемуся частной практикой или адвокату учредившему адвокатский кабинет счета инвестиционного товарищества без предъявления этим лицом свидетельства уведомления о постановке на учет в налоговом органе а равно открытие счета при наличии решения налогового органа о приостановлении операций по счетам этого лица влекут взыскание штрафа в размере 20 тысяч рублей. Нарушение срока исполнения поручения о перечислении налога сбора авансового платежа пеней...
83805. Защита прав налогоплательщиков. Право на обжалование. Порядок обжалования 39.88 KB
  Статья 137 НК РФ предоставляет каждому налогоплательщику или налоговому агенту право обжаловать акты налоговых органов ненормативного характера действия или бездействие их должностных лиц если по мнению налогоплательщика или налогового агента такие акты действия или бездействие нарушают их права. Вместе с тем административный порядок не отрицает возможности обращения в последствии за защитой в суд либо предоставляется альтернативный порядок защиты прав субъектов налоговых правоотношений. Вместе с тем НК РФ устанавливает два условия...
83806. Рассмотрение жалобы и принятие решения по ней. Последствия подачи жалобы 39.84 KB
  Вышестоящий орган или вышестоящее должностное лицо в месячный срок со дня получения жалобы обязаны ее рассмотреть и принять одно из сле6дующих решений: – оставить жалобу без удовлетворения; – отменить акт налогового органа и назначить дополнительную проверку; – отменить решение и прекратить производство по делу о налоговом правонарушении; изменить решение или вынести новое решение по суще6ству обстоятельств дела. Законодательством РФ предусмотрены следующие способы судебной защиты прав налогоплательщиков: – признание неконституционным...
83807. Административный порядок защиты нарушенных прав налогоплательщиков 40.72 KB
  Вместе с тем административный порядок не отрицает возможности обращения в последствии за защитой в суд либо предоставляется альтернативный порядок защиты прав субъектов налоговых правоотношений. Вместе с тем НК РФ устанавливает два условия соблюдение которых необходимо для защиты нарушенных прав налогоплательщиков или налоговых агентов: – ненормативные акты налоговых органов а также действия бездействие должностных органов этих органов должны по мнению налогоплательщика или налогового агента нарушать их права; – нормативные правовые...
83808. Судебный порядок защиты нарушенных прав налогоплательщиков 39.8 KB
  Законодательством РФ предусмотрены следующие способы судебной защиты прав налогоплательщиков: – признание неконституционным законодательного акта полностью или в части Конституционным Судом РФ; – признание арбитражными судами или судами общей юрисдикции недействительным нормативного либо ненормативного акта налогового органа иного государственного органа или органа местного самоуправления противоречащего закону и нарушающего право и законные интересы налогоплательщика; – отмена арбитражными судами или судами общей юрисдикции не...
83809. Современные тенденции совершенствования налоговой системы Российской Федерации 39.76 KB
  Основные направления налоговой политики принимаются ежегодно Основные направления бюджетной политики на 2015 год и на плановый период 2016 и 2017 годов принимаются и рассматриваются одновременно с проектом закона о федеральном бюджете на текущий период 3 года и утверждаются на заседании правительства РФ. Политики: Поддержка инвестиций Развитие человеческого капитала Повышение предпринимательской активности.
83810. Налоговое администрирование. Структура налоговых органов РФ, их полномочия и функции 41.21 KB
  Структура налоговых органов РФ их полномочия и функции. Нет единой точки зрение на определение налогового администрирования Налоговое администрирование система управления налоговыми правоотношениями или всем комплекс налоговых отношений Титов Налог.администрирование деятельность и управление налоговых органов по осуществлению контроля за соблюдением налогового законодательства. Однако все определения условно можно объединить в 3 блока: Связанные с управлением Не связанные с управлением Опровергающие существование самого этого понятия...