05-structures2 (1238879), страница 2

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

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

Также легко получитьгород на расстоянии 60 километров. Но увы, вынуть из хеш-таблицы всегорода от 50 до 100 километров невозможно•Говорят, что хеш-отображения не позволяют делать range-queriesОбсуждение•Главный недостаток хеш-таблиц (и шире хеш-функций как идеи) это стираниеинформации о естественном порядке объектов•Например если нужно индексировать города расстоянием от Москвы, тосложить их в хеш-таблицу по этому расстоянию легко. Также легко получитьгород на расстоянии 60 километров.

Но увы, вынуть из хеш-таблицы всегорода от 50 до 100 километров невозможно•Говорят, что хеш-отображения не позволяют делать range-queries•И это естественным образом приводит нас к поисковым деревьямПредставления бинарных деревьев•Классическая структура данныхдля бинарного дерева различаетлевый и правый листьяstruct tree_t {struct tree_t *left;struct tree_t *right;int data;};•Дополнительно можно хранитьуказателя на предка(3 (2 (1)) (5 (4) (6)))Представление в текстовом файле•Самый простой способ: хранить списокориентированных рёберkey left right521430•1 40 3-1 -1-1 -1-1 -1521430-1 40 2-1 -11 -1-1 -1Можно ли упростить это представление?Представление в текстовом файле•Самый простой способ: хранить списокориентированных рёберkey left right52 1 41 0 352 -1 41 0 23 1 -1•Да.

Например не хранить узлы с обоими пустымипотомками•Пример считывания такого файла в tree-reader.cОбходы деревьев•Обходом (traverse) называетсяпроцедура, посещающая все узлыдерева•Центрированный (inorder) обход:узлы посещаются в порядкепроектирования на прямую линию•Как написать такой обход?123456Алгоритм IR – центрированный обход•Основная идея: для каждого узла сначала обходится левое поддерево, потомпосещается сам узел, потом обходится правое поддеревоstruct tree_t {struct tree_t *left, *right; int data;};void visit(struct tree_t *top);void traverse_inorder(struct tree_t *top) {if (top == NULL) return;traverse_inorder(top->left);visit(top);traverse_inorder(top->right);}123456Обсуждение: топологический обход•Пусть дерево это зависимости междуделами•Можно ли обойти дерево так, чтобыникакое дело не было сделано раньшеего зависимостей?•Суть алгоритма IRtraverse(top->left);visit(top);traverse(top->right);•Что поменять чтобы получилсятопологический порядок?3 → 2 → 1 → 5 → 4 → 6Обсуждение: топологический обход•Пусть дерево это зависимости междуделами•Можно ли обойти дерево так, чтобыникакое дело не было сделано раньшеего зависимостей?•Модификация алгоритма IR:visit(top);traverse(top->left);traverse(top->right);•Это называется preorder обходом3 → 2 → 1 → 5 → 4 → 6Обсуждение: стереть дерево•Пусть теперь хочется стереть дерево•Можно ли обойти дерево так, чтобы вселисты были посещены раньше их предков?•Суть алгоритма IR:traverse(top->left);visit(top);traverse(top->right);1 → 2 → 4 → 6 → 5 → 3Обсуждение: стереть дерево•Пусть теперь хочется стереть дерево•Можно ли обойти дерево так, чтобы вселисты были посещены раньше их предков?•Модификация алгоритма IR:traverse(top->left);traverse(top->right);visit(top); // внутри вызовет free•Такой «стирающий» обход называетсятакже postorder обходом1 → 2 → 4 → 6 → 5 → 3Problem TT – дерево из обходов•На входе файл, содержащий preorder и inorder обходыдерева2 1 0 3 40 1 3 2 4•На выходе файл, содержащий дерево52 1 41 0 3•Теоретическое задание: подумайте хватит ли вамлюбой пары из трёх обходов?Поисковые деревья•Многие деревья, например ужерассмотренное выше, обладаютинтересным свойством•Для любого элемента все элементы влевом поддереве меньше него, а в правомвсе элементы больше него•Такие деревья называются поисковыми•Центрированный обход поисковогодерева даёт его узлы в сортированномпорядкеОбсуждение•Поисковые деревья называются поисковыми,потому что в них легко искать элемент•Дерево A не является поисковым и чтобы найти внём тройку надо просмотреть все узлы потратив() времени•Дерево Б является поисковым и чтобы найти внём четвёрку, мы идём от тройки направо, потомот пятёрки налево.

На поиск любого элементатратится времени, что гораздо лучше•Кроме того в поисковых деревьях легко делатьrange queriesДерево AДерево БАлгоритм RQ – поиск диапазонаstruct tree_t {struct tree_t *left, *right;int data;};typedef void (*visit_t)(int);void visit_range(struct tree_t *top, int l, int r, visit_t v) {if (NULL == top) return;if (r < top->data) visit_range(top->left);if (l > top->data) visit_range(top->right);v(root->data);}•Будут посещены узлы от l до r даже если в дереве нет значений l и rProblem IS – проверить поисковость•На входе файл содержащий дерево в обычномформате5 2 1 4 1 0 3•На выходе 1 если дерево поисковое и 0 если нет•В данном случае ответ 0 потому что узел 3 находитсяв левом поддереве узла 2•Но для дерева:5 3 1 4 1 0 2•Ответ: 1, так как это дерево поисковоеВетви надо мной уходят в темноту•Дополнительная и очень важная тема это повороты и балансировкапоисковых деревьев•Крайне интересны многомерные разновидности поисковых деревьев•Кроме поисковых деревьев популярностью в компьютерных наукахпользуются кучи (heaps) и лучи (tries)•Суффиксные деревья играют критическую роль в биоинформатике•Деревья и списки вместе с хеш-функциями используются в технологияхблокчейна•Увы, все эти прекрасные темы невозможно уложить в этот курс и нам надодвигаться дальшеЛитература•С11 ISO/IEC – "Information technology – Programminglanguages – C", 2011•& Brian W.

Kernighan, Dennis Ritchie – The Cprogramming language, 1988• Thomas H. Cormen – Introduction to Algorithms,2009• Donald E. Knuth – The Art of ComputerProgramming, 2011• Robert Sedgewick Algorithms, 4th edition, 2011• en.wikipedia.org/wiki/Universal_hashing.

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

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