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



         

Сбалансированные деревья - часть 9


h=true _то . вызов процедуры Balance_R; перейти к п.2; _иначе .: KEY(q)=KEY(r); r=RPTR(r); h=true; 2. Выход. _Конец . Del;

ОПИСАНИЕ РАБОТЫ:

  • П.1 - производится рекурсивный поиск самого правого элемента в поддереве. Если элемент найден, то он ставится на место удаленного элемента, устанавливается флаг удаления, и осуществляется выход. Если установлен флаг удаления элемента, то вызывается процедура балансировки.
  • П.5 - т.к. эта процедура рекурсивная, то производится возврат в место предыдущего вызова, либо в вызывающую процедуру (Delete).

    АЛГОРИТМ ПРОЦЕДУРЫ Balance_L.

    Дано: бинарное дерево, в левом поддереве которого было произведено удаление элемента.

    Задан: указатель p на место удаленного элемента.

    Алгоритм производит балансировку бинарного дерева и корректировку показателей сбалансированности.

    P1 и P2 - вспомогательные указатели, b1 и b2 - вспомогательные показатели сбалансированности.

    _Начало . Balance_L: 1. Корректировка показателей сбалансированности: _Если . BAL(p)=-1 _то .: BAL(p)=0; { перевеш. -> сбалансир. } _конец _Если . BAL(p)=0 _то .: BAL(p)=1; h=false; { сбалансир. -> перевеш. } _конец p1=RPTR(p); b1=BAL(p1); { BAL(p)=1 - критическая. } 2. Однократный RR-поворот : _Если . b1 >= 0 _то .: _Если . p=ROOT _то . ROOT=RPTR(p); _ .{ перенос корня } RPTR(p)=LPTR(p1); LPTR(P1)=p; { корректировка показателей сбалансированности } _если . b1=0 _то .: BAL(p)=1; BAL(p1)=-1; h=false; _иначе .: BAL(p)=0; BAL(p1)=0; p=p1; _конец 2. Двукратный RL-поворот : _если . b1 < 0 _если . p1=ROOT _то . ROOT=RPTR(p); { перенос корня } p2=LPTR(p1); b2=BAL(p2); LPTR(p1)=RPTR(p2); RPTR(p2)=p1; RPTR(p)=LPTR(p2); LPTR(p2)=p; { корректировка показателей сбалансированности } _если . b2=1 _то . BAL(p)=-1 _иначе . BAL(p)=0; _если . b2=-1 _то . BAL(p1)=1 _иначе . BAL(p1)=0; p=p2; BAL(p2)=0; _конец _Конец . Balance_L;

    ОПИСАНИЕ РАБОТЫ АЛГОРИТМА:

  • П.1 - если вершина не является критической, то производится изменение показателей сбалансированности. Если вершина критическая - создаются вспомогательные указатели.
  • П.2 и 3 - производят балансировку дерева однократным RR(п.2) и двукратным RL- (п.3) поворотами и изменение показателей сбалансированности.




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