Читаем Prolog полностью

с ростом размера множества. Однако плохая сбалансированность дерева ведет к деградации производительности алгоритмов, работающие со справочником. В крайнем случае, двоичный справочник вырождается в список, как показано на рис.10. l. Форма справочника зависит от той последовательности, а которой в всего записываются элементы данных. В лучшей случае мы получаем хорошую балансировку и производительность порядка log n, а в худшем - производительность будет порядка n. Анализ показывает, что в среднем сложность алгоритмов внутри, добавить и удалить сохраняет порядок log n в допущении, что все возможные входные последовательности равновероятны. Таким образом, средняя производительность, к счастью, оказывается ближе к лучшему случаю, чек к худшему. Существует, однако, несколько довольно простых механизмов, которые поддерживают хорошую сбалансированность дерева, вне зависимости от входной последовательности, формирующей дерево. Эти механизмы гарантируют производительность алгоритмов внутри, добавить и удалить порядка log n даже в худшем случае. Один из этих механизмов - двоично-троичные деревья (кратко, 2-3 деревья), а другой - AVL-деревья.

2-3 дерево определяется следующим образом: оно или пусто, или состоит из единственной вершины, или удовлетворяет следующим условиям:

каждая внутренняя вершина имеет две или три дочерних вершины, и

все листья дерева находятся на одном и том же уровне.

Двоично-троичным (2-3) справочником называется 2-3 дерево, все элементы данных которого хранятся в листьях и упорядочены слева направо. На рис. 10.2 показан пример. Внутренние вершины содержат метки, равные минимальным элементам тех или иных своих поддеревьев, в соответствии со следующими правилами:

если внутренняя вершина имеет два поддерева, то она содержит минимальный элемент второго из них;

если внутренняя вершина имеет три поддерева, то она содержит минимальные элементы второго и третьего поддеревьев.

Рис. 10. 2.  2-3 справочник. Отмеченный путь показывает процесс поиска элемента 10.

При поиске элемента Х в 2-3 справочнике мы начинаем с корня и двигаемся в направлении самого нижнего уровня, руководствуясь при этом метками внутренних вершин дерева. Пусть корень содержит метки Ml и М2, тогда

если Х < M1, то поиск продолжается в левом поддереве, иначе

если Х < М2, то поиск продолжается в среднем поддереве, иначе -

в правом поддереве.

Если в корне находится только одна метка М, то переходим к левому поддереву при Х < М и к правому поддереву - в противоположном случае. Продолжаем применять сформулированные выше правила, пока не окажемся на самом нижнем уровне дерева, где и выяснится, найден ли элемент X, или же поиск потерпел неудачу.

Так как все листья 2-3 дерева находятся на одном и том же уровне, 2-3 дерево идеально сбалансировано с точки зрения глубины составляющих его поддеревьев. Все пути от корня до листа, которые мы проходим при поиске, имеют одну и ту же длину порядка log n, где n - число элементов, хранящихся в дереве.

При добавлении нового элемента данных 2-3 дерево может расти не только в глубину, но и в ширину. Каждая внутренняя вершина, имеющая два поддерева, может приобрести новое поддерево, что приводит к росту вширь. Если же, с другой стороны, у вершины уже есть три поддерева, и она должна принять еще одно, то она расщепляется на две вершины, каждая из которых берет на себя по два из имеющихся четырех поддеревьев. Образовавшаяся при этом новая вершина передается вверх по дереву для присоединения к одной из выше расположенных вершин. Если же эта ситуация возникает на самом высоком уровне, то дерево вынуждено "вырасти" на один уровень вверх. Рис. 10.3 иллюстрирует описанный принцип.

Рис. 10. 3.  Вставление нового элемента в 2-3 справочник. Дерево

растет сначала вширь, а затем уже вглубь.

Включение нового элемента в 2-3 справочник мы запрограммируем как отношение

        доб23( Дер, X, НовДер)

где дерево НовДер получено введением элемента Х в дерево Дер. Основную работу мы поручим двум дополнительным отношениям, которые мы назовем встав. Первое из них имеет три аргумента:

        встав( Дер, X, НовДер).

