7. Поиск по бинарным деревьям
7.1. Поиск по бинарному дереву
Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.
Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем дерева.
Узел дерева, не имеющий потомков, называется листом.
Бинарное дерево может представлять собой пустое множество.
Популярным приложением бинарных деревьев, например, в технологиях баз данных является поиск требуемых элементов во входном потоке информации. Наиболее быстрый поисковый алгоритм основан на использовании бинарного дерева поиска.
Использование бинарного дерева для организации поиска позволяет сохранить эффективность на уровне бинарного поиска, обеспечивая при этом достаточно простую реализацию вставки и удаления элемента.
Для выполнения поиска бинарное дерево стоится следующим образом (предполагается, что никакие две записи не имеют одинаковых ключей):
1) Первую запись входной последовательности сопоставляют с корнем дерева.
2) Для каждой следующей записи ключ сначала сравнивается с ключом корня. Если он меньше чем ключ корня, то далее сравнивается с ключом правого потомка и т.д. до тех пор, пока потомок не будет отсутствовать. Место этого отсутствующего потомка занимает новая вершина, которой сопоставляется очередная запись.
Шаг 2 повторяется до тех пор, пока не будет просмотрена вся входная последовательность записей.
Поиск записи с заданным ключом осуществляется в точности по рассматриваемой процедуре. Сложность алгоритма поиска по дереву определяется высотой дерева и колеблется в пределах от O(Log2n) до O(n).
Схема работы:
k – ключ поиска
p – индекс некоторой вершины
a[p] – значение ключа для этой вершины
left[p] – номер левого потомка вершины p, если p=0, то потомок отсутствует
right[p] – номер левого потомка вершины p
top – номер вершины, которая является корнем дерева
TS = номеру вершины – в случае успешного поиска
TS = 0 – в случае неуспешного поиска
Информационые ресурсы:
http://www.codingrus.ru/readarticle.php?article_id=2152
7.2. Удаление из бинарного дерева
Дано: дерево Т с корнем n и ключом K.
Задача: удалить из дерева Т узел с ключом K (если такой есть).
Алгоритм:
1.Если дерево T пусто, остановиться
Иначе сравнить K с ключом X корневого узла n.
2.Если K>X, рекурсивно удалить K из правого поддерева Т.
3.Если K
4.Если K=X, то необходимо рассмотреть три случая.
1.)Если обоих детей нет, то удаляем текущий узел и обнуляем ссылку на него у родительского узла.
2.)Если одного из детей нет, то значения полей второго ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m.
3.)Если оба ребёнка присутствуют, то:
- найдём узел m, являющийся самым левым узлом правого поддерева;
- присвоим ссылке Left(m) значение Left(n)
- ссылку на узел n в узле Parent(n) заменить на Right(n);
- освободим память, занимаемую узлом n (на него теперь никто не указывает).
Случай 4.3 лучше рассмотреть на отдельном примере с рисунком для наглядности. Например, если из дерева на рис. 1 удаляется узел 20, его сначала нужно заменить на узел 37. Это даст дерево, изображенное на рис. 2 Рассуждения здесь примерно следующие. Нам нужно найти потомка узла 20, справа от которого расположены узлы с большими значениями. Таким образом, нам нужно выбрать узел с наименьшим значением, расположенный справа от узла 20. Чтобы найти его, нам и нужно сначала спуститься на шаг вправо (попадаем в узел 38), а затем на шаг влево (узел 37); эти двухшаговые спуски продолжаются, пока мы не придем в концевой узел, лист дерева.
Рис.1(удаление узла 20)
Рис.2(узел 20 удален)
Бинарные деревья представляют собой необычайно мощный ,гибкий и эффективный инструмент. Поскольку при поиске по сбалансированному бинарному дереву(наихудший случай) выполняется log2(n) сравнений, оно по сравнению со связанным списком представляет собой структуру, гораздо более удобную для поиска информации.
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] есть цена поддерева. Из оптимальных поддеревьев в результате составляется оптимальное дерево.
На втором этапе на основе этой матрицы формируется традиционная структура данных для представления дерева. Каждый узел i имеет три поля: значение ключа K[i], ссылку на номер узла - корня левого поддерева LL[i], ссылку на номер узла - корня правого поддерева RL[i]. Ссылка @ есть пустая ссылка на лист дерева. В схеме используются две функции: A(v) - адрес или индекс в массиве некоторой переменной v и ЗНАЧ(u) - значение переменной по адресу u. uk - переменная, которая имеет значение номера корневого узла оптимального дерева. Стек используется для хранения троек (u,i,j), соответствующих поддеревьям, где u - адрес или индекс в массиве корня данного поддерева, i,j - начальный и конечный индексы поддерева. Схема второго этапа имеет следующий вид.
Время работы алгоритма t примерно оценивается формулой:
t=a*N^2
где a - неизвестная константа, зависящая от программной реализации алгоритма.
7.4. Цифровой поиск по дереву
В этом алгоритме предполагается, что искомый ключ Х представляет собой последовательность бит. Функция БИТС(Х) возвращает старший бит ключа Х. Функция СДВГЛ(Х) сдвигает Х на 1 бит влево, добавляя справа 0. Схема алгоритма имеет вид.
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, считая от ссылки на него из какого-либо узла. Будем рассматривать два алгоритма: поиска (алгоритм П) и вставки новых узлов (алгоритм В). Второй алгоритм как составную часть использует первый. Схема алгоритма П имеет вид.
Схема алгоритма В имеет вид.
Следующие шаги выполняются при каждом последующем входе.
Рассмотрим пример работы алгоритмов П и В. Пусть в дерево Патриции нужно последовательно включить следующие элементы: '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.
На рисунке одинарными линиями показаны ссылки с TAG=1, а двойными - ссылки с TAG=0.
Состояние дерева после шага 4. X='С '
|
