Бинарные деревья

Рисунок 6. Иллюстрация к опыту по наблюдению и исследованию дифракции излучения на пропускающей решетке.

Лабораторная работа № 5

Бинарные деревья

Бинарное дерево представляет собой структуру, в которой каждый узел (вершина) имеет не более двух узлов-потомков и ровно одного родителя.

Можно дать следующее рекурсивное определение двоичного (бинарного) дерева:

1. Пустое множество элементов либо один элемент есть двоичное дерево;

2. Двоичное дерево есть элемент, который связан с двумя двоичными деревьями.

Когда говорят о двоичном дереве, то используют терминологию из ботаники и родственных связей. Так, узел, связанный с другими, называется родитель, у родителя могут быть два ребенка – левый и правый. Элемент, не имеющий поддеревьев, называется листом. Элемент, не имеющий родителя, - корнем. Высотой дерева называется длина максимального пути от корня к листу.

Количество элементов в полном дереве из n уровней равно 2 ⁿ - 1.

Дерево называется идеально сбалансированным, если для каждого узла количество узлов в левом и правом поддереве отличается не более чем на единицу. Высота идеально сбалансированного дерева будет минимальной и равна [log₂ n].

Двоичные (бинарные) деревья, хранимые в динамической памяти, можно использовать для различных задач хранения и обработки информации.

С помощью двоичных деревьев представляются генеалогические деревья предков, схемы теннисного турнира, арифметические выражения и т. п.

Подобно элементам списка, узлы дерева будем представлять записями, содержащими некоторую информацию и два указателя: left и right – на корни левого и правого поддерева соответственно. Ссылки на пустые поддеревья будут обозначаться значением nil.

 

 

 

 

		nil

 

 

 

 

			nil
				nil

 

 

Получим следующее описание типа:

 

Type

PNode=^Node;

Node = record

Data: DataType;

left,right: PNode;

end;

 

Отдельная переменная t:PNode будет указывать на корень дерева.

 

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

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

Проводя математические рассуждения, можно показать, что из n элементов можно организовать двоичное дерево с высотой не более log₂ n. Поэтому, если дерево идеально сбалансировано, поиск среди его n элементов выполняется максимум за Q (log n) сравнений. Такая же сложность будет у операции добавления и удаления. Ясно, что подобные деревья для поиска данных значительно эффективнее, чем все изученные ранее структуры данных.

Рассмотрим подробнее основные операции с деревьями. Прежде всего нужно научиться выполнять некоторую операцию, например вывод, для каждого элемента дерева. Такая задача называется «обход» дерева.

Если корень дерева обозначить R, левое поддерево – A, правое – B, как на рисунке,

 

то можно говорить о четырех способах обхода:

1. Сверху вниз: R, А, В (корень посещается ранее, чем поддеревья).

2. Слева направо: А, R, В.

3. Справа налево: B, R, A.

4. Снизу вверх: А, В, R (корень посещается после поддеревьев).

 

Обход дерева выполняется в виде рекурсивной процедуры. Рассмотрим, например, процедуру обхода слева направо.

 

Остальные операции реализуются аналогично. Очевидно, что для двоичного дерева поиска обход слева направо приведет к выводу значений в порядке возрастания ключей, обход справа налево – в порядке убывания ключей. Таким образом, двоичные деревья можно использовать и для сортировки записей.

Запишем процедуру добавления элемента в дерево. Для этого заметим, что если дерево пусто, то элемент ставится в его вершину. Если дерево непусто, то можно сравнить добавляемый ключ с ключом в вершине и рекурсивно добавить элемент в левое или правое поддерево. Получаем процедуру:

 

Сложность процедуры Q(H), где H – высота дерева. В худшем случае, если данные изначально упорядочены, например по возрастанию, вставка будет производиться всегда в правое поддерево. В результате полученное дерево будет являться фактически линейным списком, например:

 

 

 

 

	nil

 

 

nil

 

 

		nil

nil

 

В этом случае сложность вставки будет Q (n). Для сбалансированного дерева сложность вставки уменьшается до Q (log n).

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

 

	t

 

 

 

 

 

x

 

 

			nil

 

 

nil

 

 

a

 

b

 

 

 

		nil
				nil
				nil

 

 

Элемент x можно заменить на a или на b: так как a – наибольший элемент, меньший x, то он будет меньше всех элементов, расположенных правее x и больше всех элементов, расположенных левее x, аналогично, b – наименьший элемент, больший x, поэтому он также будет меньше всех элементов, расположенных правее x и больше всех элементов, расположенных левее x.

Все детали приводятся в самой рекурсивной процедуре под названием delete. В ней различаются три случая:

1. Компонента с ключом, равным х, нет.

2. Компонент с ключом х имеет не более одного потомка.

3. Компонент с ключом х имеет двух потомков.

Вспомогательная рекурсивная процедура del начинает работать только в случае 3. Она «спускается» вдоль правой ветви левого поддерева элемента q^, который нужно исключить, и заменяет данные в q^ на соответствующие значения из самого правого компонента r^ левого поддерева.