C.Ю.Соловьев

Методические материалы
по курсу
"Алгоритмы и алгоритмические языки"

Программа курса
Программирование в машинных кодах
Примеры-1
Примеры-2
Пример "большой" программы
Нисходящее программирование
Ссылочные типы
Структуры данных
Очереди и стеки
Деревья поиска
AVL-деревья
Таблицы
Хеш-таблицы
Динамические страницы

Деревья поиска

(* Напоминание.                                                *)
(* Двоичное дерево (Бинарное дерево) - дерево, в котором       *)
(* каждая вершина имеет 0, 1 или 2 непосредственных потомков.  *)
(*                                         Конец напоминания.  *)
(* Подход к представлению деревьев на языке Паскаль:           *)
(* -1- вершина - запись в динамической памяти;                 *)
(* -2- ребро (a,b) - в записи вершины a есть поле,             *)
(*                   содержащее указатель на запись b.         *)
(* Соглашение.                                                 *)
(* С каждой вершиной дерева связана информация (ключ),         *)
(* однозначно идентифицирующая эту вершину.                    *)
(* Ключи должны допускать сравнения на больше-меньше-равно.    *)
(* В Паскале ключами  могут быть: integer, char, строки, real  *)
(* (с оговорками) и др.                                        *)
(* Считаем, что ключ имеет целый тип (integer).                *)
 
type    info = record (* заглушка *) end;
     pRecord = ^info;
     pDoTree = ^DoTree;
      DoTree = record   Key : integer;  (* ключ *)
                       Left : pDoTree;  (* указатель на левое  поддерево *)
                      Right : pDoTree;  (* указатель на правое поддерево *)
                       REFF : pRecord;  (* ассоциированная информация    *)
               end;
