53495

Алгоритм вставки вершины AVL дерево. Случай одного (левого) поворота

Доклад

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

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

Русский

2014-04-01

129.41 KB

1 чел.

Алгоритм вставки вершины AVL дерево. Случай одного (левого) поворота.

Алгоритм добавления узла в AVL дерево

3 этапа:

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

Включение узла:

  1. Выполнить вставку в бинарное дерево.
  2. Если вставка в левое поддерево, то имеют место 3 случая:
  3. Если правое поддерево было длиннее, то стало сбалансированным.
  4. Если был баланс, то левое поддерево выросло, и нужно проверить балансировку выше.
  5. Левое поддерево было длинее, имеем расбалансировку.
  6. Если в правое:
  7. Если левое поддерево было длиннее, то стало сбалансированным.
  8. Если был баланс, то правое поддерево выросло, и нужно проверить балансировку выше.
  9. Правое поддерево было длинее, имеем расбалансировку.

Случай левого поворота


 

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

47009. СКРЫТЫЕ (УСЛОВНЫЕ) БАЗЫ 44.26 KB
  Применение условных скрытых баз при проектировании тем более удобно что позволяет исключить из расчетов неизбежные погрешности реальных поверхностей снижающие точность базирования. При базировании деталей собираемых узлов и обрабатываемых заготовок в подавляющем большинстве случаев используются материальные поверхности явные базы по ГОСТ 21495 76 однако и в этом случае для повышения точности базирования иногда применяются условные скрытые базы материализуемые различными устройствами отвесы коллиматоры центрирующие...
47010. Эластичность спроса и предложения. Финансовая устойчивость страховых компаний и ее составляющие 45.47 KB
  Эластичность - степень реакции одной экономической величины на изменение другой. Эластичность показывает, на сколько процентов изменяется одна переменная экономическая величина при изменении другой...
47011. Морфологическая категория лица и числа глагола 44.5 KB
  Формы лица выражают отнесенность действия к говорящему формы 1 лица к собеседнику формы 2 лица или к лицу которое не является ни говорящим ни собеседником а также к неодушевленному предмету формы 3 лица. Формы 1 и 2 л. В качестве производителя действия равно выступает как лицо формы 1 2 3 л. так и предмет формы 3 л.
47015. Электрохимическая коррозия. Механизм протекания на границе «металл – электролит» 44.54 KB
  Коррозия металлов это процесс вызывающий разрушение металла или изменение его свойств в результате химического либо электрохимического воздействия окружающей среды. Электрохимическая коррозия взаимодействие металла с корой электропроводящей средой при котором ионизация атомов металла и восстановление окислительного компта корой среды протекает не в одном акте и их скорость зависит от величины элемого потенциала металла. Термином электрохимическая коррозия объединяют следующие виды коррозионных процессов: коррозия в...