Слайды лекций - 2014 (лектор - Белеванцев А. А.) (1107979), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

Сделать стек пустым, т.е.затолкнуть NULL на дно стека: stack[0] = NULL;установить указатель стека на дно стека: top = 0;установить указатель t на корень дерева: t = r.(2)[Конец ветви].Если t == NULL, перейти к (4).(3)[Продолжение ветви]. Затолкнуть t в стек:stack[++top] = t;установить t = t->left и вернуться к шагу (2).(4)[К обработке правой ветви].

Вытолкнуть верхнийэлемент стека в t: t = stack[top]; top--;Если t == NULL, выполнение алгоритмапрекращается, иначе обработать данные узла, накоторый указывает t, и перейти к шагу (5).(5)[Начало обработки правой ветви]. Установитьt = t->right и вернуться к шагу (2).12Двоичное деревоНерекурсивная функция обхода двоичного дереваint inorder (node *r, char *order) {node *t = r;node *stack[depth];// depth = ?int top = 0, i = 0;if (!t)return 0;stack[0] = NULL;while (1) {while (t) {stack[++top] = t;t = t->left;}t = stack[top--];if (t) {order[i++] = t->info;t = t->right;} elsebreak;}return i;}//Шаг 1//Шаг 2//Шаг 3//Шаг 4//обработка//Шаг 5//t == NULL//Шаг 413Двоичное деревоПрошитое двоичное деревоРассмотрим двоичноедерево на верхнемрисунке.У этого дерева нулевыхуказателей, больше,чем ненулевых:10 против 8.Это – типичный случай.Будем записыватьвместо нулевыхуказателей указателина родителей (илиболее далеких предков)соответствующих узлов(такие указателиназываются нитями).Это позволит приобходе дерева неиспользовать стек.14Двоичное деревоПрошитое двоичное деревоОписание узла прошитого двоичного дереваtypedef struct bin_tree {char info;struct bin_tree *left;struct bin_tree *right;char left_tag;char right_tag;} threaded_node;Нитиустанавливаютсятаким образом,чтобы указывать напредшественников(левые нити) илипоследователей(правые нити)текущего узла присоответствующемобходе дерева.Например, в случаесимметричногообхода:Обычное деревоПрошитое деревоP->left == NULLP->left_tag == 1, P->left == P_pred_inP->left == QP->left_tagP->right == NULLP->right_tag == 1, P->right == P_next_inP->right == QP->right_tag == 0, P->right == Q== 0, P->left== Q15Двоичное деревоПрошитое двоичное деревоНити существенно упрощают алгоритмы обхода двоичныхдеревьев.

Например, для вычисления для каждого узла pуказатель узла P_next_in можно использовать следующийпростой алгоритм:threaded_node * next_in (threaded_node *p) {threaded_node *q = p->right;if (p->right_tag == 1)return q;while (q->left_tag == 0) //q != NULLq = q->left;//q->left != NULLreturn q;}Функция next_in фактически реализует симметричныйобход дерева, так как позволяет для произвольного узладерева P найти P_next_in. Многократно применяя этуфункцию, можно вычислить топологический порядок узловдвоичного дерева, соответствующий симметричному обходу.16Двоичное деревоПрошитое двоичное деревоАналогичным образом можно вычислить P_next_pred иP_next_post.Применяя функции next_pred (либо next_post), можновычислить топологический порядок узлов, соответствующийпрямому (либо обратному) обходу.Замечания(1)С помощью обычного представления невозможно дляпроизвольного узла P вычислить P_next_in, невычисляя всей последовательности узлов.(2)Функции next_in не требуется стек ни в явной, нив неявной (рекурсия) форме.17Двоичное деревоПрошитое двоичное деревоСравнение функций inorder()и next_in()позволяет сделать следующие выводы:Если p – произвольно выбранный узел дерева,тоследующий фрагмент функции next_in():q = p->right;if (p->right_tag == 1)return q;выполняется только один раз.Обход прошитого дерева выполняется быстрее, так какдля него не нужны операции со стеком.Для inorder() требуется больше памяти, чем дляnext_in(), из-за массива stack[depth].depth стараются взять не очень большим, но depth неможет быть меньше высоты двоичного дерева.Нельзя допускать переполнение стека деревьев.18Двоичное дерево Прошитое двоичное деревоВ функции inorder() используетсяуказатель r на корень двоичного дерева.Желательно, применив функцию next_in()к корню r, получить указатель на самыйпервый узел дерева для выбранногопорядка обхода.

Для этого к деревудобавляется еще один узел –заголовок дерева (header).поля структурыtypedef struct bin_tree{char info;struct bin_tree *left;struct bin_tree *right;char left_tag;char right_tag;} threaded_node;threaded_node *header;заполняются в заголовкеследующим образомheader->left_tag = 0;header->right_tag = 0;header->left = r;header->right = header;На рисунке дугидерева показаны болеежирными линиями, 19чем нити.Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Лекция 201Двоичные деревья поискаПроблема: организовать хранилище данных, которое позволяетхранить большие объемы данных и предоставляет возможностьбыстро находить и модифицировать данные.Хранилище данных обеспечивает пользователю интерфейс, вкотором определены словарные операции: search (найти, иногданазывается fetch), insert (вставить) и delete (удалить).Также предоставляется один или несколько вариантов обходахранилища (посещения всех данных).Варианты решения – деревья поиска, хеширование2Двоичные деревья поискаСтруктура для представления узла двоичного дерева поиска:struct BT_node {int key;struct BT_node *left;struct BT_node *right;struct BT_node *parent;}Ключи в двоичном дереве поиска хранятся с соблюдениемсвойства упорядоченности:Пусть x – произвольный узел двоичного дерева поиска.Если узел y принадлежит левому поддереву, тоkey[y] < key[x],если y находится в правом поддереве узла x, тоkey[y] > key[x].Возможно хранение дублирующихся ключей (нестрогиенеравенства), не рассматривающееся в данном курсе3Двоичные деревья поиска: поиск узлаНа входе: искомый ключ k и указатель root на корень поддерева,в котором производится поиск.На выходе: указатель на узел с ключом key (если такой узелесть), либо пустой указатель NULL.struct BT_node *Btsearch (struct BT_node *root, int k){if (! root || root->key == k)return root;if (k < root->key)return Btsearch (root->left, k);elsereturn Btsearch (root->right, k);}4Двоичные деревья поиска: поиск узлаИтеративная версия поиска.struct BT_node *Btsearch (struct BT_node *root, int k){struct BT_node *p = root;while (p && p->key != k)if (k < p->key)p = p->left;elsep = p->right;return p;}Среднее время поиска O(h), где h – высота дерева.5Двоичные деревья поиска: минимум и максимумНа входе: указатель root на корень поддерева.На выходе: указатель на узел с минимальным ключом k.struct BT_node *Btmin (struct BT_node *root){struct BT_node *p = root;while (p->left)p = p->left;return p;}Среднее время выполнения O(h), где h – высота дерева.6Двоичные деревья поиска: следующий элементНа входе: указатель node на узел дерева.На выходе: указатель на следующий за node узел дерева.struct BT_node *Btsucc (struct BT_node *node) {struct BT_node *p = node, *q;/* I случай: правое поддерево узла не пусто */if (p->right)return Btmin (p->right);/* II случай: правое поддерево узла пусто,идем по родителям до тех пор, пока не найдемродителя, для которого наше поддерево левое */q = p->parent;while (q && p == q->right) {p = q;q = q->parent;}return q;}Среднее время выполнения O(h), где h – высота дерева.7Связь с симметричным порядком обхода и прошитыми деревьями.Двоичные деревья поиска: вставкаНа входе: указатель root на корень дерева и указатель node нановый узел, у которого есть значение ключа, а все поля суказателями имеют значение NULL.struct BT_node * Btinsert (struct BT_node *root,struct BT_node *node) {struct BT_node *p, *q;p = root, q = NULL;while (p) {q = p;p = (node->key < p->key) ? p->left : p->right;}node->parent = q;if (q == NULL)root = node;else if (node->key < q->key)q->left = node;elseq->right = node;return root;}8Двоичные деревья поиска: удалениеНа входе: указатель на корень root дерева T иуказатель на узел n дерева T.На выходе: двоичное дерево T с удаленным узлом n(ключи нового дерева по-прежнему упорядочены).Необходимо рассмотреть три случая: (1) у узла n нет детей(листовой узел); (2) у узла n только один ребенок;(3) у узла n два ребенка.(1) просто удаляем узел n;(2) вырезаем узел n, соединив единственного ребенкаузла n с родителем узла n.(3) находим succ(n) и удаляем его, поместив ключsucc(n) в узел n.9Двоичные деревья поиска: удалениеШаг 1: если у n меньше двух детей, удаляем n, иначе удаляемsucc(n); устанавливаем указатель y на удаляемый узел.Шаг 2: находим ребенка удаляемого узла (ребенка либо нет,либо он единственный) и устанавливаем на него указатель x.Шаг 3: подвешиваем ребенка y (указатель x) к родителю y;если у y нет родителя, новым корнем дерева становится x;устанавливаем в соответствующем поле родителя указатель наx, полностью исключая y из дерева.Шаг 4: если удаляемый узел succ(n), заменяем данные узла n наданные узла succ(n).10Двоичные деревья поиска: удалениеstruct BT_node * BTdelete (struct BT_node **root,struct BT_node *n) {struct BT_node *x, *y;/* Шаг 1: y – указатель на удаляемый узел n */y = (! n->left || ! n->right) ? n : BT_succ (n);/* Шаг 2: x – указатель на ребенка y, либо NULL */x = y->left ? y->left : y->right;/* Шаг 3: если x – ребенок y, вырезаем y из родителей */if (x)x->parent = y->parent;/* Шаг 3: если у y нет родителя, новым корнем дерева становится x */if (! y->parent)*root = x;else {/* Шаг 3: x присоединяется к y->parent с требуемой стороны */if (y == y->parent->left)y->parent->left = x;elsey->parent->right = x;}<...>11Двоичные деревья поиска: удалениеstruct BT_node * BTdelete (struct BT_node **root,struct BT_node *n) {struct BT_node *x, *y;<...>/* Шаг 4: если удалялся не узел n, а succ(n), необходимозаменить данные узла n на данные узла succ(n) */if (y != n)n->key = y->key;/* функция возвращает указатель удаленного узла, чтодает возможность использовать этот узел в другихструктурах, либо очистить занимаемую им память */return y;}Среднее время выполнения O(h), где h – высота дерева.12Построение двоичного дерева поиска.Постановка задачи.

Характеристики

Список файлов лекций