Лекция 16. Двоичные деревья (окончание) (Электронные лекции)

Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годЛекция 16 Двоичные деревья (окончание)16.1. Операции над двоичными деревьями.16.1.1. Ключевое слово typedef позволяет определять новые имена типов данных.Синтаксис: typedef тип новое_имя_типа. (1)Например, в функциях обработки двоичного дерева постоянно использовался типstruct BT_node, причем такой тип описывал как корень двоичного дерева (т.е. вседвоичное дерево), так и его узел. Конструкция (1) позволяет ввести два новых именидля типа:struct BT_node {int key;struct BT_node *left;struct BT_node *right;struct BT_node *parent;}Имеем:typedef struct BT_node *BT; /* BT – новое имя типа"указатель на structBT_node" */typedef struct BT_node *node; /* node – еще одно новоеимя типа "указатель наstruct BT_node" */Теперь можно написать новые объявления функций обработки двоичного дерева:node BTsearch(BT T, int k);node BTmin(BT T);node BTmax(BT T);node BTsucc(node n);node BTpred(node n);void BTinsert(BT T, node n);node BTdelete(BT T, node n);16.1.2.

Новое имя типа, определенное с помощью typedef, можно использовать в другихtypedef в позиции тип для определения еще более новых имен типа.16.1.3. Конструкция typedef не вводит новых типов данных (в отличие от конструкцииstruct). Она вводит новые имена для старых типов данных, что может существенноупростить написание кода и сделать его более понятным.16.2. Определение функции void BTdelete(BT T, node n);16.2.1. Алгоритм.На входе: указатель на дерево T (фактически это указатель на корень root дерева T) иуказатель на узел n дерева T.На выходе: двоичное дерево T с удаленным узлом n (ключи нового дерева попрежнему упорядочены).Необходимо рассмотреть три случая: (1) у узла n нет детей (листовой узел); (2) у узлаn только один ребенок; (3) у узла n два ребенка.(1) просто удаляем узел n;(2) вырезаем узел n, соединив единственного ребенка узла n с родителем узла n.(3) находим succ(n) и удаляем его, поместив ключ succ(n) в узел n.(с) Кафедра системного программирования ф-та ВМК МГУ, 20101Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годСлучаи (1) и (2) можно объединить.Шаг 1: если у n меньше двух детей (либо левый, либо правый ребенок отсутствует),удаляем n, иначе удаляем succ(n); устанавливаем указатель y на удаляемый узел.Шаг 2: находим ребенка удаляемого узла (на него указывает y) и устанавливаем нанего указатель x (если у удаляемого узла нет детей, имеет значение NULL).Шаг 3: подвешиваем ребенка y (указатель x) к родителю y; если у y нет родителя (y –корень дерева), новым корнем дерева становится x; устанавливаем в соответствующемполе родителя указатель на x, полностью исключая y из дерева.Шаг 4: если удаляемый узел succ(n), заменяем данные узла n на данные узла succ(n).16.2.2.

Программа на Си.node BTdelete(BT T, node n) {node x, y;/* y – указатель на удаляемый узел n */if(n->left == NULL || n->right == NULL) y = n;else y = succ(n);/* x – указатель на ребенка y, либо NULL */if(y->left != NULL) x = y->left;else x = y->right;/* если x – ребенок y, вырезаем y */if(x != NULL) x->parent = y->parent;/* если у y нет родителя (y – корень дерева) *//* новым корнем дерева становится x */if(y->parent = NULL) T = x;else {/* x присоединяется к y->parent с требуемой стороны */if(y == y->parent->left) y->parent->left = x;else y->parent->right = x;}/* если удалялся не узел n, а succ(n), необходимо *//* заменить данные узла n на данные узла succ(n) */if(y != n) n->key = y->key;......................../* функция возвращает указатель удаленного узла, что *//* дает возможность использовать этот узел в других *//* структурах, либо очистить занимаемую им память */return y;}Среднее время выполнения функции BTdelete O(h), где h – высота дерева T.16.3.

Построение двоичного дерева поиска.16.3.1. Пусть имеется множество из m ключей: k0, k1, …, km-1. Произведем разбиение этогомножества на три подмножества В1, В2, В3, причем В2 состоит ровно из одногоэлемента, а В1 и В3 могут быть пустые. Разбиение произведем таким образом, что всеключи из В1 меньше ключа из В2, а все ключи из В3 больше (или равны) ключа из В2.(с) Кафедра системного программирования ф-та ВМК МГУ, 20102Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годДалее движемся рекурсивно: В1 разбивается на В11, В12, В13, а В3 на В31, В32, В33 и т.д.

Вкаждой тройке сохраняется то же соотношение ключей, что и при первом разбиении.16.3.2. Пример: 15,10,1,3,8,12,4. Первое разбиение: {1,3,4}, {8}, {15,10,12}; второе разбиение:{{1}{3}{4}}{8}{{10}{12}{15}}. Получилось полностью сбалансированное двоичноедерево, высота которого, как известно пропорциональна log2m.16.3.3. Дерево называется полностью сбалансированным (совершенным), если длина пути откорня до любой листовой вершины одинакова.16.3.4.

