Двоичные деревья поиска

Двоичные деревья

Двоичные деревья (ДД) используются наиболее часто и поэтому представляют наибольший практический интерес. Каждая вершина ДД должна иметь два связующих поля для адресации двух своих возможных потомков.

ДД можно реализовать двумя способами:

· на основе массива записей с использованием индексных указателей

· на базе механизма динамического распределения памяти с сохранением в каждой вершине адресов ее потомков (если они есть)

Второй способ является значительно более удобным и поэтому используется наиболее часто. В этом случае каждая вершина описывается как запись, содержащая как минимум три поля: информационную составляющую и два ссылочных поля для адресации потомков:

struct TREE {
int Info;
TREE *Right;
TREE *Left;
};

Для обработки дерева достаточно знать адрес корневой вершины. Для хранения этого адреса надо ввести ссылочную переменную:
TREE *Root;

Тогда пустое дерево просто определяется установкой переменной Root в нулевое значение:
Root = NULL;

Реализацию основных операций с ДД удобно начать с процедур обхода. Поскольку дерево является нелинейной структурой, то НЕ существует единственной схемы обхода дерева. Классически выделяют три основных схемы:

· обход в прямом направлении

· симметричный обход

· обход в обратном направлении

Для объяснения каждого из этих правил удобно воспользоваться простейшим ДД из трех вершин. Обход всего дерева следует проводить за счет последовательного выделения в дереве подобных простейших поддеревьев и применением к каждому из них соответствующего правила обхода. Выделение начинается с корневой вершины.

Сами правила обхода носят рекурсивный характер и формулируются следующим образом:

1. Обход в прямом направлении:

o обработать корневую вершину текущего поддерева

o перейти к обработке левого поддерева таким же образом

o обработать правое поддерево таким же образом

2. Симметричный обход:

o рекурсивно обработать левое поддерево текущего поддерева

o обработать вершину текущего поддерева

o рекурсивно обработать правое поддерево

3. Обход в обратном направлении:

o рекурсивно обработать левое поддерево текущего поддерева

o рекурсивно обработать правое поддерево

o затем – вершину текущего поддерева

Деревья поиска – частный, но практически, пожалуй, наиболее важный вид двоичных деревьев. Будем считать, что каждая вершина имеет некое ключевое поле, позволяющее упорядочить множество вершин. Двоичное дерево называется деревом поиска или поисковым деревом, если для каждой вершины дерева все ключи в ее левом поддереве меньше ключа этой вершины, а все ключи в ее правом поддереве больше ключа вершины.

Пример дерева поиска с целыми ключами представлен на следующем рисунке.

Деревья поиска являются одной из наиболее эффективных структур построения упорядоченных данных. Как известно, в упорядоченном массиве очень эффективно реализуется поиск (дихотомия!), но очень тяжело выполнить добавление и удаление элементов. Наоборот, в упорядоченном списке легко реализуется добавление и удаление элементов, но не эффективна реализация поиска из-за необходимости последовательного просмотра всех элементов, начиная с первого. Деревья поиска позволяют объединить преимущества массивов и линейных списков: легко реализуется добавление и удаление элементов, а также эффективно выполняется поиск.

Эффективность процесса поиска в ДП определяется дихотомической структурой самого дерева. На каждом шаге поиска, начиная с корня, отбрасывается одно из поддеревьев – левое или правое. Двоичный поиск наиболее эффективен для идеально сбалансированных деревьев или близких к ним. В самом плохом случае число сравнений равно высоте дерева. При этом, как и в методе двоичного поиска в упорядоченном массиве, сравнительная эффективность поиска в ДП быстро увеличивается при увеличении числа вершин в этом дереве.

Например, если идеально сбалансированное ДП имеет 1000 вершин, то даже в наихудшем случае потребуется не более 10 сравнений (2 в степени 10 есть 1024), а если число вершин 1 миллион, то потребуется не более 20 сравнений.

Можно сделать следующий вывод: ДП следует использовать для представления упорядоченных данных, когда число их достаточно велико и часто приходится выполнять операции добавления, удаления и поиска.

Интересно заметить, что обход ДП в симметричном порядке позволяет получить исходный набор данных в соответствии с заданным упорядочиванием, а обход в обратно-симметричном порядке – в обратном порядке.

Алгоритм поиска в ДП очень прост:

Начиная с корневой вершины для каждого текущего поддерева надо выполнить следующие шаги:

· сравнить ключ вершины с заданным значением x

· если заданное значение меньше ключа вершины, перейти к левому потомку, иначе перейти к правому поддереву.

Поиск прекращается при выполнении одного из двух условий:

· либо если найден искомый элемент

· либо если надо продолжать поиск в пустом поддереве, что является признаком отсутствия искомого элемента

2.8. Как устроена память?

Память компьютера построена из двоичных запоминающих элементов— битов, объединенных в группы по 8 битов, которые называются байтами. (Единицы измерения памяти совпадают с единицами измерения информации). Все байты пронумерованы. Номер байта называется его адресом.

Байты могут объединяться в ячейки, которые называются также словами. Для каждого компьютера характерна определенная длина слова — два, четыре или восемь байтов. Это не исключает использования ячеек памяти другой длины (например, полуслово, двойное слово). Как правило, в одном машинном слове может быть представлено либо одно целое число, либо одна команда. Однако, допускаются переменные форматы представления информации. Разбиение памяти на слова для четырехбайтовых компьютеров представлено в таблице:

Широко используются и более крупные производные единицы объема памяти: Килобайт, Мегабайт, Гигабайт, а также, в последнее время, Терабайт и Петабайт.

Современные компьютеры имеют много разнообразных запоминающих устройств, которые сильно отличаются между собой по назначению, временным характеристикам, объёму хранимой информации и стоимости хранения одинакового объёма информации. Различают два основных вида памяти — внутреннюю и внешнюю.