(* NB. В связи с выбранной реализацией вершин появляется        *)
(*     понятия правого и левого поддеревьев (каждой) вершины.   *)
(*                                                              *)
(* Пусть R : DoTree - вершина бинарного дерева.                 *)
(* R - лист, если R.Left =  nil, R.Right =  nil;                *)
(* R   имеет одного (левого)  непосредственного потомка,        *)
(*           если R.Left <> nil, R.Right =  nil;                *)
(* R   имеет одного (правого) непосредственного потомка,        *)
(*           если R.Left =  nil, R.Right <> nil;                *)
(* R   имеет двух непосредственных потомков,                    *)
(*           если R.Left <> nil, R.Right <> nil;                *)
(*                                                              *)
(* Обозначим:                                                   *)
(* LK(R) - множество ключей, встречающихся в левом  поддереве R *)
(* RK(R) - множество ключей, встречающихся в правом поддереве R *)
(* Дерево поиска - бинарное дерево, для каждой вершины которого *)
(*                     справедливо:  x < R.Key < y,             *)
(*                 для всех x из LK(R)  и  для всех y из RK(R). *)
(*                                                              *)
(* Основные операции:                                           *)
(* -1- поиск вершины по известному ключу;                  Find *)
(* -2- включить   в дерево вершину с заданным ключом.      Form *)
(* -3- исключить из дерева вершину с заданным ключом;      Kill *)
(*                                                              *)
(* ///////////////////////// Пусть //////////////////////////// *)
 
   program ...;
   Type    info = record (* заглушка *) end;
        pRecord = ^info;
        pDoTree = ^DoTree;
         DoTree = record   Key : integer;  (* ключ *)
                          Left : pDoTree;  (* указатель на левое  поддерево *)
                         Right : pDoTree;  (* указатель на правое поддерево *)
                          REFF : pRecord;  (* ассоциированная информация    *)
                  end;
   ...
   Var T : pDotree; (* Дерево *)
   ...
Мы здесь
   ...
   begin   T:=nil;  (* Сначала дерева нет *)
           ...
   end.
(* Find : поиск в дереве вершины с ключом K.                    *)
(*        Find(T,K) = nil, если такой вершины в дереве нет,     *)
(* иначе  Find(T,K) = ссылка на вершину с ключом K.             *)

function Find(X : pDoTree; K : integer) : pDoTree;
begin        if X = nil then Find:=nil
        else with X^ do
             if Key = K then Find:=X
        else if Key < K then Find:=Find(Right,K)
        else                 Find:=Find(Left ,K)   end;

(* Findm : поиск в дереве вершины с ключом K. Упрощенная версия. *)
 
function Findm(X : pDoTree; K : integer) : pDoTree;
begin    Findm:=X;                                  (* D = nil / K = Key *)
             if X <> nil then with X^ do
             if  Key < K then Findm:=Findm(Right,K)
        else if  K < Key then Findm:=Findm(Left ,K)  end;
(* Form : включить в дерево T (новую) вершину с ключом K.       *)
(*        Form(T,K) = указатель на существующую или             *)
(*                    вновь созданную вершину с ключом K.       *)
(*                 Во вновь созданной вершине REFF = nil.       *)
 
function Form(var D : pDotree; K : integer) : pDoTree;
begin   if D = nil then begin
             new(D);                                  (* Построить новую вершину *)
                 D^.Key  :=K;
                 D^.Reff :=nil;
                 D^.Left :=nil;
                 D^.Right:=nil;
           Form:=D
        end;
        with D^ do
             if Key = K then Form:=D
        else if Key < K then Form:=Form(Right,K)
        else                 Form:=Form(Left ,K)  end;
(* Kill : удалить в дереве поиска вершину с ключом K.           *)
(*                                                              *)
(* Подход: Если в дереве найдется вершина с ключом K,           *)
(*         то (из общих соображений) возможны 4 различных,      *)
(*            случая каждый из которых обрабатывается отдельно. *)

1, 2, 3

4.1, 4.2

procedure Kill(var D : pDoTree; K : integer);
   var Q : pDoTree;
   procedure Case41;
   begin   Q^.Key :=D^.Left^.Key;
           Q^.Reff:=D^.Left^.Reff;
           Q:=D^.Left;
           D^.Left:=D^.Left^.Left
   end;
   procedure Ki(var D : pDotree);
   begin   with D^ do
           if Right <> nil then Ki(Right) else begin
              Q^.Key :=D^.Key;
              Q^.Reff:=D^.Reff;
              Q:=D;
              D:=D^.Left
           end
   end;
begin   if D = nil then Exit;
        with D^ do
             if Key < K then Kill(Right,K)
        else if Key > K then Kill(Left ,K)
        else begin Q:=D;
                if Q^.Reff <> nil then Dispose(Q^.Reff);
                if       (Left = nil) and
                        (Right = nil) then D:=nil       (* 3   *)
           else if        Left = nil  then D:=Right     (* 1   *)
           else if       Right = nil  then D:=Left      (* 2   *)
           else if Left^.Right = nil  then Case41       (* 4.1 *)
           else                            Ki(Left);    (* 4.2 *)
           Dispose(Q)
        end                                         end;
(* Упрощения                                                    *)
(* 1. Случай 3: if (Left = nil) and (Right = nil) then D:=nil   *)
(* покрывается: if  Left = nil then D:=Right  при Right = nil   *)
(*    Поэтому отдельно случай 3 можно не рассматривать          *)
(*                                                              *)
(* 2. Процедура Case41 повторяет операторы из процедуры Ki      *)
(*    для случая D есть D^.Left                                 *)
(*    Введем в процедуре параметр и получим:                    *)

procedure Kill(var D : pDoTree; K : integer);
   var Q : pDoTree;
   procedure Case41(var D : pDoTree);
   begin   Q^.Key :=D^.Key;
           Q^.Reff:=D^.Reff;
           Q:=D;
           D:=D^.Left
   end;
   procedure Ki(var D : pDotree);
   begin   if D^.Right <> nil then Ki(D^.Right)
                              else Case41(D)
   end;
begin   if D = nil then Exit;
        with D^ do
             if Key < K then Kill(Right,K)
        else if Key > K then Kill(Left ,K)
        else begin Q:=D;
                if Q^.Reff <> nil then Dispose(Q^.Reff);
                if        Left = nil then D:=Right      (* 1   *)
           else if       Right = nil then D:=Left       (* 2   *)
           else if Left^.Right = nil then Case41(Left)  (* 4.1 *)
           else                           Ki(Left);     (* 4.2 *)
           Dispose(Q)
        end                                         end;
(* Упрощения                                                    *)
(* 3. Случай 4.1:   if Left^.Right = nil then Case41(Left)      *)
(*    эквивалентен: if Left^.Right = nil then Ki(Left)          *)
(*    Поэтому случаи 4.1 и 4.2 можно объединить.                *)
(*    Получим:                                                  *)
 
procedure Kill(var D : pDoTree; K : integer);
   var Q : pDoTree;
   procedure Case41(var D : pDoTree);
   begin   Q^.Key :=D^.Key;
           Q^.Reff:=D^.Reff;
           Q:=D;
           D:=D^.Left
   end;
   procedure Ki(var D : pDotree);
   begin   if D^.Right <> nil then Ki(D^.Right)
                              else Case41(D)
   end;
begin   if D = nil then Exit;
        with D^ do
             if Key < K then Kill(Right,K)
        else if Key > K then Kill(Left ,K)
        else begin Q:=D;
                if Q^.Reff <> nil then Dispose(Q^.Reff);
                if  Left = nil then D:=Right      (* 1   *)
           else if Right = nil then D:=Left       (* 2   *)
           else                     Ki(Left);     (* 4   *)
           Dispose(Q)
        end                                         end;
(* Упрощения                                                    *)
(* 4. Объединим процедуры Case41 и Ki.                          *)
(*    Окончательно получим:                                     *)

procedure Kill(var D : pDoTree; K : integer);
   var Q : pDoTree;
   procedure Ki(var D : pDotree);
   begin   if D^.Right <> nil then Ki(D^.Right) else begin
              Q^.Key :=D^.Key;
              Q^.Reff:=D^.Reff;
              Q:=D;
              D:=D^.Left
           end
   end;
begin   if D = nil then Exit;
        with D^ do
             if Key < K then Kill(Right,K)
        else if Key > K then Kill(Left ,K)
        else begin Q:=D;
                if Q^.Reff <> nil then Dispose(Q^.Reff);
                if  Left = nil then D:=Right      (* 1   *)
           else if Right = nil then D:=Left       (* 2   *)
           else                     Ki(Left);     (* 4   *)
           Dispose(Q)
        end                                            end;
(*    Соглашение о скобочной записи бинарных деревьев поиска      *)
(* Дерево c корнем A и ключом nn (= A^.Key )                      *)
(* - обозначается  Tnn,       если A^.Left = nil и A^.Right = nil *)
(* - обозначается (Tnn nil Правое-Поддерево), если A^.Left  = nil *)
(* - обозначается (Tnn Левое-Поддерево nil) , если A^.Rigth = nil *)
(* - обозначается (Tnn Левое-Поддерево Правое-Поддерево),         *)
(*                            если A^.Left <> nil A^.Rigth <> nil *)
(* Примеры:  T20                                                  *)
(*          (T25 T9 nil)                                          *)
(*          (T22 (T11 T5 nil) T30)                                *)
(*          (T30 (T10 (T7 T2 T8) (T15 T11 nil)) (T40 T33 T69))    *)
(*                                                Факультативно. *)
(* List : Ввести на печать дерево X в скобочном виде.            *)
 
procedure List(X : pDoTree);
begin   if   X = nil
        then write('nil')
        else with X^ do
             if (Left  = nil) and
                (Right = nil) then write('T',Key) else begin
                write('(T',Key,' '); List(Left);
                write(         ' '); List(Right); write(')')
             end                                         end;
(*                                Конец факультативного примера. *)
(*                                             Факультативно. *)
(* BT  : функция проверки бинарных деревьев на                *)
(*       принадлежность классу деревьев поиска.               *)
(*       BT(X) = true , если X - дерево поиска.               *)
(* Подход. Использовать определение.                          *)
(*         Множества LK и RK достаточно представлять их       *)
(*         максимальными и минимальными элементами:           *)
(*         Lmin, Lmax и Rmin, Rmax соответственно.            *)
(*         Тогда в дереве поиска R:                           *)
(*         -1- выполняется: Lmax < R.Key < Rmin               *)
(*         -2- представлены ключи из диапазона [Lmin,Rmax].   *)
(* BTW - вспомогательная функция: BTW(X,Kmin,Kmax) = true,    *)
(*       если X - непустое дерево поиска; при этом            *)
(*       Kmin и Kmax - значения максимального                 *)
(*                     и минимального ключей в дереве X.      *)
 
function BTW(X : pDoTree; var Kmin,Kmax : integer) : boolean;
   var Lmin,Lmax,Rmin,Rmax : integer;
begin   BTW:=true;                     (* оптимистический подход *)
        with X^ do begin               (* NB. D <> nil *)
                if         Left  = nil      then Kmin:=Key
           else if not BTW(Left ,Lmin,Lmax) then  BTW:=false
           else if  Lmax < Key              then Kmin:=Lmin
           else                                   BTW:=false;
                if         Right = nil      then Kmax:=Key
           else if not BTW(Right,Rmin,Rmax) then  BTW:=false
           else if         Key < Rmin       then Kmax:=Rmax
           else                                   BTW:=false
        end                                              end;
 
function BT(X : pDoTree) : boolean;
   var Tmin,Tmax : integer;
begin   if X = nil then BT:=true
                   else BT:=BTW(X,Tmin,Tmax)   end;

(* Конец факультативного примера *)
(*                                                      Факультативно. *)
(* BTrees : Программа построения и модификации дерева поиска.          *)
(*          Реализация в виде пригодном для использования в Интернет;  *)
(*          метод задания параметров - POST. >> pasweb.htm              *)
(*              перем.T : указатель на корень дерева.                  *)
(*                        Первоначально T = nil                        *)
(*          Программа получает от пользователя последовательность      *)
(*          целых чисел ISQ[1..N] и обрабатывает ее по следующим       *)
(*          правилам  (K = ISQ[I]) :                                   *)
(* Если 0 < K <= 999  , то включть в T вершину с ключом K.       Form  *)
(* Если     K = 0     , то проверить корректность T.             BT    *)
(* Если -999 <= K <  0, то удалить в T вершину с ключом abs(K).  Kill  *)
(* Если 1000 <= abs(K), то найти в T вершину с ключом            Find  *)
(*                                           abs(K) mod 1000.          *)
 
program BTrees;  (* Структура программы. Полный текст >> btrees.htm *)
 
const    MSQ = 200;
 
type    info = record inf : integer end;   (* Для определенности *)
     pRecord = ^info;
     pDoTree = ^DoTree;
      DoTree = record   Key : integer;  (* ключ *)
                       Left : pDoTree;  (* указатель на левое  поддерево *)
                      Right : pDoTree;  (* указатель на правое поддерево *)
                       REFF : pRecord;  (* ассоциированная информация    *)
               end;
 
var      ISQ : array [1..MSQ] of integer;
       I,K,N : integer;
         V,T : pDoTree;                    (* Дерево *)

(* IntSeq - ввод последовательности *) procedure IntSeq(var N : integer);
(*          целых чисел ISQ[1..N]   *)                                        begin end;
(* Find : поиск в дереве            *) function  Find(    X:pDoTree;K:integer):pDoTree;
(*        вершины с ключом K        *)                                        begin end;
(* Form : включить в дерево D       *) function  Form(var D:pDoTree;K:integer):pDoTree;
(*       (новую) вершину с ключом K *)                                        begin end;
(* Kill : удалить в дереве D        *) procedure Kill(var D:pDoTree;K:integer);
(*        вершину с ключом K        *)                                        begin end;
(*   BT : функция проверки          *) function    BT(    X:pDoTree          ):boolean;
(*        бинарных деревьев         *)                                        begin end;
(* List : Ввести на печать дерево D *) procedure List(    X:pDoTree);
(*        в скобочном виде          *)                                        begin end;

begin   T:=nil;
        IntSeq(N);
        writeln('Content_type: text/html'); (* <== Обязательно *)
        writeln;                            (* <== Обязательно *)
        writeln('<html><pre>');
        writeln(' ':17,'*** Программа BTrees ***');
        writeln;
        write('ISQ[1..':10,N:3,'] = ');
        for I:=1 to N do write(ISQ[I],' '); writeln;
        writeln('Начало. T = nil':20);
        writeln;
        for I:=1 to N do begin
           K:=ISQ[I];
                if      K = 0     then write('BT(T)= ':17,BT(T))
           else if 1000 <= abs(K) then begin
                   K:=abs(K) mod 1000;
                   write('Find(T,',K:3,')    = ');
                   List(Find(T,K))
                end
           else if      0 < K     then begin
                   write('Form(T,',K:3,'); T = ');
                   V:=Form(T,K);
                   with V^ do
                   if REFF = nil then begin
                      new(REFF);
                      REFF^.Inf:=I
                   end; 
                   List(T)
                end
           else        (* K < 0 *)       begin
                   K:=abs(K);
                   write('Kill(T,',K:3,'); T = ');
                   Kill(],K);
                   List(T)
                end;
           writeln;
        end;
        writeln;
        write('Результат. T = ':17); List(T); writeln;
        writeln;  
        writeln('Конец.</pre></html>');
end.
(* Вызов btrees *)     Введите строку:     
(* Конец факультативного примера *)

Вопросы?