Здесь НовДер - результат вставления элемента Х в Дер. Деревья Дер и НовДер имеют одну и ту же глубину. Разумеется, не всегда возможно сохранить ту же глубину дерева. Поэтому существует еще одно отношение с пятью аргументами специально для этого случая:

        встав( Дер, X, НДа, Mб, НДб).

Имеется в виду, что при вставления Х в Дер дерево Дер разбивается на два дерева НДа и НДб, имеющих ту же глубину, что и Дер. Мб - это минимальный элемент из НДб. Пример показан на рис. 10.4.

Рис. 10. 4.  Объекты, показанные на рисунке, удовлетворяют отношению встав( Дер, 6, НДа, Мб, НДб).

2-3 деревья мы будем представлять в программе следующим образом:

nil представляет пустое дерево;

Перейти на страницу:

Похожие книги

C++ Primer Plus
C++ Primer Plus

C++ Primer Plus is a carefully crafted, complete tutorial on one of the most significant and widely used programming languages today. An accessible and easy-to-use self-study guide, this book is appropriate for both serious students of programming as well as developers already proficient in other languages.The sixth edition of C++ Primer Plus has been updated and expanded to cover the latest developments in C++, including a detailed look at the new C++11 standard.Author and educator Stephen Prata has created an introduction to C++ that is instructive, clear, and insightful. Fundamental programming concepts are explained along with details of the C++ language. Many short, practical examples illustrate just one or two concepts at a time, encouraging readers to master new topics by immediately putting them to use.Review questions and programming exercises at the end of each chapter help readers zero in on the most critical information and digest the most difficult concepts.In C++ Primer Plus, you'll find depth, breadth, and a variety of teaching techniques and tools to enhance your learning:• A new detailed chapter on the changes and additional capabilities introduced in the C++11 standard• Complete, integrated discussion of both basic C language and additional C++ features• Clear guidance about when and why to use a feature• Hands-on learning with concise and simple examples that develop your understanding a concept or two at a time• Hundreds of practical sample programs• Review questions and programming exercises at the end of each chapter to test your understanding• Coverage of generic C++ gives you the greatest possible flexibility• Teaches the ISO standard, including discussions of templates, the Standard Template Library, the string class, exceptions, RTTI, and namespaces

Стивен Прата

Программирование, программы, базы данных
1001 совет по обустройству компьютера
1001 совет по обустройству компьютера

В книге собраны и обобщены советы по решению различных проблем, которые рано или поздно возникают при эксплуатации как экономичных нетбуков, так и современных настольных моделей. Все приведенные рецепты опробованы на практике и разбиты по темам: аппаратные средства персональных компьютеров, компьютерные сети и подключение к Интернету, установка, настройка и ремонт ОС Windows, работа в Интернете, защита от вирусов. Рассмотрены не только готовые решения внезапно возникающих проблем, но и ответы на многие вопросы, которые возникают еще до покупки компьютера. Приведен необходимый минимум технических сведений, позволяющий принять осознанное решение.Компакт-диск прилагается только к печатному изданию книги.

Юрий Всеволодович Ревич

Программирование, программы, базы данных / Интернет / Компьютерное «железо» / ОС и Сети / Программное обеспечение / Книги по IT
3ds Max 2008
3ds Max 2008

Одни уверены, что нет лучшего способа обучения 3ds Мах, чем прочитать хорошую книгу. Другие склоняются к тому, что эффективнее учиться у преподавателя, который показывает, что и как нужно делать. Данное издание объединяет оба подхода. Его цель – сделать освоение 3ds Мах 2008 максимально быстрым и результативным. Часто после изучения книги у читателя возникают вопросы, почему не получился тот или иной пример. Видеокурс – это гарантия, что такие вопросы не возникнут: ведь автор не только рассказывает, но и показывает, как нужно работать в 3ds Мах.В отличие от большинства интерактивных курсов, где работа в 3ds Мах иллюстрируется на кубиках-шариках, данный видеокурс полностью практический. Все приемы работы с инструментами 3ds Мах 2008 показаны на конкретных примерах, благодаря чему после просмотра курса читатель сможет самостоятельно выполнять даже сложные проекты.

Владимир Антонович Верстак , Владимир Верстак

Программирование, программы, базы данных / Программное обеспечение / Книги по IT