Методические указания алгоритмы и структуры данных. Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию Часть 2 Выпуск 1606
 Скачать 429.85 Kb.
|
2. ДЕРЕВЬЯ ДВОИЧНОГО ПОИСКАДерево двоичного поиска (ДДП) — это способ хранения множества в форме расширяемого упорядоченного списка с сохранением упорядоченности при вставке новых элементов без перемещения уже имеющихся. ДДП — это дерево с нагруженными узлами, вес в любом узле которого больше любого веса в левом его поддереве и не больше любого веса в правом поддереве. Количество шагов алгоритма поиска элемента множества в таком дереве не превышает его высоты, т. е. имеет сложность O(log n). Такую же сложность имеют операции вставки нового элемента в дерево и удаления элемента. ДДП можно получить из упорядоченной последовательности ключей, если двоичное дерево соответствующей мощности разметить внутренним (симметричным) способом, а затем заменить номера узлов соответствующими элементами последовательности. Если последовательность хранится в массиве, то построить ДДП можно методом деления пополам: поместить в корень дерева средний по порядку элемент, затем рекурсивно создать левое поддерево из первой половины последовательности, а правое — из второй. Node * Build(int a, int b, int * data) //Сборка ДДП из массива узлов data { if (b <= a) return 0; int c = (a + b) /2; Node * s = new Node (data[ c ]); s->left = Build(a, c, data); s->right = Build(c+1, b, data); return s; } Недостаток ДДП — в том, что оно хорошо работает только в том случае, если сбалансировано, т. е. длины путей из корня в любой лист примерно одинаковы. Однако при поэлементной вставке в дерево упорядоченной последовательности дерево вырождается, превращаясь в линейный список. Поиск, вставка и удаление в таком дереве будут выполняться не за логарифмическое, а за линейное время. Вероятность вырождения весьма велика. Так, из 7 узлов можно образовать только одно полностью сбалансированное дерево, а полностью вырожденных — 64. Поэтому алгоритмы работы с ДДП часто дополняют автобалансировкой после вставки и удаления. Наиболее употребительны следующие схемы: 1) АВЛ-деревья. Разность высот поддеревьев любого узла дерева не превышает 1. Информация о разности высот хранится в узле и используется для его перестройки после вставки и удаления узла; 2) красно-чёрные деревья. Узлы красятся в один из двух цветов — чёрный или красный. Если узел — красный, его сыновья — обязательно чёрные. Вставляемый узел — всегда красный. При появлении цепочки из двух красных узлов дерево перестраивается; 3) 2–3-деревья. Данные хранятся в листьях, над которыми делается надстройка из управляющих узлов, каждый из которых может иметь 2 или 3 сына и содержит наибольшие значения ключей в левом и в среднем поддеревьях, что необходимо для операции поиска. Если в результате вставки или удаления у управляющего узла оказывается 1 или 4 сына, дерево перестраивается. Подробнее о ДДП и деревьях с автобалансировкой см. [1, с. 457–468], [2, с. 523–566], [5, с. 341–344]. Двуместные операции над множествами в ДДП можно выполнять, используя примитивы проверка–вставка–удаление. Очевидно, что временная сложность двуместной операции при этом будет в среднем O(n log n). В худшем случае, при вырожденных деревьях, двуместная операция потребует O(n2) времени. Более того, если алгоритм порождает упорядоченную последовательность ключей, ДДП, полученное в результате последовательности вставок, всегда будет вырожденным. Однако можно использовать тот факт, что из ДДП легко получить упорядоченную последовательность ключей внутренним обходом. Применив такой обход к двум ДДП одновременно, можно обработать последовательности алгоритмом слияния, модифицировав его для нужной операции над множествами. Результат в виде упорядоченной последовательности записывается в массив, из которого затем описанным ранее методом деления пополам строится новое ДДП. Этот способ обеспечивает получение результата за время O(n) независимо от формы исходных ДДП, а результат всегда получается сбалансированным. ДДП сами по себе мало пригодны для хранения множеств с повторениями, поскольку дубликаты ключей искажают форму дерева, образуя в нём мёртвые зоны: группы указателей, которые никогда не используются. Ситуацию можно улучшить, если вместо дубликатов ключей хранить в каждом узле значение кратности (1 или больше). Если же дубликаты должны быть представлены явно, их можно хранить в узлах как цепочки переполнения, по аналогии с хеш-таблицей. 2.1. Практикум по темеПеределать программу, составленную по теме «Хеш-таблицы», под использование деревьев двоичного поиска. Вид дерева определить из табл. 2.1 по номеру варианта индивидуального задания. Таблица 2.1Варианты вида дерева для реализации в теме «Деревья двоичного поиска»
Примечание. В таблице использованы следующие обозначения: ДДП — дерево двоичного поиска (без автобалансировки); АВЛ-д — АВЛ-дерево (с автобалансировкой); К-ч-д — красно-чёрное дерево (с автобалансировкой); 2–3-д — 2–3-дерево (всегда сбалансированное). 2.2. Требования к отчётуВ выводах отчёта по теме «Деревья двоичного поиска» попробуйте оценить, насколько удачен выбор типа ДДП для вашего варианта задания на обработку множеств. 2.3. Контрольные вопросы1. Каким способом следует разметить дерево, чтобы в нём был возможен двоичный поиск? Как его следует нагрузить? 2. Почему для операций с двоичным деревом дают две оценки сложности — «в худшем случае» и «в среднем»? Почему не рассматривается «лучший» случай? 3. Отчего деревья двоичного поиска вырождаются? 4. Можно ли воспрепятствовать вырождению ДДП? 5. Каков оптимальный алгоритм двуместной операции над множествами, представленными деревьями двоичного поиска? 6. Какова временная сложность такой операции и как сказывается на ней возможное вырождение деревьев? 7. Может ли при двуместной операции над множествами в ДДП получиться вырожденное дерево-результат? 8. Можно ли хранить в дереве двоичного поиска множество с повторениями? 9. Какая структура данных требует больше памяти для хранения множества — хеш-таблица или дерево двоичного поиска? 10. Какая из них быстрее работает? 11. Как сделать не вырождающееся ДДП? Зачем оно может понадобиться? |