Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 4.10. СЛОВАРИ И ОЧЕРЕДИ С ПРИОРИТЕТАМИВ этом разделе мы изучим основные преобразования, требуемые для реализации словарей и очередей с приоритетами. На протяжении всего раздела будем предполагать, что элементы приписаны листьям 2-3-дерева в порядке слева направо и в каждом нелисте Чтобы в 2-3-дерево вставить новый элемент а, надо найти место для нового листа Если из узла Пример 4.9. Если в 2-3-дерево, изображенное на рис. 4.27,а, вставляется элемент 2, то получается 2-3-дерево, изображенное на рис. 4.27,6.
Рис. 4.27. Вставка в 2-3-дерево: а — дерево перед вставкой; Теперь предположим, что сына оставим сыновьями узла Пример 4.10. Если в 2-3-дерево на рис. 4.27,а, вставляется элемент 4, то новый лист с меткой 4 надо сделать самым левым сыном узла с. Поскольку у с уже есть три сына, строим новый узел с. Затем делаем листья 4 и 5 сыновьями узла с, а листья 6 и 7 — сыновьями узла с. Теперь делаем с сыном узла а. Но поскольку у а уже есть три сына, строим новый узел а. Делаем узлы
Рис. 4.28. Дерево с рис. 4.27, а после вставки элемента 4. Алгоритм 4.4. Вставка нового элемента в 2-3-дерево Вход. Непустое Выход. Преобразованное 2-3-дерево с новым листом, помеченным а. Метод. По условию 1. Если 2. Если
Рис. 4.29. Процедура лист I с меткой а. Если
Рис. 4.30. Процедура в корень. Другие очевидные изменения, корректирующие значения Теорема 4.6. Алгоритм 4.4 вставляет новый элемент в Доказательство. Очевидная индукция по числу вызовов процедуры ПОИСК показывает, что новый лист становится сыном того узла, какого надо. Порядок исходных листьев не затрагивается. Что касается времени работы, то в силу леммы 4.6 высота Элемент а можно удалить из 2-3-дерева способом, по существу обратным к вставке. Пусть а — метка листа Случай 1. Если Случай 2. Если I — сын узла, имеющего трех сыновей, удаляем его. Случай 3. Если I — сын узла, имеющего двух сыновей а) б) Пример 4.11. Из 2-3-дерева на рис. 4.28 удалим элемент 4. Лист с меткой 4 является сыном узла с, у которого два сына. Поэтому делаем лист с меткой 5 самым правым сыном узла Узел с — сын узла а, у которого два сына. Узел а — правый брат узла а. Поэтому по симметрии делаем
Рис. 4.31. Дерево с рис. 4.28 после удаления элемента 4. Узел а — сын корня. Применяя случай За, делаем а корнем остающегося дерева (рис. 4.31). Формальную детализацию процесса, а также доказательство того, что на 2-3-дереве с Итак, операции ПРИНАДЛЕЖАТЬ, ВСТАВИТЬ и УДАЛИТЬ на 2-3-дереве с Исследуем теперь операцию MIN. Наименьший элемент в 2-3-дереве расположен в самом левом листе, который, конечно, можно найти за
|
1 |
Оглавление
|