Основы теории

Рассмотрим еще один способ хранения множества значений – представление множеств с помощью деревьев.

 

Рисунок 1 – Терминология дерева

При обсуждении деревьев применяется специальная терминология. Программисты не являются специалистами в области филологии, и поэтому терминология, применяемая в теории графов (а ведь деревья представляют собой частный случай графов!), является классическим примером неправильного употребления слов. Первый элемент дерева называется корнем (root). Каждый элемент данных называется вершиной дерева (node), а любой фрагмент дерева называется поддеревом (subtree). Вершина, к которой не присоединены поддеревья, называется заключительным узлом (terminal node) или листом (leaf). Высота (height) дерева равняется максимальному количеству уровней от корня до листа. При работе с деревьями можно допустить, что в памяти они существуют в том же виде, что и на бумаге. Но помните, что дерево — всего лишь способ логической организации данных в памяти, а память линейна.

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

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

На первом уровне двоичного дерева может быть только одна вершина – корень, на втором – две (сыновья корня), на третьем – четыре (сыновья сыновей корня). В общем случае на i-м уровне может быть до 2i-1 вершин. Дерево, содержащее n полностью заполненных уровней, будем называть полным. Полное двоичное дерево содержит =2i-1 вершин.

Всякое непустое двоичное T-дерево разбивается на 3 части: корень, левое и правое поддеревья. Отсюда можно дать следующее рекурсивное определение двоичного дерева:

пустое дерево – двоичное дерево;

вершина с левым и правым двоичными поддеревьями – двоичное дерево.

Левое и правое поддеревья могут быть пустыми.

Высотой поддерева будем считать максимальную длину цепи y[1]..y[n] его вершин такую, что y[i+1] – сын y[i] для всех i. Высота пустого дерева равна 0. Высота дерева из одного корня – единице.

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

Двоичное T-дерево упорядочено, если для любой вершины X справедливо такое свойство: все элементы, хранимые в левом поддереве, меньше элемента, хранимого в X, а все элементы, хранимые в правом поддереве, больше элемента, хранимого в X.

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

В дальнейшем будет идти речь только о двоичных упорядоченных деревьях, опуская слова «двоичный» и «упорядоченный».

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

Приведенная ниже функция stree() создает упорядоченное двоичное дерево:

struct tree {

char info;

struct tree *left;

struct tree *right;

};

 

struct tree *stree(

struct tree *root,

struct tree *r,

char info)

{

if(! r) {

r = (struct tree *) malloc(sizeof(struct tree));

if(! r) {

printf(" Не хватает памяти\n");

exit(0);

}

r-> left = NULL;

r-> right = NULL;

r-> info = info;

if(! root) return r; /* первый вход */

if(info < root-> info) root-> left = r;

else root-> right = r;

return r;

}

if(info < r-> info)

stree(r, r-> left, info);

else

stree(r, r-> right, info);

 

return root;

}

Приведенный выше алгоритм просто следует по ссылкам дерева, переходя к левой или правой ветви очередной вершины на основании содержимого поля info до достижения места вставки нового элемента. Чтобы использовать эту функцию, необходимо иметь глобальную переменную-указатель на корень дерева. Этот указатель изначально должен иметь значение нуль (NULL). При первом вызове функция stree() возвращает указатель на корень дерева, который нужно присвоить глобальной переменной. При последующих вызовах функция продолжает возвращать указатель на корень. Допустим, что глобальная переменная, содержащая корень дерева, называется rt. Тогда функция stree() вызывается следующим образом:

/* вызов функции street() */rt = street(rt, rt, info);

Функция stree() использует рекурсивный алгоритм, как и большинство процедур работы с деревьями.

 

#include< iostream>

usingnamespace std;

struct Node

{

int d;

Node *left;

Node *right;

};

Node * first (int d);

Node * search_insert(Node *root, int d);

void print_tree(Node *root, int level);

//

int main()

