Алгоритм insert_&_balanse включения узла в сбалансированное дерево.

АЛГОРИТМ Insert_&_Balanse включения узла в сбалансированное дерево.

Дано: сбалансированное бинарное дерево с корнем ROOT.

Поля: LPTR, RPTR, KEY (ключ), BAL (показатель сбалансированности), DATA (информация).

Заданы переменные: ключ - х, информация - INF.

Алгоритм вставляет в дерево новый элемент, сохраняя сбалансированность дерева. Если элемент уже присутствует в дереве, то выводится соответствующее сообщение.

Переменная h используется как флаг, указывающий на то, что было произведено включение элемента. P - текущий указатель при перемещении по дереву, p1 и p2 - вспомогательные указатели. Count - счетчик вставленных элементов.

_Начало . Insert_&_Balanse: 1. Поиск места для вставки: _Если . x < KEY(p) _то .: _если . p=nil _то .: ВСТАВИТЬ_ЭЛЕМЕНТ и перейти к п. 3; _иначе .: p=LPTR(p) и перейти к п. 1; повторный вызов Insert_&_Balanse; _Если . x > KEY(p) _то .: _если . p=nil _то .: ВСТАВИТЬ_ЭЛЕМЕНТ и перейти к п. 5; _иначе .: p=RPTR(p) и перейти к п. 1; повторный вызов Insert_&_Balanse; 2. Совпадение: Напечатать "Элемент уже вставлен" и _конец .. 3. Изменение показателей сбалансированности: (производилась вставка в левое поддерево) _если . BAL(p)=1 _то .: BAL(p)=0; h=false; { перевеш.-> сбалансир.} перейти к п. 7 _если . BAL(p)=0 _то . BAL(p)=-1; { перевеш.-> критическ.} перейти к п. 7 4. Балансировка при возрастании левого поддерева: _если . p=ROOT _то . ROOT=LPTR(p); { перенос корневой вершины } p1=LPTR(); { вводим дополнительный указатель } _если . BAL(p1)=-1 _то .: { однокр. LL-поворот } LPTR(p)=RPTR(p1); RPTR(p1)=p; BAL(p)=0; p=p1; перейти к п. 7 _иначе .: { двукратн. LR-поворот } _если . p1=ROOT _то . ROOT=RPTR(p1); { перенос корневой вершины } p2:=RPTR(p1); RPTR(p1)=LPTR(p2); LPTR(p1)=p1; LPTR(p)=RPTR(p2); RPTR(p2)=p; (изменение показателей сбалансированности ) _если . BAL(p2)=-1 _то . BAL(p)=1 _иначе . BAL(p)=0; _если . BAL(p2)=1 _то . BAL(p1)=-1 _иначе . BAL(p1)=0; p=p2; BAL(p)=0; h=false; перейти к п. 7; 5. Изменение показателей сбалансированности: (производилась вставка в правое поддерево) _если . BAL(p)=-1 _то .: BAL(p)=0; h=false; { перевеш.-> сбалансир.} перейти к п. 7 _если . BAL(p)=0 _то BAL(p)=1; { перевеш.-> критическ.} перейти к п. 7 6. Балансировка при возрастании правого поддерева: _если . p=ROOT _то . ROOT=RPTR(p); { перенос корневой вершины } p1=RPTR(p); { вводим дополнительный указатель } _если . BAL(p1)=1 _то .: { однокр. RR-поворот } RPTR(p)=LPTR(p1); LPTR(p1)=p; BAL(p)=0; p=p1; перейти к п. 7 _иначе .: { двукратн. LR-поворот } _если . p1=ROOT _то . ROOT=LPTR(p1); { перенос корневой вершины } p2:=LPTR(p1); LPTR(p1)=RPTR(p2); RPTR(p1)=p1; RPTR(p)=LPTR(p2); LPTR(p2)=p; (изменение показателей сбалансированности ) _если . BAL(p2)=1 _то . BAL(p)=-1 _иначе . BAL(p)=0; _если . BAL(p2)=-1 _то . BAL(p1)=1 _иначе . BAL(p1)=0; p=p2; BAL(p)=0; h=false; 7. Выход. (Т.к. процедура осуществляет рекурсивный вызов самой себя в п.3, то здесь производится возврат в место предыдущего вызова. Последний выход осуществляется в вызывающую программу). _Конец . Insert_&_Balanse. 8. Алгоритм процедуры ВСТАВИТЬ_ЭЛЕМЕНТ: _Начало .: LPTR(p)=nil; RPT(p)=nil; BAL=0; { обнуление указателей } DATA=INF; KEY=x; { занесение информации } h=true; { установка флага вставки элемента } _если . count=0 { это первый элемент ? } _то . ROOT=p; count=count+1; _Конец ..