Модели и структуры данных




Описание работы:



Описание работы:

  • П.1 - осуществляется поиск места для вставки элемента. Производится последовательный рекурсивный вызов процедурой самой себя. При нахождении места для вставки к дереву добавляется новый элемент с помощью процедуры ВСТАВИТЬ_ЭЛЕМЕНТ.
  • П.2 - Если такой элемент уже существует в дереве, то выводится сообщение об этом и выполнение процедуры завершается.
  • П.3 (П.5) - производит изменение показателей сбалансированности после включения нового элемента в левое (правое для П.5) поддерево.
  • П.4 (П.6) - производит балансировку дерева путем перестановки указателей - т.е. LL- и LR-повороты (RR- и RL-повороты в П.6)
  • П.7 - с помощью рекурсивных вызовов в стеке запоминается весь путь до места создания новой вершины. В П.7 производится обратный обход дерева, корректировка всех изменившихся показателей сбалансированности (в П. 3 и 5) и при необходимости балансировка. Это позволяет производить правильную балансировку, даже если критическая вершина находится далеко то места вставки.








Содержание    Назад    Вперед