{

int b[] = {10, 25, 20, 6, 21, 8, 1, 30};

Node *root = first(b[0]);

for (int i = 1; i< 8; i++)search_insert(root, b[i]);

print_tree(root, 0);

return 0;

}

// Формирование первого элемента дерева

Node * f1rst(int d)

{

Node *pv = new Node;

pv-> d = d;

pv-> left = 0;

pv-> right = 0;

return pv;

}

// Поиск с включением

Node * search_insert(Node *root, int d)

{

Node *pv = root, *prev;

bool found = false;

while (pv & &! found)

{

prev = pv;

if(d == pv-> d) found = true;

elseif(d < pv-> d) pv = pv-> left;

else pv = pv-> right;

}

if (found) return pv;

// Создание нового узла

Node *pnew = new Node;

pnew-> d = d;

pnew-> left = 0;

pnew-> right = 0;

if (d < prev-> d)

// Присоединение к левому поддереву предка

prev-> left = pnew;

else

// Присоединение к правому поддереву предка

prev-> right = pnew;

return pnew;

}

// Обходдерева

void print_tree(Node *p, int level)

{

if (p)

{

print_tree(p-> left, level+1); // выводлевогоподдерева

for (int i = 0; i< level; i++)cout < < " ";

cout < < p-> d < < endl; // вывод корня поддерева

print_tree(p-> right, level+1); // вывод правого поддерева

}

}

Текущий указатель для поиска по дереву обозначен pv, указатель на предка pv обозначен prev, переменная pnew используется для выделения памяти под включаемый в дерево узел. Рекурсии удалось избежать, сохранив всего одну переменную (prev) и повторив при включении операторы, определяющие, к какому поддереву присоединяется новый узел.

Рассмотрим подробнее функцию обхода дерева. Вторым параметром в нее передается целая переменная, определяющая, на каком уровне находится узел. Корень находится на уровне 0.

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

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

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

Итак, в худшем случае хранение в упорядоченном дереве никакого выигрыша по сравнению с обычным способом хранения множества в массиве не дает. В лучшем случае для всех операций (поиск/добавление/удаление) получается логарифмическая сложность, а это очень хорошо (ни один из рассмотренных ранее способов хранения такого результата для всех операций не давал). Но как гарантировать логарифмическую сложность всегда? Выход открывает способ, который был предложен в 1962 году двумя советскими математиками – Г.М.Адельсоном-Вельским и Е.М.Ландисом.

Так исторически сложилось, что у АВЛ-деревьев есть два альтернативных названия: АВЛ-деревья и сбалансированные деревья. АВЛ произошло от фамилий изобретателей.

Идеально сбалансированным называется дерево, у которого для каждой вершины выполняется требование: число вершин в левом и правом поддеревьях различается не более, чем на 1. Однако идеальную сбалансированность довольно трудно поддерживать. В некоторых случаях при добавлении/удалении может потребоваться значительная перестройка дерева, не гарантирующая логарифмической сложности. Поэтому Г.М.Адельсон-Вельский и Е.М.Ландис ввели менее строгое определение сбалансированности и доказали, что при таком определении можно написать программы добавления/удаления, имеющие логарифмическую сложность и сохраняющие дерево сбалансированным.

Дерево считается сбалансированным по АВЛ (в дальнейшем просто «сбалансированным»), если для каждой вершины выполняется требование: высота левого и правого поддеревьев различаются не более, чем на 1. Не всякое сбалансированное дерево идеально сбалансировано, но всякое идеально сбалансированное дерево сбалансировано.

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

В сбалансированном дереве показатели сбалансированности всех вершин лежат в пределах от -1 до 1. При операциях добавления/удаления могут появляться вершины с показателями сбалансированности -2 и 2.

Пусть показатель сбалансированности вершины, в которой произошло нарушение баланса, равен -2, а показатель сбалансированности корня левого поддерева равен -1. Тогда восстановить сбалансированность такого поддерева можно следующим преобразованием, называемым малым левым вращением:

