           7. Поиск по бинарным деревьям

           Явное использование структуры данных в виде бинарного дерева поз-
        воляет эффективно производить операции не только поиска, но и встав-
        ки новых элементов, а также удаления. В структуре дерева каждый эле-
        мент имеет кроме ключа K[i] две связи: LL[i] - указатель (индекс) на
        левое  поддерево  и  RL[i] - указатель (индекс) на правое поддерево.
        Пустой указатель @ соответствует указателю на конечный узел  -  лист
        дерева.

           7.1. Поиск по бинарному дереву.

           Схема алгоритма соответствует двум операциям:  поиску (удачному и
        неудачному) и включению в дерево нового элемента. Для различения ре-
        жима  включения  при неудачном поиске и режима просто поиска в алго-
        ритме используется условие "Поиск?".  В программе этот режим опреде-
        ляется при ее запуске в диалоге с пользователем. Логическая перемен-
        ная f служит для запоминания последней пустой связи, которая привела
        к неудачному поиску.  Значение false соответствует левой пустой свя-
        зи, true - правой. Схема алгоритма поиска и, возможно, вставки имеет
        следующий вид. Функция avail() выделяет место в  памяти  для  нового
        элемента в случае вставки.

            p = индекс элемента, стоящего в корне дерева
         ╔═════════════>════════╬═══════════<════════════════════════════╗
         ║                     if(X<K[p])                                ║
         ║   then               ║     else                               ║
         ║   ╔════════<═════════╩══════>════╗                            ║
         ║   ║                            if(X=K[p]) Конец:удачный поиск ║
         ║ if(LL[p]╪@) p=LL[p]═>═╗        if(RL[p]╪@) p=RL[p]══════>═════╝
         ╚═══════════════════════╝        else f=true ═>╗
           else f=false ═════════════>═══╦════<═════════╝         then
                                      if(Поиск?) ══════>═════════════════╗
                                      q=avail();                         ║
                                      K[q]=X;                            ║
                                      LL[q]=RL[q]=@;                     ║
                                      if(f) RL[p]=q else LL[p]=q;        ║
                                      p=q;                               ║
                                      Конец: вставка элемента            ║
                                      Конец:неудачный поиск═════════════<╝

           Время работы алгоритма t примерно оценивается формулой:
                   t=a*lgN
        где a - неизвестная константа, зависящая от программной реализа-
        ции алгоритма, а также от результата поиска: удачен-неудачен.
           7.2. Удаление из бинарного дерева

           Предполагается, что дерево создано алгоритмом 7.1. Узел p являет-
        ся предком удаляемого узла q.  В алгоритме  используется  переменная
        pq,  которая  является указателем на поле той связи узла p,  которая
        указывает на q.  Функция ЗНАЧ(pq) используется в смысле самого  поля
        связи, на которое указывает pq. Алгоритм имеет вид.

                                 t=q;
                                 if(RL[t]=@)
                 then             ║    else
                ╔═══════════<═════╩═══>══╗
           ЗНАЧ(pq)=LL[t];               ║
                ║                     if(LL[t]=@)
                ║             then       ║    else
                ║            ╔════════<══╩══>════╗
                ║      ЗНАЧ(pq)=RL[t];       r=RL[t];
        ╔══<════╩═══<════════╝               if(LL[r]=@)
        ║                  then                  ║   else
        ║       ╔════════════════<═══════════════╩═══>══╗
        ║ LL[r]=LL[t];ЗНАЧ(pq)=r;                      s=LL[r]; ══<══════╗
        ║       ║                                      if(LL[s]╪@) r=s ═>╝
        ╠══<════╝                                      LL[s]=LL[t];
        ║                                              LL[r]=RL[s];
        ║                                              RL[s]=RL[t];
        ╚═══>═══════════════>═══╦═<═╗                  ЗНАЧ(pq)=s;
                                ║   ╚════════════════<═════╝
                        ┌───────╨──────────┐
                        │ Освободить память│
                        │ узла t           │
                        └──────────────────┘
                          Конец алгоритма

           7.3. Построение оптимальных бинарных деревьев поиска

           Деревья, получаемые данным алгоритмом, минимизируют цену дерева -
        взвешенную длину путей в дереве.  Весами узлов являются частоты (ве-
        роятности) P[1] P[2] ...  P[N] поиска данного ключа,  одного из K[1]
        K[2] ... K[N] (значения ключей упорядочены в порядке возрастания)
        или частоты (вероятности) попадания искомого значения Х в промежуток
        между соседними значениями ключей Q[0] Q[1] ... Q[N]. Узлы занумеро-
        ваны от 1 до N.
           Алгоритм состоит из двух этапов. На первом этапе вычисляется мат-
        рица размером (N+1)*(N+1), каждая строка и столбец которой соответс-
        твует узлу  (строка и столбец 0 соответствуют внешнему узлу - листу,
        отражающему значения ключа поиска меньше наименьшего K[1]). В каждом
        элементе  матрицы с индексами [i,j] хранятся три параметра оптималь-
        ного поддерева,образованного множеством узлов от узла i до  узла  j.
        R[i,j]  есть корень оптимального поддерева,  W[i,j] есть сумма весов
        узлов,  C[i,j] есть цена поддерева. Из оптимальных поддеревьев в ре-
        зультате составляется оптимальное дерево.

        for i=0 to N
        ┌──────────────────────────────────────────────────────────┐
        │R[i,i]=i;                   ┌────────────────────────────┐│
        │W[i,i]=Q[i]; for j=i+1 to N │ W[i,j]=W[i,j-1]+P[j]+Q[j]; ││
        │C[i,i]=0;                   └────────────────────────────┘│
        └──────────────────────────────────────────────────────────┘
                     ┌──────────────────────────────┐
        for j=1 to N │C[j-1,j]=W[j-1,j];R[j-1,j]=j; │
                     └──────────────────────────────┘
        for d=2 to N
        ┌─────────────────────────────────────────────────────────────┐
        │  for j=d,N                                                  │
        │ ┌────────────────────────────────────────────────────────┐  │
        │ │ i=j-d; v=R[i,j-1]; min=C[i,v-1];kmin=v;                │  │
        │ │ for k=v to R[i+1,j]                                    │  │
        │ │ ┌───────────────────────────────────────────────────┐  │  │
        │ │ │                          ┌──────────────────────┐ │  │  │
        │ │ │if(C[i,k-1]+C[k,j] < min) │ min= C[i,k-1]+C[k,j] │ │  │  │
        │ │ │                          │ kmin=k               │ │  │  │
        │ │ │                          └──────────────────────┘ │  │  │
        │ │ └───────────────────────────────────────────────────┘  │  │
        │ │  C[i,j]=min+W[i,j];                                    │  │
        │ │  R[i,j]=kmin;                                          │  │
        │ └────────────────────────────────────────────────────────┘  │
        └─────────────────────────────────────────────────────────────┘
           На втором этапе на основе этой матрицы  формируется  традиционная
        структура данных для представления дерева.
           Каждый узел i имеет три поля:  значение ключа K[i], ссылку на но-
        мер узла - корня левого поддерева LL[i], ссылку на номер узла - кор-
        ня правого поддерева RL[i].  Ссылка @ есть пустая ссылка на лист де-
        рева. В  схеме  используются две функции: A(v) - адрес или индекс в
        массиве некоторой переменной v  и  ЗНАЧ(u) - значение переменной по
        адресу u. uk - переменная,  которая имеет  значение  номера корнево-
        го  узла  оптимального дерева.  Стек используется для хранения троек
        (u,i,j),   соответствующих  поддеревьям,  где u - адрес или индекс в
        массиве корня данного поддерева, i,j - начальный и  конечный индексы
        поддерева. Схема второго этапа имеет следующий вид.

                   i=0; j=N; u=A(uk); Опустошить стек.
                          ║
                          ╠════════<════════════════════════════════╗
                         v=R[i,j];                                  ║
                         ЗНАЧ(u)=v;                                 ║
                         if(j>v)                                    ║
             then         ║                   else                  ║
             ╔══════<═════╩═════>═══════════════════╗               ║
             ║                                      ║               ║
         u=A(RL[v]);                              ЗНАЧ(u)=j;        ║
         (u,v+1,j) => в стек;                       ║               ║
             ╚══════>═════╦══════════════<══════════╝               ║
                       u=A(LL[v]);                                  ║
                       j=v-1;                                       ║
                       if(j>i) ════>═══════════════════════════════>╣
                            ┌──────────────────────────────────┐    ║
                       else │if(i=0) ЗНАЧ(u)=@ else ЗНАЧ(u)=i; │    ║
                            └──────────────────────────────────┘    ║
                      if(стек не пуст) извлечь из стека (u,i,j);═══>╝
                      Конец алгоритма.

           Для примера рассмотрим построение оптимального дерева из 6  узлов
        со следующими частотами P и Q.
        ┌────┬────┬────┬────┬────┬────┬────┬────┐
        │  i │ 0  │  1 │ 2  │  3 │ 4  │ 5  │ 6  │
        ├────┼────┼────┼────┼────┼────┼────┼────┤
        │P[i]│ -  │  9 │ 1  │  4 │ 1  │ 3  │ 2  │
        ├────┼────┼────┼────┼────┼────┼────┼────┤
        │Q[i]│ 0  │  0 │ 0  │  0 │ 0  │ 0  │ 0  │
        └────┴────┴────┴────┴────┴────┴────┴────┘

           Работа алгоритма представлена в виде матрицы. В каждой клетке ма-
        трицы указано значение R[i,j],  W[i,j],  C[i,j] и, возможно, пределы
        значений индекса k. Cимволом ° отмечено то значение k, которое, взя-
        тое в качестве корня, дает оптимальное поддерево, так как ему  соот-
        ветствует минимальная  цена  С[i,j]=W[i,j]+C[i,k-1]+C[k,j]. Просмотр
        клеток ведется по диагоналям, по возрастанию значений d=0,1,...,6 .

            0     1       2          3          4          5         6
         ┌─────┬─────┬──────────┬──────────┬──────────┬──────────┬─────────┐
         │R 0  │  1  │  1       │ 1        │ 1        │ 1        │ 3       │
        0│W 0  │  9  │  10      │ 14       │ 15       │ 18       │ 20      │
         │C 0  │  9  │  10+1=11 │ 14+6=20  │ 15+8=23  │ 18+15=33 │ 20+20=40│
         │     │     │  k=°1,2  │ k=°1,2,3 │ k=°1,2,3 │ k=°1,2,3 │ k=1,2,°3│
         ├─────┼─────┼──────────┼──────────┼──────────┼──────────┼─────────┤
         │     │  1  │  2       │ 3        │ 3        │ 3        │ 3(5)    │
        1│     │  0  │  1       │ 5        │ 6        │ 9        │ 11      │
         │     │  0  │  1       │ 5+1=6    │ 6+2=8    │ 9+6=15   │ 11+10=21│
         │     │     │          │ k=2,°3   │ k=°3     │ k=°3     │ k=°3,4,5│
         ├─────┼─────┼──────────┼──────────┼──────────┼──────────┼─────────┤
         │     │     │  2       │ 3        │ 3        │ 3        │ 5       │
        2│     │     │  0       │ 4        │ 5        │ 8        │ 10      │
         │     │     │  0       │ 4        │ 5+1=6    │ 8+5=13   │ 10+8=18 │
         │     │     │          │          │ k=°3,4   │ k=°3,4,5 │ k=3,4,°5│
         ├─────┼─────┼──────────┼──────────┼──────────┼──────────┼─────────┤
         │     │     │          │ 3        │ 4        │ 5        │ 5       │
        3│     │     │          │ 0        │ 1        │ 4        │ 6       │
         │     │     │          │ 0        │ 1        │ 4+1=5    │ 6+3=9   │
         │     │     │          │          │          │ k=4,°5   │ k=5     │
         ├─────┼─────┼──────────┼──────────┼──────────┼──────────┼─────────┤
         │     │     │          │          │ 4        │ 5        │ 5       │
        4│     │     │          │          │ 0        │ 3        │ 5       │
         │     │     │          │          │ 0        │ 3        │ 5+2=7   │
         │     │     │          │          │          │          │ k=°5,6  │
         ├─────┼─────┼──────────┼──────────┼──────────┼──────────┼─────────┤
         │     │     │          │          │          │ 5        │ 6       │
        5│     │     │          │          │          │ 0        │ 2       │
         │     │     │          │          │          │ 0        │ 2       │
         ├─────┼─────┼──────────┼──────────┼──────────┼──────────┼─────────┤
         │     │     │          │          │          │          │ 6       │
        6│     │     │          │          │          │          │ 0       │
         │     │     │          │          │          │          │ 0       │
         └─────┴─────┴──────────┴──────────┴──────────┴──────────┴─────────┘

           Время работы алгоритма t примерно оценивается формулой:
                   t=a*N¤
        где a - неизвестная константа, зависящая от программной реализа-
        ции алгоритма.

           7.4. Цифровой поиск по дереву

           В этом алгоритме предполагается,  что искомый ключ Х представляет
        собой последовательность бит. Функция БИТС(Х) возвращает старший бит
        ключа Х.  Функция СДВГЛ(Х) сдвигает Х на 1 бит влево,добавляя справа
        0. Схема алгоритма имеет вид.
                          p = индекс элемента, стоящего в корне дерева
                          X1=X;
                            ╠═══════════════<═════════════════════════╗
                            ║                                         ║
                      if(X=K[p]) Конец: удачный поиск;                ║
                      b=БИТС(X1); K1=СДВГЛ(X1);                       ║
                      if(b)                                           ║
              0         ║              1                              ║
             ╔════════<═╩═════════════>══╗                            ║
             ║                          if(RL[p]╪@) p=RL[p]═>═╦═>═════╝
           if(LL[p]╪@) p=LL[p]═>══════>══╬══════>═════════════╝
             ║                           ║
             ╚════>═════╦══════<═════════╝
                       if(Поиск?) ══════>═════════════════╗
                       q=avail();                         ║
                       K[q]=X;                            ║
                       LL[q]=RL[q]=@;                     ║
                       if(b=0) LL[p]=q else RL[p]=q;      ║
                       p=q;                               ║
                       Конец:вставка или неудачный поиск;<╝

        7.5. Цифровой поиск для длинных ключей, хранимых в
             текстовом массиве (Патриция)

           Название Патриция(Patricia) произошло  от  сокращения:  Practical
        Algorithm To Retrieve Information Coded In Alphanumeric.  Ключи,  по
        которым производится поиск, имеют вид текстовых фраз различной длины
        и хранятся в массиве TEXT. В узлах дерева поиска хранятся лишь ссыл-
        ки на TEXT, которые будем обозначать через KEY(p), где p - номер уз-
        ла.  Поиск выполняется путем последовательного просмотра битов ключа
        поиска Х и "путешествия" по дереву в  зависимости  от  их  значения.
        Каждый узел p дерева кроме ссылки KEY(p) на массив TEXT содержит:
        - ссылки на левое LL(p) и правое RL(p) поддерево;
          -  битовые признаки LTAG(p) и RTAG(p) для LL(p) и RL(p)  соответс-
          твенно,  обозначающие окончание поиска:  если признак равен 0,  то
          ссылка LL(p) или RL(p) не пуста и имеет обычный  смысл;  если при-
          знак  равен  1,  то  ссылка выполнена на одного  из  предков этого
          узла или на него самого и обозначает необходимость окончания  про-
          смотра дерева и обращения к массиву TEXT из этого узла;
          -  значения SKIP(p), обозначающие количество бит в аргументе поис-
          ка, которые нужно пропустить перед сравнением в следующем узле, то
          есть номер следующего бита, по которому выполняется сравнение,есть
          не j+1 ( j - номер бита,  по которому выполнялось сравнение в дан-
          ном узле p),  а j+SKIP(p). Данный признак позволяет удалить из де-
          рева  узлы,  из которых ведет только одна ссылка,  а другая пуста.
          Начальный узел поиска назван  "голова"  (head),  узел  head  имеет
          только  левую ссылку LL(head) и ccылку на массив TEXT - KEY(head).
          Через n обозначено количество бит в аргументе поиска Х. Через Х[i]
          обозначим  i-й бит аргумента Х,  через TEXT[i] - i-й бит в массиве
          TEXT, считая от ссылки на него из какого-либо узла. Будем рассмат-
          ривать  два  алгоритма:  поиска (алгоритм П) и вставки новых узлов
          (алгоритм В).  Второй алгоритм как составную часть использует пер-
          вый. Схема алгоритма П имеет вид.
