7. Поиск по бинарным деревьям Явное использование структуры данных в виде бинарного дерева поз- воляет эффективно производить операции не только поиска, но и встав- ки новых элементов, а также удаления. В структуре дерева каждый эле- мент имеет кроме ключа K[i] две связи: LL[i] - указатель (индекс) на левое поддерево и RL[i] - указатель (индекс) на правое поддерево. Пустой указатель @ соответствует указателю на конечный узел - лист дерева. 7.1. Поиск по бинарному дереву. Схема алгоритма соответствует двум операциям: поиску (удачному и неудачному) и включению в дерево нового элемента. Для различения ре- жима включения при неудачном поиске и режима просто поиска в алго- ритме используется условие "Поиск?". В программе этот режим опреде- ляется при ее запуске в диалоге с пользователем. Логическая перемен- ная f служит для запоминания последней пустой связи, которая привела к неудачному поиску. Значение false соответствует левой пустой свя- зи, true - правой. Схема алгоритма поиска и, возможно, вставки имеет следующий вид. Функция avail() выделяет место в памяти для нового элемента в случае вставки. p = индекс элемента, стоящего в корне дерева ╔═════════════>════════╬═══════════<════════════════════════════╗ ║ if(X════╗ ║ ║ ║ 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│ │ │ └─┬──┬─┘ │ └────<─┘ └──>──┘