Рисунок 2 – Малое левое вращение

На приведенном рисунке прямоугольниками обозначены поддеревья. Рядом с поддеревьями указана их высота. Поддеревья помечены арабскими цифрами. Кружочками обозначены вершины. Цифра рядом с вершиной - показатель сбалансированности в данной вершине. Буква внутри кружка - условное обозначение вершины.

Как видно из рисунка после малого левого вращения показатель сбалансированности вершины, в которой было нарушение баланса, становится равным нулю.

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

Рисунок 3 – малое правое вращение

Несколько сложнее случай, когда показатель сбалансированности в вершине, в которой произошло нарушение баланса равен -2, а показатель сбалансированности в корне левого поддерева равен 1 или 0. В этом случае применяется преобразование, называемое большим левым вращением. Как видно из рисунка здесь во вращении участвуют три вершины, а не две как в случае малых вращений.

 

 

Рисунок 4 – Большое правое вращение

 

Пусть имеется дерево, сбалансированное всюду, кроме корня, а в корне показатель сбалансированности по модулю равен 2-м. Такое дерево можно сбалансировать с помощью одного из четырех вращений. При этом высота дерева может уменьшиться на 1. Для восстановления баланса после удаления/добавления вершины надо пройти путь от места удаления/добавления до корня дерева, проводя при необходимости перебалансировку и изменение показателя сбалансированности вершин вдоль пути к корню.

Схематично алгоритм вставки нового элемента в сбалансированное дерево будет состоять из следующих трех основных шагов:

Поиск по дереву.

Вставка элемента в место, где закончился поиск, если элемент отсутствует.

Восстановление сбалансированности.

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

3-ий шаг представляет собой обратный проход по пути поиска: от места добавления к корню дерева. По мере продвижения по этому пути корректируются показатели сбалансированности проходимых вершин и производится балансировка там, где это необходимо. Добавление элемента в дерево никогда не требует более одного поворота.

Алгоритм удаления элемента из сбалансированного дерева будет выглядеть так:

- поиск по дереву.

- удаление элемента из дерева.

- восстановление сбалансированности дерева (обратный проход).

1-ый шаг необходим, чтобы найти в дереве вершину, которая должна быть удалена. Первые два шага аналогичны удалению элемента.

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

Операция удаления может потребовать перебалансировки всех вершин вдоль обратного пути к корню дерева, то есть порядка log(N) вершин. Доказательство того, что порядок числа вершин имеет такой аналитический вид, смотрите в следующем разделе.

Понятно, что в случае полного двоичного дерева (наилучший случай) мы получим сложность T(log(n)) (на каждом шаге размер дерева поиска будет сокращаться вдвое). Рассмотрим минимальное сбалансированное дерево (худший случай). Таким будет дерево, у которого для каждой вершины высота левого и правого поддеревьев различаются на 1. Для такого дерева можно записать следующую рекуррентную формулу для числа вершин (h – высота дерева):

Покажем, что h< log2(Nh). Для этого необходимо и достаточно показать, что 2h> Nh. Докажем последнее методом математической индукции.

 

а) h=0: 20> N0=0;

б) h=1: 21> N1=1;

в) h> 1: Пусть 2h-2> Nh-2 и 2h-1> Nh-1.

Тогда 2h-2+2h-1> Nh-2+ Nh-1.

И далее получаем 2h> 1+2h-2+2h-1> 1+Nh-2+ Nh-1=Nh, что и требовалось доказать.

Таким образом, мы доказали, что алгоритмы поиска/добавления/удаления элементов в сбалансированном дереве имеют сложность T(log(n)).

Г.М. Адельсон-Вельский и Е.М. Ландис доказали теорему, согласно которой высота сбалансированного дерева никогда не превысит высоту идеально сбалансированного дерева более, чем на 45%.