x                    p=head; j=0;
           ╔══════>════════════╗                         ╔═══════════<═══╗
           ║            q=p; p=LL(q);                 q=p;p=RL(p);       ║
           ║            if(LTAG(q)=1)                 if(RTAG(q)=1)      ║
           ║        then    ║        else     else       ║   then        ║
           ║       ╔══════<═╩═════════>═══╦════<═════════╩═════>══╗      ║
           ║       ║                   j=j+SKIP(p)                ║      ║
           ║       ║                   if(j>n) ═════>═════════════╣      ║
           ║       ║                   if(X[j]=1)                 ║      ║
           ║       ║                   if(X[j])                   ║      ║
           ║       ║                 0    ║    1                  ║      ║
           ╚═══════╬═════════════════<════╩════>══════════════════╬══>═══╝
                   ╚══════>═══════════════╦═════════<═════════════╝
                              for i=KEY(p) to KEY(p)+n-1
                              ┌────────────────────┐
                              │  if(TEXT[i]╪X[i] ══╪═>══╗
                              └───╥────────────────┘    ║
                                  ║                  l=i-KEY(p)
                                  ║                     ║
                             Конец: удачный        Конец: неудачный
                                    поиск                 поиск

        Cхема алгоритма В имеет вид.

      ┌────────────────────────────────────────────────────────────────┐
      │ Начальный шаг: выполняется при первом  обращении к алгоритму В.│
      ├────────────────────────────────────────────────────────────────┤
      │ Занести в массив TEXT с индекса 1 первый аргумент поиска       │
      │ KEY(head)=1; LL(head)=head; LTAG(head)=1;                      │
      └────────────────────────────────────────────────────────────────┘
        Следующие шаги выполняются при каждом последующем входе.
      ┌──────────────────────────────────────────────────────────────────┐
      │Выполнить алгоритм П с выходом по неудачному поиску.              │
      │Уменьшить длину ключа Х с n до величины l - числа совпавших при   │
      │поиске бит. Снова выполнить алгоритм П с выходом на этот раз по   │
      │удачному поиску.                                                  │
      └────────────────────╥─────────────────────────────────────────────┘
                     r=AVAIL() - память для нового узла r
                     if(p есть левая ссылка для q)
           then            ║                    else
        ╔════════════<═════╩════════>══════════════════════╗
     LL(q)=r;                                          RL(q)=r;
     t=LTAG(q);                                        t=RTAG(q);
     LTAG(q)=0;                                        RTAG(q)=0;
        ╚══════════════════╦═══════════════════════════════╝
                       b = (l+1)-й бит Х
                        if(b)
             1             ║                            0
           ╔═══════════════╩════════════════════════════════╗
     RTAG(r)=1;                                       LTAG(r)=1;
      RL(r)=r;                                         LL(r)=r;
      LTAG(r)=t;                                       RTAG(r)=t;
      LL(r)=p;                                         RL(r)=p;
           ╚═══════════════╦════════════════════════════════╝
                         if(t)
             0             ║                            1
           ╔═══════════════╩════════════════════════════════╗
     SKIP[r]=(l+1)-j;                              SKIP[r]=(l+1)-(j-SCIP[p]);
           ║                                       SKIP[p]=j-(l+1);
           ╚═══════════════╦════════════════════════════════╝
                  Конец: в дерево включена
                  новая вершина r.

        Рассмотрим пример работы алгоритмов П и В. Пусть в дерево Патриции
        нужно последовательно включить следующие элементы: '0 ','А ','Б ','С '.
        В качестве конечного символа в каждом заказе на поиск используется
        символ пробела. В 16-ричном и двоичном виде заказы на поиск имеют
        следующий вид:
        '0 '= 4820=0100 1000 0010 0000   Шаг 1
        'А '= 8020=1000 0000 0010 0000   Шаг 2
        'Б '= 8120=1000 0001 0010 0000   Шаг 3
        'С '= 9120=1001 0001 0010 0000   Шаг 4
        Шаг 1. Х='0 '
        Состояние дерева  после  шага  1.  Дерево состоит только из головной
        вершины,  в которой определены ссылки: на TEXT: KEY(h)=1 (на рисунке
        показан непосредственно текст '0 ', на который указывает ссылка), на
        левое поддерево: LL(h)=h и LTAG(h)=1.

                              ┌>'0 '
                            ┌─┴─┐
                        ┌──>┤ h │
                        │   └─┬─┘
                        └──<──┘

          Состояние дерева после шага 2.      Состояние дерева после шага 3.
          X='А '                              X='Б '
                       ┌>'0 '                              ┌>'0 '
                     ┌─┴─┐                               ┌─┴─┐
         ┌──────────>┤ h │                   ┌──────────>┤ h │
         │           └─╥─┘                   │           └─╥─┘
         │     ╔═══════╝                     │     ╔═══════╝
         │     ║ ┌>'А '                      │     ║ ┌>'А '
         │ ┌───╨─┴┐                          │ ┌───╨─┴┐
         │ │   1  │                        ┌─┼>┤   1  │
         │ │SKIP=1├<┐                      │ │ │SKIP=1│
         │ └─┬─┬──┘ │                      │ │ └─┬─╥──┘
         └──<┘ └>───┘                      │ └───┘ ╚════════╗
                                           │                ║ ┌>'Б '
                                           │            ┌───╨─┴┐
                                           │            │   2  │
                                           │            │SKIP=7├<┐
                                           │            └─┬─┬──┘ │
                                           └─────────────<┘ └>───┘
        На рисунке одинарными линиями показаны ссылки с TAG=1, а  двойными -
        ссылки с TAG=0.

        Состояние дерева после шага 4. X='С '

                          ┌>'0 '
                        ┌─┴─┐
            ┌──────────>┤ h │
            │           └─╥─┘
            │     ╔═══════╝
            │     ║ ┌>'А '
            │ ┌───╨─┴┐
         ┌──┼>┤   1  │
         │  │ │SKIP=1│
         │  │ └──┬─╥─┘
         │  └──<─┘ ╚═>═════╗
         │                 ║ ┌>'C '
         │             ┌───╨─┴┐
         │             │   3  │
         │             │SKIP=3├<─┐
         │             └──╥─┬─┘  │
         │        ╔═<═════╝ └─>──┘
         │        ║ ┌>'Б '
         │    ┌───╨─┴┐
         │    │   2  ├<──┐
         │    │SKIP=4│   │
         │    └─┬──┬─┘   │
         └────<─┘  └──>──┘
