О.В. Сенюкова - Сбалансированные деревья поиска (1113408)
Текст из файла
МОСКОВСКИЙ ГОСУДАРСТ ВЕННЫЙ УНИВЕРСИТЕТимени М . В . Л О М О Н О С О В АФакультетвычислительной математикии кибернетикиО.В. СЕНЮКОВАСБАЛАНСИРОВАННЫЕДЕРЕВЬЯ ПОИСКАМОСКВА2014МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М.В. ЛОМОНОСОВАФ ак ул ь т ет в ыч ис л и те л ьно й м а тем а т и к и и к иб ер н ет и к иО.В. СенюковаСБАЛАНСИРОВАННЫЕДЕРЕВЬЯ ПОИСКАУчебно-методическое пособиеÌîñêâà2003МОСКВА – 20141УДК 004.021:519.163(075.8)ББК 22.12:22.176я73С31Печатается по решению Редакционно-издательского советафакультета вычислительной математики и кибернетикиМГУ имени М.В. ЛомоносоваРецензенты:доцент А.А.
Белеванцев(факультет вычислительной математики и кибернетики МГУ имени М.В. Ломоносова);доцент Ю.С. Корухова(факультет вычислительной математики и кибернетики МГУ имени М.В. Ломоносова)С31Сенюкова О.В.Сбалансированные деревья поиска: Учебно-методическое пособие. –М.: Издательский отдел факультета ВМиК МГУ имени М.В.
Ломоносова(лицензия ИД N 05899 от 24.09.2001 г.); МАКС Пресс, 2014. – 68 c.ISBN 978-5-89407-528-0ISBN 978-5-317-04873-0Методическое пособие посвящено сбалансированным деревьям поиска. В начале пособия рассматриваются деревья поиска общего вида. Далее рассматриваются три вида сбалансированных деревьев поиска: АВЛдеревья, красно-черные деревья и самоперестраивающиеся деревья.Теоретический материал сопровождается иллюстрациями и примерамиреализации операций над деревьями на псевдокоде. В конце каждогораздела предлагается набор задач теоретического характера для самостоятельного решения.
Последний раздел пособия посвящен сравнениюрассмотренных видов деревьев и приведены примеры их практическогоиспользования.Пособие предназначено для студентов и преподавателей лекционногокурса «Алгоритмы и алгоритмические языки» и поддерживающего егокурса «Практикум на ЭВМ».УДК 004.021:519.163(075.8)ББК 22.12:22.176я73ISBN 978-5-89407-528-0ISBN 978-5-317-04873-0 Факультет ВМК МГУ имени М.В.
Ломоносова, 2014 Сенюкова О.В., 20142Оглавление1. Введение ......................................................................................... 42. Двоичные деревья поиска ............................................................. 42.1 Поиск узла в двоичном дереве поиска ................................. 62.2 Вставка узла в двоичное дерево поиска ............................ 102.3 Удаление узла из двоичного дерева поиска ......................
112.4 Балансировка двоичного дерева поиска ............................ 143. АВЛ-деревья ................................................................................ 173.1 Вставка узла в АВЛ-дерево ................................................ 183.2 Удаление узла из АВЛ-дерева ............................................ 263.3 Оценка сложности поиска в АВЛ-дереве .......................... 303.4 Задачи.................................................................................... 354. Красно-черные деревья ...............................................................
374.1 Вставка узла в КЧ-дерево ................................................... 384.2 Удаление узла из КЧ-дерева ............................................... 424.3 Оценка сложности поиска в КЧ-дереве ............................. 494.4 Задачи.................................................................................... 505. Самоперестраивающиеся деревья (splay trees) ......................... 515.1 Вставка узла в самоперестраивающееся дерево ...............
525.2 Удаление узла из самоперестраивающегося дерева ......... 535.3 Выполнение операции splay(T, k) ...................................... 555.4 Оценка сложности операцийнад самоперестраивающимся деревом ....................................... 585.5 Задачи.................................................................................... 646. Сравнение АВЛ-деревьев, КЧ-деревьеви самоперестраивающихся деревьев .............................................. 657. Литература ...................................................................................
6731. ВведениеДанное методическое пособие посвящено определенному видуструктур данных – сбалансированным деревьям поиска. В началепособия вводится понятие дерева поиска, на примерах рассматриваются его свойства, разбираются основные операции над ним:поиск, вставка и удаление узла. Далее подробно излагается теоретический материал по трем видам сбалансированных деревьевпоиска: АВЛ-деревьям, красно-черным деревьям и самоперестраивающимся (splay) деревьям.
Основные операции над этимидеревьями рассматриваются по шагам, с комментариями и иллюстрациями. Приводятся оценки сложности операций с доказательствами. Приводится описание реализации этих операций на псевдокоде. В конце каждого раздела предлагается набор задач теоретического характера для самостоятельного решения. Последнийраздел пособия посвящен сравнению рассмотренных видов деревьев и приведены примеры их практического использования.Пособие предназначено для студентов и преподавателей лекционного курса «Алгоритмы и алгоритмические языки» и поддерживающего его курса «Практикум на ЭВМ».Автор приносит глубокую благодарность рецензентам за ценныезамечания, а также Кириллу Батузову за помощь при подготовкепособия.2. Двоичные деревья поискаС развитием компьютерной техники проблема хранения и обработки больших объемов данных становилась все более актуальной.Возникла необходимость организации хранилища для большихобъемов данных, которое предоставляет возможность быстронаходить и модифицировать данные.
Один из способов организации такого хранилища — двоичные деревья поиска. Эту структуруданных можно описать на любом языке программирования, в котором есть составные типы данных.4Двоичное дерево представляет собой в общем случае неупорядоченный набор узлов, который либо пуст (пустое дерево) либо разбит на три непересекающиеся части:◦узел, называемый корнем;◦двоичное дерево, называемое левым поддеревом;◦двоичное дерево, называемое правым поддеревом.Таким образом, двоичное дерево — это рекурсивная структураданных.Каждый узел двоичного дерева можно представить в виде структуры данных, состоящей из следующих полей: данные, обладающие ключом, по которому их можноидентифицировать; указатель на левое поддерево; указатель на правое поддерево; указатель на родителя (необязательное поле).Значение ключа уникально для каждого узла.Описание узла двоичного дерева на языке программирования может выглядеть следующим образом:Cstruct BTNode{key_type key;struct BTNode *left;struct BTNode *right;struct BTNode *parent;};PascaltypeTree = ^BTNode;BTNode = recordkey: key_type;left: Tree;right: Tree;parent: Tree;end;Дерево поиска – это двоичное дерево, в котором узлы упорядочены определенным образом по значению ключей: для любого узла x5значения ключей всех узлов его левого поддерева меньше значения ключа x, а значения ключей всех узлов его правого поддеревабольше значения ключа x.
Поэтому для key_type, типа значенийключей, должна быть определена операции сравнения меньше.Рассмотрим выполнение основных операций над деревьями поиска:поиск узла в дереве, вставка узла в дерево, удаление узла из дерева.Далее, для простоты будем считать, что ключ и данные – это однои то же, и ключ имеет целочисленный тип.2.1 Поиск узла в двоичном дереве поискаПроцедура поиска узла по ключу заключается в том, что на каждом шаге значение искомого ключа сравнивается со значениемключа рассматриваемого узла, начиная с корня.
Если значение искомого ключа меньше, чем значение ключа рассматриваемого узла, то поиск продолжается в левом поддереве, если больше — то вправом поддереве. И так, пока не будет найден узел с искомымключом (см. Рис. 1(а)) или пока поиск не достигнет того узла, ниже которого этот узел не может находиться.
Если при поиске мыобнаруживаем, что узел далее надо искать, например, в правомподдереве, а оно пусто (как на Рис. 1(б)), следовательно, мы можем сделать вывод, что искомого ключа в дереве нет.Таким образом, алгоритм следует из определения дерева поиска.4444363130834248453689316430834248458964(а)(б)Рис. 1. Поиск узла по ключу. Направление поиска показанострелками: (а) поиск узла 48; (б) поиск узла 326Приведем рекурсивную реализацию операции поиска узла по ключу в двоичном дереве поиска.TREE-SEARCH(T, k)/* На вход подается дерево T, в котором производится поиск, и k– значение ключа. Возвращается узел дерева, в котором находится искомый ключ, или NULL, если узла с искомым ключом в деревенет.
*/1 x ← root[T]2 if x = NULL или k = key[x] then /* нерекурсивная ветвь */3return x4 if k < key[x] then5return TREE-SEARCH(left[x], k) /* вызываем функцию длялевого поддерева */6 else7return TREE-SEARCH(right[x], k) /* вызываем функциюдля правого поддерева */Более эффективная по времени и используемой памяти итеративная реализация операции поиска:INTERATIVE-TREE-SEARCH (T, k)/* На вход подается дерево T, в котором производится поиск, и k– значение ключа.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