Пусть h – высота полностью сбалансированного двоичного дерева. Тогда числовершин m должно быть равно:h1 ⋅ ( 2 h − 1)im = 1 + 2 + 22 + … + 2h = ∑ 2 == 2h – 12− 1i= 0откуда h = log2(m + 1).16.3.5. Если все m ключей известны заранее, их можно отсортировать (O(m⋅log2m)), послечего построение сбалансированного дерева будет тривиальной задачей. Если жедерево строится по мере поступления ключей, то все может быть: от линейного дерева(O(m)) до полностью сбалансированного дерева (O(log2m)).Например, если идет поток ключей 1, 3, 5, 8, 10, 12, 15, то, поместив в корень дереваключ 1, мы будем заносить все ключи справа от текущего узла и получим линейноедерево.16.3.6. Пусть T = {root, left, right} – двоичное дерево; тогда hT = max(hleft, hright) + 1.16.4. Деревья Фибоначчи16.4.1.

Числа Фибоначчи возникли в решении задачи о кроликах, предложенном в XIII векеЛеонардо из Пизы, известным как Фибоначчи. Задача: пара новорожденных кроликовпомещена на остров. Каждый месяц любая пара дает приплод – также пару кроликов.Пара начинает давать приплод в возрасте двух месяцев. Сколько кроликов будет наострове через n месяцев? В конце первого и второго месяцев на острове будет однапара кроликов: f1 = 1, f2 = 1. В конце третьего месяца родится новая пара, так что f3 = f2+ f1. По индукции можно доказать, что для n ≥ 3 fn = fn-1 + fn-2.

n-е число Фибоначчивычисляет следующая функция:int Fbn(int n) {if ((n == 1) || (n == 2))return 1;else {g = h = 1;for(k = 2; k < n; k++) {Fb = g + h;h = g;g = Fb;}return Fb;}}16.4.2. Определение дерева Фибоначчи (это тоже искусственное дерево).(1) Пустое дерево – это дерево Фибоначчи с высотой h = 0.(2) Двоичное дерево, левое и правое поддерево которого есть деревья Фибоначчи свысотами соответственно h – 1 и h – 2 (либо h – 2 и h – 1), есть дерево Фибоначчис высотой h.(с) Кафедра системного программирования ф-та ВМК МГУ, 20103Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годИз определения следует, что в дереве Фибоначчи значения высот левого и правогоподдерева отличаются ровно на 1.16.4.3. Пример. Дерево Фибоначчи с h = 6.85327469116.4.4.

Теорема.Число вершин в дереве Фибоначчи Fh высоты h равно m(h) = fh+2 – 1.Доказательство по индукции.h = 0: m(0) = f2 – 1 = 0б m(1) = f3 – 1 = 1.Шаг: по определению (16.4.2) m(h) = m(h – 1) + m(h – 2) + 1. Имеем m(h) = (fh+1 – 1) + (fh– 1) + 1 = fh+2 – 1, так как согласно 16.4.1 fh + fh + 1 = f h + 216.4.5. Теорема.Пусть C1 и C2 таковы, что уравнение r2 – C1r – C2 = 0 (*) имеет два корня r1 и r2 , r1 ≠ r2.Тогда (1) из an = C1an-1 + C2an-2 и начальных условий а0 и а1 следует an = α1r1n + α2r2n дляn = 1, 2, ...

, и (2) из an = α1r1n + α2r2n следует an = C1an-1 + C2an-2 .Доказательство (2). Так как r1 и r2 – корни уравнения (*), то r12 = C1r1 + C2 и r22 = C1r2 +C2. Имеем:C1an-1 + C2an-2 = С1(α1r1n-1 + α2r2n-1) + С2(α1r1n-2 + α2r2n-2) =(**)n-2n-2n-2 2n-2 2n= α1r1 (С1r1 + C2) + α2r2 (C1r2 + C2) = α1r1 r1 + α2r2 r2 = α1r1 + α2r2n = anДоказательство (1).

Нужно не только повторить в обратном порядке вывод (**), но иподобрать такие α1 и α2, чтобы а0 = α1 + α2, а1 = α1r1 + α2r2 (***). Рассматривая (***)как систему линейных уравнений относительно α1 и α2, получим:a − a ⋅r− a1 + a0 ⋅ r1α1= 1 0 2, α2=. Теорема доказана.r1 − r2r1 − r216.4.6. Применим теорему (16.4.5) к числам Фибоначчи: fn = fn-1 + fn-2. Корнями уравнения1+ 51− 5r2 – r – 1 = 0 являются r1 =и r2 =. Следовательно, согласно теореме22(с) Кафедра системного программирования ф-та ВМК МГУ, 20104Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годnn 1+ 5  1− 5  + α 2⋅f n = α 1 ⋅ r + α 2 ⋅ r = α 1 ⋅  2  , 2 f 0 = α 1 + α 2 = 0,n1n2, 1+ 5  1− 5  + α 2⋅f1 = α 1 ⋅  2 =1211α1=,α 2 = −55Откудаn1  1+ 5 1  1− 5  −fn =⋅ ⋅5  2 5  2 Согласно (16.4.4)1  1+ 5 m(h) = fh+2 – 1=5  2 1  1− 5 Но ⋅5  2 h+ 2h+ 2n1  1− 5 −5  2 h+ 2−11  1+ 5 < 1 , следовательно, m(h) + 1 >5  2 Введя обозначение γ =1+h+ 25и логарифмируя обе части последнего неравенства,2log 2 (m + 1) log 2 5+получаем: h + 2 <, откуда h < 1.44⋅ log 2 (m + 1) – 0.32log 2 γlog 2 γТаким образом, мы доказали, что для деревьев Фибоначчи с числом вершин mколичество сравнений в худшем случае не превышает 1.44⋅ log 2 (m + 1) – 0.32.16.4.7.

Итак, для искусственно построенных двоичных деревьев получены хорошие оценки.Следующий шаг – научиться строить естественные деревья с такими же хорошимиоценками.(с) Кафедра системного программирования ф-та ВМК МГУ, 20105.