2.3 Перечень вопросов, планируемых при изучении материала
Понятие дерева.
Бинарное дерево.
Построение бинарного дерева на основе линейного списка.
Изучение операций на бинарном дереве.
2.4 Аннотация к лекции
Бинарное дерево – иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.
Основным преимуществом двоичного дерева поиска перед другими структурами данныхявляется возможная высокая эффективность реализации основанных на нём алгоритмовпоискаисортировки.
Двоичное дерево поиска применяется для построения более абстрактных структур, таких, как множества, мультимножества, ассоциативные массивы.
2.5 Текст лекции Бинарные деревья
Если в дереве каждая нетерминальная вершина может иметь не более двух вершин следующего уровня, то такое дерево называется бинарным. Обычно бинарные деревья считают упорядоченными, а вершины следую- щего уровня называют левой и правой. Соответственно, каждое из подде- ревьев левой и правой вершин называют левым и правым поддеревьями. Бинарные деревья имеют важное самостоятельное значение, т.к. применя- ются для организации поиска, вычислений и т.д. Упорядоченные бинарные деревья. Такие деревья часто применя- ются для поиска элемента по его ключу. Ранее было показано, что лога- рифмический поиск возможен для упорядоченного множества в непрерыв- ной реализации. Для ссылочной реализации упорядоченного множества в виде упорядоченного бинарного дерева также можно выполнить логариф- мический поиск. Такое дерево называют деревом поиска. Если дерево ор- ганизовано так, что для каждой его вершины i все ключи левого поддерева меньше ключа i , а все ключи правого поддерева больше ключа i , то такое дерево является деревом поиска. Пусть дано множество элементов: A = {8, 9, 11, 15, 19, 20, 21, 7, 3, 2, 1, 5, 6, 4, 13, 14, 10, 12, 17, 16, 18}. Очевидно, что это неупорядоченное мно- жество. Представим его в виде упорядоченного бинарного дерева, которое позволит выполнить логарифмический поиск. Будем достраивать такое де- рево при каждом очередном предъявлении элемента из данного множества (рис. 1).
Рисунок 1 – Дерево поиска множества A
Бинарный поиск на дереве. Будем полагать, что в элементе atom поле item имеет структуру, показанную на рис. 2, где pos – это позиция элемента множества, а v – его значение.
Рисунок 2 – Структура элемента в дереве поиска
Т.к. множество A является неупорядоченным, то позиции его элементов получаются при выстраивании элементов множества в ряд в некотором произвольном порядке, который абсолютно не гарантирует упорядоченности элементов по их значениям. Позиции элементов нумеруются с единицы. Если элемент не найден или множество пусто, то программа возвращает значение pos=0.
pos locate(key,tree t)
{
if t.root is null then return null
root(t)
if key eq t.current->item->v then
return t.current->item->pos
while (t.current->down not null)
{
if key < t.current->item->v then
down(t)
else if key > t.current->item->v then
{down(t), tnext(t)}
if key eq t.current->item->v then
return t.current->item->pos
}
return null
}