Таблицы символов и деревья бинарного поиска

Программа 12.2. АТД таблицы символов

В данном интерфейсе определены операции для простой таблицы символов: инициализация, возврат значения счетчика элементов, поиск элемента с заданным ключом, добавление нового элемента, удаление элемента, выбор k-го наименьшего элемента и вывод элементов в порядке возрастания ключей (в указанный выходной поток).

template <class Item, class Key>
class ST
  { private:
    // Код, зависящий от реализации 
    public:
      ST(int);
    int count();
    Item search(Key) ;
    void insert(Item);
    void remove(Item);
    Item select(int);
    void show(ostream);
  };
      

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

Обработку элементов с повторяющимися ключами можно выполнять различными способами. Один из подходов - потребовать, чтобы первичная структура данных поиска содержала только элементы с различными ключами и, для каждого ключа, ссылку на список элементов с такими же ключами. То есть в первичной структуре данных используются элементы, содержащие ключ и ссылку, а элементы с одинаковыми ключами отсутствуют. Для некоторых приложений эта организация удобна, поскольку все элементы с данным искомым ключом могут быть получены одной операцией найти или удалены одной операцией удалить. С точки зрения реализации такая организация эквивалентна поручению обработки повторяющихся ключей клиенту.

Вторая возможность - оставлять элементы с одинаковыми ключами в первичной структуре данных поиска и возвращать любой элемент в результате поиска по данному ключу. Такое соглашение проще для приложений, которые обрабатывают элементы по одному, а порядок обработки элементов с одинаковыми ключами не важен. Но с точки зрения разработки алгоритма это может оказаться неудобным, поскольку может потребовать включения в интерфейс механизма выборки всех элементов с данным ключом или вызова указанной функции для каждого элемента с заданным ключом.

Третья возможность - считать, что каждый элемент имеет уникальный идентификатор (кроме ключа) и потребовать, чтобы функция найти при заданном ключе отыскивала элемент с данным идентификатором. Или может потребоваться какой-либо более сложный механизм. Эти рассуждения применимы ко всем операциям с таблицами символов при наличии повторяющихся ключей. Нужно ли удалить все элементы с данным ключом, или любой элемент с этим ключом, или конкретный элемент (для этого потребуется реализация с дескрипторами элементов)? При описании реализаций таблиц символов мы будем неформально указывать способ обработки элементов с одинаковыми ключами, не обязательно рассматривая каждый механизм для каждой реализации.

Программа 12.3 - пример клиентской программы, который иллюстрирует некоторые из упомянутых выше соглашений для реализаций таблиц символов. Таблица символов используется в ней для поиска различных значений в последовательности ключей (сгенерированных случайным образом или считанных из стандартного ввода), которые затем выводятся в порядке возрастания.

Как обычно, следует иметь в виду, что различные реализации операций на таблицах символов имеют различные характеристики производительности, которые могут зависеть от конкретного набора операций. Одно приложение может использовать операцию вставить сравнительно редко (возможно, для построения таблицы), а затем выполнять очень большое количество операций найти; другое может выполнять в относительно небольших таблицах огромное количество операций вставить и удалить, вперемешку с операциями найти. Не в каждой реализации будут поддерживаться все операции, и некоторые из них могут обеспечивать эффективную поддержку определенных операций за счет других, неявно предполагая, что менее эффективные операции выполняются редко.

Программа 12.3. Пример клиента для таблицы символов

В этой программе таблица символов используется для поиска различных ключей в случайно сгенерированной или считанной из стандартного ввода последовательности. Для каждого ключа вызывается функция search - чтобы проверить, встречался ли такой ключ раньше. Если нет, элемент с этим ключом вставляется в таблицу символов. Типы ключей и элементов, а также абстрактные операции с ними определены в файле Item.cxx (см., например, программу 12.1).

#include <iostream.h>
#include <stdlib.h>
#include "Item.cxx"
#include "ST.cxx"
int main(int argc, char *argv[])
  { int N, maxN = atoi(argv[1]), sw = atoi(argv[2]);
    ST<Item, Key> st(maxN); 
    for (N = 0; N < maxN; N++)
      { Item v;
        if (sw) v.rand();
        else if (!v.scan()) break;
        if (!(st.search(v.key())).null()) continue;
        st.insert(v);
      }
    st.show(cout);
    cout << endl; cout << N << " ключей" << endl;
    cout << st.count() << " различных ключей" << endl;
  }
      

Каждая из базовых операций в интерфейсе таблицы символов в каких-то случаях важна, поэтому для эффективного использования различных сочетаний операций предлагается множество базовых вариантов реализации. В этой и нескольких последующих главах основное внимание будет уделено реализациям базовых функций создать, вставить и найти, с некоторыми пояснениями, по мере необходимости, относительно функций удалить, выбрать, сортировать и объединить. Огромное множество рассматриваемых алгоритмов порождено различием характеристик производительности разных сочетаний базовых операций, и, возможно, ограничениями на значения ключей, размером элементов и другими факторами.

В этой главе мы встретимся с реализациями, в которых среднее время выполнения операций найти, вставить, удалить и выбрать для случайных ключей пропорционально логарифму количества элементов в словаре, а операция сортировать выполняется за линейное время. В мы рассмотрим способы достижения этого уровня производительности, и в разделе 12.2 будет приведена одна, а в и - несколько реализаций с постоянным временем выполнения.

Имеются и многие другие операции с таблицами символов. Примерами могут служить найти от метки, при котором поиск может начинаться с точки, в которой завершился предыдущий поиск; найти в диапазоне, когда нужно подсчитать или показать все узлы, попадающие в заданный интервал; и - при наличии концепции расстояния между ключами - поиск ближайшего соседа, при котором выполняется поиск ключей, ближайших к заданному. Такие операции будут рассматриваться в части VI, при изучении геометрических алгоритмов.

Упражнения

12.1. Напишите реализацию класса Item (аналогичную программе 12.1), который позволит в реализациях таблиц символов обрабатывать элементы, состоящие только из целочисленных ключей.

12.2. Напишите реализацию класса Item (аналогичную программе 12.1), который позволит в реализациях таблиц символов обрабатывать элементы, состоящие только из строковых ключей в стиле C. Класс должен содержать буфер для строк, как в программе 6.11.

12.3. Используя АТД таблицы символов из программы 12.2, реализуйте АТД стека и очереди.

12.4. Используя АТД таблицы символов из программы 12.2, реализуйте АТД очереди с приоритетами, который поддерживает операции удаления как максимального, так и минимального элементов.

12.5. Используя АТД таблицы символов из программы 12.2, реализуйте сортировку массива, совместимую с реализациями из глав 6-10.

12.6. Добавьте в программу 12.2 объявления деструктора, конструктора копирования и перегруженной операции присваивания, чтобы преобразовать ее в АТД первого класса (см. и 9.5).

12.7. Определите интерфейс АТД таблицы символов, позволяющий клиентским программам удалять заданные дескрипторами элементы и изменять ключи (см. и).

12.8. Приведите интерфейс и реализацию для элементов с двумя полями: 16-битным целочисленным ключом и строкой в стиле C, которая содержит информацию, связанную с этим ключом.

12.9. Укажите среднее количество различных ключей, которые найдет программа-драйвер (программа 12.3) среди N случайных положительных целых чисел, меньших 1000, для N = 10, 102, 103, 104 и 105 . Найдите ответ эмпирически, аналитически или обоими методами.

Распределяющий поиск

Предположим, что значения ключей представляют собой различные небольшие числа, как, например, в программе 12.4. В этом случае простейший алгоритм поиска основывается на хранении элементов в массиве, индексированном значениями ключей - так сделано в реализации, приведенной в программе 12.4. Ее код весьма прост: оператор new[] заносит во все элементы значение nullItem, затем можно вставить элемент со значением ключа k, просто записав его в st[k], и найти элемент со значением ключа k, выбрав его из st[k]. Чтобы удалить элемент со значением ключа k, в st[k] записывается значение nullItem. Реализации операций выбрать, сортировать и подсчитать в программе 12.4 используют линейный просмотр массива с пропуском пустых элементов. Данная реализация оставляет клиенту решение задачи обработки элементов с повторяющимися ключами и проверку таких условий, как выполнение операции удалить для ключа, отсутствующего в таблице. Эта реализация служит отправной точкой для всех реализаций таблиц символов, которые рассматриваются в этой главе и лекциях 13-15.

Программа 12.4. Таблица символов, основанная на индексируемом значениями ключей массиве

В данной реализации предполагается, что значения ключей - положительные целые числа, меньшие сигнального значения M - используются в качестве индексов массива. Конструктор Item создает элементы со значениями ключей, равными сигнальному значению, чтобы конструктор ST мог найти в пустом элементе значение M. Основные затраты этого метода - объем памяти, необходимый при большом размере сигнального значения, и время, необходимое конструктору ST, когда значение N мало по сравнению с M.

template <class Item, class Key>
class ST
  { private:
      Item nullItem, *st;
      int M;
    public:
      ST(int maxN)
        { M = nullItem.key(); st = new Item[M]; }
      int count()
        { int N = 0; 
for (int i = 0; i < M; i++)
  if (!st[i].null()) N+ + ;
return N;
        }
      void insert(Item x)
        { st[x.key()] = x; }
      Item search(Key v)
        { return st[v]; }
      void remove(Item x)
        { st[x.key()] = nullItem; }
      Item select(int k)
        { for (int i = 0; i < M; i++)
  if (!st[i].null())
    if (k- == 0) return st[i];
return nullItem;
        }
      void show(ostream os)
        { for (int i = 0; i < M; i++)
if (!st[i].null()) st[i].show(os); }
  };
      

Она пригодна для различных клиентов и различных типов элементов. Компилятор проверит, следуют ли интерфейс, реализация и клиент одним и тем же соглашениям.

Операция индексации, на которой основан распределяющий поиск, совпадает с базовой операцией в методе сортировки распределяющим подсчетом, рассмотренном в . Когда возможно, следует выбирать этот метод, поскольку вряд ли операции найти и вставить можно реализовать эффективнее.

Если элементы вообще отсутствуют (имеются только ключи), можно использовать битовую таблицу. В этом случае таблица символов называется таблицей существования (existence table), поскольку ее к-й разряд можно рассматривать как признак существования значения к в множестве ключей таблицы. Например, используя на 32-разрядном компьютере таблицу из 313 слов, этот метод позволяет быстро выяснить, используется ли уже конкретный 4-значный номер телефонного коммутатора (см. упражнение 12.14).

Программа 12.4 не обрабатывает повторяющиеся ключи, и в ней предполагается, что значения ключей лежат в пределах между 0 и , посвященной хешированию, где для реализации таблиц символов для любых ключей используется этот подход - преобразование ключей из потенциально широкого диапазона в узкий и выполнение специальной обработки элементов с повторяющимися ключами. Пока будем считать, что старый элемент с ключом, равным ключу вставляемого элемента, может быть либо молча проигнорирован (как в программе 12.4), либо считаться ошибкой (см. упражнение 12.10).

Реализация операции подсчитать в программе 12.4 - пример " ленивого " подхода, когда действия выполняются только при вызове функции count. Альтернативный ( " энергичный " ) подход заключается в использовании локальной переменной для счетчика непустых позиций таблицы с увеличением значения этой переменной при вставке в позицию таблицы, содержащую nullItem, и с уменьшением счетчика при удалении из позиции таблицы, не содержащей nullItem (см. упражнение 12.11). " Ленивый " подход предпочтительнее, если операция подсчитать используется редко (или вообще не используется), а количество возможных значений ключей мало; в остальных случаях предпочтительнее " энергичный " подход. Для подпрограммы библиотеки общего назначения лучше использовать " энергичный " подход, поскольку он обеспечивает оптимальную производительность в худшем случае при небольшом постоянном коэффициенте увеличения затрат на выполнение операций вставить и удалить. Для внутреннего цикла в приложении с очень большим количеством операций вставить и удалить, но незначительным количеством операций подсчитать " ленивый " подход удобнее, поскольку обеспечивает наиболее быструю реализацию часто выполняемых операций. Как мы уже неоднократно убеждались, подобная дилемма типична для разработки АТД, которые должны поддерживать различные наборы операций.

При разработке интерфейса общего назначения приходится принимать и ряд других решений. Например, должен ли диапазон ключей быть одинаковым для всех объектов или различным для различных объектов? При выборе последнего варианта может потребоваться добавление параметров в конструктор и функция, предоставляющая клиенту доступ к диапазону ключей.

Индексируемые значениями ключей массивы удобны для многих приложений, но они неприменимы, если ключи не попадают в узкий диапазон. И можно считать, что эта и несколько последующих глав посвящены разработке решений для случая, когда диапазон возможных значений ключей столь широк, что невозможно использовать индексированную таблицу с одним потенциальным местом для каждого ключа.

Упражнения

12.10. Реализуйте АТД таблицы символов первого класса (см. упражнение 12.6), используя динамически размещаемые массивы с индексированием по ключам.

12.11. Измените реализацию в программе 12.4, чтобы обеспечить " энергичную " реализацию функции count (с помощью отслеживания количества непустых записей).

12.12. Измените реализацию из упражнения 12.10, чтобы обеспечить " энергичную " реализацию функции count (см. упражнение 12.11).

12.13. Разработайте версию программы 12.4, в которой используется функция h(Key), преобразующая ключи в неотрицательные целые числа, меньшие M - так, чтобы никакие два ключа не отображались одним и тем же целым числом. (Это усовершенствование делает реализацию полезной, если ключи лежат в узком диапазоне (не обязательно начинающемся с 0) и в других простых случаях.)

12.14. Разработайте версию программы 12.4 для случая, если элементы представляют собой ключи, являющиеся положительными целыми числами, меньшими M (без какой-либо связанной информации). В этой реализации используйте динамически размещаемый массив, состоящий приблизительно из M/bitword слов, где bitword - количество битов в одном слове в используемой компьютерной системе.

12.15. Используйте реализацию из упражнения 12.14 для экспериментального определения среднего значения и среднеквадратичного отклонения количества различных целых чисел в случайной последовательности N неотрицательных целых чисел, меньших N, для N, близкого к объему памяти, который доступен программе в используемом компьютере, и выраженному в количестве битов (см. программу 12.3)

Последовательный поиск

В общем случае, когда значения ключей относятся к слишком большому диапазону, чтобы их можно было использовать в качестве индексов, один из простых подходов к реализации таблиц символов - упорядоченное хранение элементов в последовательном массиве. Когда требуется вставить новый элемент, мы вставляем его в массив, сдвигая большие элементы на одну позицию, как при сортировке вставками; когда необходимо выполнить поиск, выполняется последовательный просмотр массива. Поскольку массив упорядочен, при встрече ключа больше искомого можно сделать вывод о неудачном завершении поиска. Более того, благодаря упорядоченности массива реализация операций выбрать и сортировать тривиальна. Программа 12.5 является реализацией таблицы символов, основанной на этом подходе.

В программе 12.5 можно было бы несколько усовершенствовать внутренний цикл в реализации операции найти - с помощью сигнального значения исключить проверку выхода за пределы массива в том случае, если ни один из элементов таблицы не содержит искомого ключа. А именно, можно зарезервировать для служебных целей позицию после конца массива, а перед поиском заполнять ее поле ключа искомым значением. В таком случае поиск всегда будет завершаться на элементе, содержащем искомый ключ, а находится ли ключ в таблице, всегда можно определить, проверив, находится ли найденный элемент в массиве или за его пределами. (Этот прием более уместен при работе с неупорядоченными массивами (см. следующий абзац), когда неудачные поиски вынуждены доходить до конца массива. - прим. перев.)

Программа 12.5. Таблица символов (упорядоченная) на основе массива

Подобно программе 12.4, в этой реализации используется массив элементов, но здесь не требуется, чтобы ключи были небольшими целыми числами. Упорядоченность массива обеспечивается тем, что при вставке нового элемента большие элементы сдвигаются, освобождая место, как при сортировке вставками. Потом функция search выполняет просмотр массива, когда нужно найти элемент с заданным ключом. Если просмотр дошел до элемента с большим ключом, возвращается значение nullItem. Реализации функций select и sort тривиальны, а реализация функции remove оставлена в качестве упражнения (см. упражнение 12.16).

template <class Item, class Key>
class ST
  { private:
      Item nullItem, *st;
      int N;
    public:
      ST(int maxN)
        { st = new Item[maxN+1]; N = 0; }
      int count()
        { return N; }
      void insert(Item x)
        { int i = N++; Key v = x.key();
while (i > 0  v < st[i-1].key())
  { st[i] = st[i-1]; i--; }
st[i] = x;
        }
      Item search(Key v)
        { for (int i = 0; i < N; i++)
  if (!(st[i].key() < v)) break;
if (v == st[i].key()) return st[i];
return nullItem;
        }
      Item select(int k)
        { return st[k]; }
      void show(ostream os)
        { int i = 0; while (i < N) st[i++].show(os); }
  } ;
      

Можно использовать другой подход и создать реализацию, в которой упорядоченность элементов в массиве не обязательна. При вставке новый элемент помещается в конец массива; во время поиска осуществляется последовательный просмотр массива. Характерная особенность этого подхода состоит в том, что операция вставить выполняется быстро, а операции выбрать и сортировать требуют значительно большего объема работы (для обеих требуется один из методов, описанных в лекциях 7-10) . Удаление элемента с заданным ключом можно выполнить, найдя его, а затем переместив в его позицию последний элемент массива и уменьшив размер массива на 1; удаление всех элементов с заданным ключом реализуется повторением этой операции. Если доступен дескриптор, позволяющий определить индекс элемента в массиве, то поиск не требуется, и операция удалить выполняется за постоянное время.

Еще один простой вариант реализации таблицы символов - использование связного списка. В этом случае можно также хранить список в упорядоченном виде, для упрощения поддержки операции сортировать, либо оставить его неупорядоченным, для ускорения операции вставить. В программе 12.6 реализован второй подход. Как обычно, преимущество применения связных списков по сравнению с массивами состоит в том, что необязательно заранее точно определять максимальный размер таблицы, а недостаток - в дополнительном расходе памяти (под ссылки) и невозможности эффективной поддержки операции выбрать.

Подходы с использованием неупорядоченного массива и неупорядоченного списка оставлены для самостоятельной проработки (см. упражнения 12.20 и 12.21). Все четыре подхода (массив или список, упорядоченный или неупорядоченный) могут взаимозаменяемо использоваться в приложениях, отличаясь только временем выполнения и объемом требуемой памяти. В этой и нескольких последующих главах мы рассмотрим различные подходы к решению задачи реализации таблиц символов.

Хранение элементов в упорядоченном виде иллюстрирует мысль, что в общем случае в реализациях таблиц символов ключи используются для структурирования данных, обеспечивающего быстрый поиск. Такая структура может поддерживать быстрые реализации ряда операций, но при этом следует учитывать затраты на поддержку самой структуры, которые могут привести к замедлению других операций. Мы еще увидим много примеров этому. Например, в приложении, где часто требуется функция сортировать, лучше выбрать упорядоченное представление (массивом или списком), поскольку такая структура таблицы делает реализацию функции сортировать тривиальной, в отличие от необходимости полной реализации сортировки. В приложении, в котором заведомо потребуется часто выполнять операцию выбрать, лучше использовать представление упорядоченным массивом, т.к. эта структура таблицы обеспечивает постоянное время выполнения операции выбрать. А вот время выполнения операции выбрать в связном списке линейно зависит от количества элементов, даже если список упорядочен.

Программа 12.6. Таблица символов (неупорядоченная) на основе связного списка

В данной реализации операций создать, подсчитать, найти и вставить используется односвязный список, каждый узел которого содержит элемент с ключом и ссылкой. Функция insert помещает новый элемент в начало списка и тратит на это постоянное время. Для выполнения просмотра списка функция-член search использует приватную рекурсивную функцию searchR.

Поскольку список не упорядочен, реализации операций выбрать и сортировать опущены.

#include <stdlib.h>
template <class Item, class Key>
class ST
  { private:
    Item nullItem;
    struct node
      { Item item; node* next;
        node(Item x, node* t)
{ item = x; next = t; }
        } ;
        typedef node *link;
        int N;
        link head;
        Item searchR(link t, Key v)
{ if (t == 0) return nullItem;
  if (t->item.key() == v) return t->item;
  return searchR(t->next, v);
}
public:
  ST(int maxN)
  { head = 0; N = 0; } int count()
      { return N; }
    Item search(Key v)
      { return searchR(head, v); }
    void insert(Item x)
      { head = new node(x, head); N++; }
  };
      

Чтобы подробнее проанализировать последовательный поиск для случайных ключей, сначала рассмотрим затраты на вставку новых ключей, отдельно для случаев успешного и неудачного поиска. Первый часто называют попаданием при поиске, а второй - промахом при поиске. Нас интересуют затраты как для попаданий, так и для неудач, в среднем и худшем случаях. Вообще-то в реализации с использованием упорядоченного массива (см. программу 12.5) каждый элемент проверяется двумя операциями сравнения (== и <). В главах 12-16 в целях анализа мы будем считать эту пару одним сравнением, поскольку обычно их можно эффективно объединить с помощью низкоуровневой оптимизации.

Построение упорядоченных таблиц с помощью последовательных вставок по своей сути эквивалентно выполнению алгоритма сортировки вставками из . Общее время, необходимое для построения таблицы, квадратично зависит от количества элементов, поэтому для построения больших таблиц этот метод неприменим. Однако если в небольшой таблице нужно выполнять очень большое количество операций найти, то поддержка упорядоченности элементов вполне оправданна, поскольку в соответствии с леммами 12.3 и 12.4 этот подход может вдвое уменьшить время при неудачном поиске. Если элементы с повторяющимися ключами не должны храниться в таблице, то дополнительные затраты на поддержку упорядоченности таблицы не столь велики, как может показаться, т.к. вставка выполняется только после неудачного поиска и, следовательно, время, затрачиваемое на вставку, пропорционально времени, затрачиваемому на поиск.

С другой стороны, если элементы с повторяющимися ключами могут присутствовать в таблице, то для неупорядоченной таблицы можно реализовать операцию вставить с постоянным временем выполнения. Использование неупорядоченной таблицы предпочтительнее для приложений, в которых выполняется очень большое количество операций вставить при сравнительно небольшом числе операций найти.

Помимо учета этих различий, приходится, как обычно, идти на компромисс: для реализаций с использованием связных списков требуется дополнительный объем памяти для ссылок, а для реализаций с использованием массивов необходимо заранее знать максимальный размер таблицы или же предусмотреть увеличение таблицы во время работы (см. ). Кроме того, как было сказано в разделе 12.9, использование связных списков дает гибкость, позволяющую эффективно реализовать другие операции наподобие объединить и удалить.

Эти результаты во взаимосвязи с другими алгоритмами, рассматриваемыми далее в этой главе и и , сведены в таблицу 12.1. В разделе 12.4 будет рассмотрен бинарный поиск, сводящий время поиска до lg N, и поэтому широко используемый при работе со статическими таблицами (когда вставки выполняются сравнительно редко).

В каждой ячейке этой таблицы представлено (с точностью до постоянного множителя) время выполнения как функция от количества элементов в таблице N и размера таблицы M (если он отличен от N) для реализаций, в которых новые элементы можно вставить независимо от наличия в таблице элементов с таким ключом. Элементарные методы (первые четыре строки) требуют постоянного времени выполнения для некоторых операций и линейного времени для остальных; более продвинутые методы гарантируют логарифмическое или постоянное время выполнения для большинства или всех операций. Значения ). Звездочками помечены значения для маловероятных худших случаев.

В разделах 12.5-12.9 мы рассмотрим деревья бинарного поиска, которые обеспечивают время поиска и вставки, пропорциональное будут рассмотрены красно-черные деревья и рандомизированные деревья бинарного поиска, которые, соответственно, гарантируют логарифмическую производительность либо существенно увеличивают ее вероятность. В мы познакомимся с хешированием, которое обеспечивает поиск и вставку за постоянное время в среднем, но не позволяет эффективно выполнять операцию сортировать и некоторые другие операции. В будут изучаться методы поразрядного поиска, аналогичные методам поразрядной сортировки из ; в исследуются методы, применимые к файлам на внешних носителях.

Упражнения

12.16. Добавьте операцию удалить в реализацию таблицы символов на основе упорядоченного массива (программа 12.5).

12.17. Для таблиц символов на основе списка (программа 12.6) и массива (программа 12.5) реализуйте функции searchinsert. Они должны искать в таблице символов элемент с ключом, равным ключу заданного элемента, и при неудачном поиске вставить этот элемент.

12.18. Реализуйте операцию выбрать для реализации таблицы символов на основе списка (программа 12.6).

12.19. Приведите количество сравнений, необходимых для помещения ключей E A S Y Q U E S T I O N в первоначально пустую таблицу с использованием АТД, реализованных с помощью одного из четырех элементарных подходов: упорядоченный или неупорядоченный массив или список. Пусть для каждого ключа выполняется поиск, и в случае неудачи выполняется вставка, как в упражнении 12.17.

12.20. Для интерфейса таблицы символов из программы 12.2 реализуйте операции создать, найти и вставить, используя для представления таблицы символов неупорядоченный массив. Характеристики производительности программы должны соответствовать таблица 12.1.

12.21. Для интерфейса таблицы символов из программы 12.2 реализуйте операции создать, найти и вставить, используя для представления таблицы символов упорядоченный связный список. Характеристики производительности программы должны соответствовать таблица 12.1.

12.22. Измените реализацию таблицы символов на основе списка (программа 12.6) на двусвязный список, чтобы она поддерживала клиентские дескрипторы элементов (см. упражнение 12.7); добавьте деструктор, конструктор копирования и перегруженную операцию присваивания (см. упражнение 12.6); добавьте операции удалить и объединить; и напишите программу-драйвер, тестирующую полученные интерфейс и реализацию АТД первого класса таблицы символов.

12.23. Напишите программу-драйвер измерения производительности, которая использует функцию insert для заполнения таблицы символов, а затем функции select и remove для ее опустошения; эти операции должны многократно повторяться для случайных последовательностей ключей различной длины, от малой до большой. Программа должна замерять время каждого выполнения и выводить средние значения в виде текста или графика.

12.24. Напишите программу-драйвер проверки производительности, которая использует функцию insert для заполнения таблицы символов, а затем функцию search (в среднем 10 раз успешное выполнение и примерно столько же - неудачное); эти операции должны многократно повторяться для случайных последовательностей ключей различной длины, от малой до большой. Программа должна замерять время каждого выполнения и выводить средние значения в виде текста или графика.

12.25. Напишите программу-драйвер, использующую функции из интерфейса таблицы символов программы 12.2 для трудных или вырожденных случаев, которые могут возникнуть в реальных приложениях. Простые примеры: уже упорядоченные файлы, файлы в обратном порядке, файлы с одинаковыми ключами и файлы, состоящие только из двух различных значений.

12.26. Какую реализацию таблицы символов лучше использовать для приложения, в котором в произвольном порядке выполняется 10² операций вставить, 10³ операций найти и 10⁴ операций выбрать? Обоснуйте свой ответ.

12.27.( В действительности это упражнение состоит из пяти упражнений). Выполните упражнение 12.26 для пяти других вариантов сочетания операций и частоты их использования.

12.28. Алгоритм самоорганизующегося поиска - это алгоритм, который изменяет порядок элементов так, чтобы часто запрашиваемые элементы встречались в начале поиска. Измените реализацию операции найти для упражнения 12.20 так, чтобы при каждом успешном поиске она помещала найденный элемент в начало списка, сдвигая на одну позицию вправо все элементы от начала списка до освободившейся позиции. Эта процедура называется эвристикой перемещения вперед (move-to-front).

12.29. Приведите порядок ключей после того, как элементы с ключами E A S Y Q U E S T I O N помещаются в первоначально пустую таблицу с помощью операции найти и последующей вставить в случае неудачного поиска, с использованием эвристики самоорганизующегося поиска перемещением вперед (см. упражнение 12.28).

12.30. Напишите программу-драйвер для методов самоорганизующегося поиска, в которой таблица символов заполняется N ключами с помощью функции insert, а затем выполняется 10N успешных поисков в соответствии с известным распределением вероятности.

12.31. Воспользуйтесь решением упражнения 12.30 для сравнения времен выполнения реализации из упражнения 12.20 и времени выполнения реализации из упражнения 12.28 для N = 10, 100 и 1000, используя распределение вероятности, при котором операция найти выполняется для i-го наибольшего ключа с вероятностью 1/2i при $$${1}\leq{i}\leq{N}$$$.

12.32. Выполните упражнение 12.31 для распределения вероятности, при котором операция найти выполняется для i-го наибольшего ключа с вероятностью HN/i при $$${1}\leq{i}\leq{N}$$$. Это распределение называется законом Зипфа.

12.33. Сравните эвристику перемещения вперед с оптимальной организацией для распределений из упражнений 12.31 и 12.32 - а именно с хранением ключей в порядке возрастания (в порядке уменьшения ожидаемой частоты обращения к ним). То есть в упражнении 12.31 вместо решения из упражнения 12.20 воспользуйтесь программой 12.5.

Бинарный поиск

В реализации последовательного поиска в массиве большого количества элементов общее время поиска можно существенно сократить, используя процедуру поиска, основанную на стандартном принципе " разделяй и властвуй " (см. ): делим множество элементов на две части, определяем, к какой из двух частей принадлежит искомый ключ, и затем продолжаем поиск в этой части. Разумный способ разделения множества элементов на части состоит в поддержании упорядоченности элементов и использовании индексов в отсортированном массиве для определения той части массива, с которой нужно продолжать работать. Такая технология поиска называется бинарным поиском (binary search). Программа 12.7 представляет собой рекурсивную реализацию этой фундаментальной стратегии. В программе 2.2 показана нерекурсивная реализация, в которой стек не нужен, поскольку рекурсивная функция в программе 12.7 завершается рекурсивным вызовом.

На рис 12.1 показаны подфайлы, проверяемые в ходе бинарного поиска в небольшой таблице; на рис 12.2 приведен больший пример. Каждая итерация отбрасывает чуть больше половины таблицы, поэтому количество требуемых итераций мало.

Для нахождения искомого ключа L в этом файле с помощью бинарного поиска достаточно только трех итераций. В первом вызове алгоритм сравнивает L с ключом в середине файла - G. Поскольку L больше этого ключа, в следующей итерации используется правая половина файла. Затем, поскольку L меньше M, находящегося в середине правой половины, в ходе третьей итерации рассматривается подфайл, состоящий из трех элементов - H, I и L. После выполнения еще одной итерации размер подфайла становится равным 1, и алгоритм находит ключ L.

Для нахождения записи в файле из 200 элементов бинарный поиск требует только семь итераций. Размеры подфайлов описываются последовательностью 200, 99, 49, 24, 11, 5, 2, 1; то есть каждая из исследуемых частей несколько меньше половины предыдущей.

Программа 12.7. Бинарный поиск (в таблице символов на основе массива)

Данная реализация функции search использует процедуру рекурсивного бинарного поиска. Для определения, присутствует ли заданный ключ v в отсортированном массиве, этот ключ сначала сравнивается с элементом в средней позиции. Если v меньше, он должен находиться в первой половине массива, а если больше - то во второй.

Массив должен быть отсортирован. Этой функцией можно заменить функцию search в программе 12.5, которая обеспечивает динамическое упорядочение во время вставки. Либо можно добавить конструктор таблицы символов, использующий стандартную процедуру сортировки, который принимает массив в качестве аргумента, а затем строит таблицу символов из элементов входного массива и готовит ее к поиску с помощью одной из стандартных подпрограмм сортировки.

        private:
Item searchR(int l, int r, Key v)
  { if (l > r) return nullItem;
    int m = (l+r)/2;
    if (v == st[m].key()) return st[m];
    if (l == r) return nullItem;
    if (v < st[m].key())
      return searchR(l, m-1, v);
    else
    return searchR(m+1, r, v);
  }
        public:
Item search(Key v)
  { return searchR(0, N-1, v); }
      

Поддержание таблицы в отсортированном виде, как при сортировке вставками, приводит к квадратичной зависимости времени выполнения от количества операций вставить, но эти затраты можно считать приемлемыми или даже пренебрежимыми при очень большом количестве операций найти. В типичной ситуации, когда все элементы (или большая их часть) доступны до начала поиска, можно создать таблицу с помощью конструктора, который принимает в качестве параметра массив и во время инициализации использует один из стандартных методов сортировки, описанных в лекциях 6-10. После этого обновления таблицы могут выполняться различными способами. Например, можно поддерживать упорядоченность во время вставок, как в программе 12.5 (см. также упражнение 12.21), либо накопить их отдельно, выполнить сортировку и слить с существующей таблицей (как описано в упражнении 8.1). Всякое обновление может быть связано со вставкой элемента, ключ которого меньше ключа любого из элементов таблицы, и тогда для освобождения места может потребоваться сдвиг всех элементов.

Эти потенциально высокие затраты на обновление таблицы - наибольший недостаток использования бинарного поиска. С другой стороны, существует огромное число приложений, в которых достаточно заранее отсортировать статическую таблицу, и в этом случае, благодаря быстрому доступу, обеспечиваемому такими реализациями, как программа 12.7, бинарный поиск очень удобен.

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

Если в таблице могут быть повторяющиеся ключи, бинарный поиск можно расширить, включив операции для подсчета количества элементов с данным ключом или возврата их в виде группы. Несколько элементов, ключи которых совпадают с искомым, образуют в таблице непрерывный блок (поскольку таблица упорядочена), и в программе 12.7 успешный поиск завершится где-то внутри этого блока. Если приложению требуется доступ ко всем таким элементам, в программу можно добавить код для выполнения просмотра в обоих направлениях от точки завершения поиска и возврата двух индексов, ограничивающих элементы с ключами, равными искомому. В этом случае время выполнения поиска пропорционально lgN плюс количество найденных элементов. Аналогичный подход используется для решения более общей задачи поиска в диапазоне, которая состоит в нахождении всех элементов, ключи которых попадают в указанный интервал. Мы рассмотрим подобные расширения базового набора операций с таблицами символов в части 6.

Последовательность сравнений, выполняемых алгоритмом бинарного поиска, предопределена: конкретная используемая последовательность зависит от значения искомого ключа и значения N. Ее можно описать в виде структуры бинарного дерева, подобной приведенной на , используемое для описания размеров под-файлов во время сортировки слиянием ( рис 8.3). Но в бинарном поиске используется один путь в дереве, тогда как при сортировке слиянием - все пути. Это дерево является статическим и неявным; в разделе 12.5 будут рассмотрены алгоритмы, в которых для выполнения поиска используется динамическая, явно построенная структура бинарного дерева.

На этих диаграммах в виде деревьев " разделяй и властвуй " показана последовательность индексов для сравнений при бинарном поиске. Эти последовательности зависят только от размера исходного файла, но не от значений ключей в файле. Такие деревья несколько отличаются от деревьев, соответствующих сортировке слиянием и аналогичным алгоритмам ( рис 5.6 и 8.3), поскольку элемент, находящийся в корне, в поддеревья не включается.

На верхней диаграмме показан поиск в файле из 15 элементов, проиндексированных от 0 до 14. Анализируется средний элемент (с индексом 7), затем (рекурсивно) левое поддерево, если искомый элемент меньше его, или правое поддерево, если искомый элемент больше корня. Каждый поиск соответствует пути от корня до низа дерева: например, поиск элемента, значение которого находится между 10 и 11, проходит по пути 7, 11, 9 и 10. Для файлов, размер которых не равен степени 2 минус 1, структура не настолько регулярна - пример одной из них (для 12 элементов) приведен на нижней диаграмме.

Одно из возможных усовершенствований бинарного поиска - более точное предположение о положении ключа поиска в текущем интервале (вместо тупого сравнения его на каждом шаге со средним элементом). Эта тактика имитирует способ поиска имени в телефонном справочнике или слова в словаре: если нужная запись начинается с буквы, находящейся в начале алфавита, мы открываем книгу ближе к началу, а если она начинается с буквы из конца алфавита, поиск выполняется в конце книги. Для реализации данного метода, называемого интерполяционным поиском (interpolation search), нужно заменить в программе 12.7 оператор

m = (l+r)/2
      

на оператор

m = l+(v-[l].key())*(r-l)/(a[r].key()-a[l].key());
      

Для обоснования этого изменения отметим, что выражение (l + r) / 2 равнозначно выражению $$$l + \frac{1/2}(r - l)$$$: мы вычисляем середину интервала, добавляя к левой границе половину размера интервала. Использование интерполяционного поиска сводится к замене в этой формуле коэффициента $$$\frac{1/2}$$$ оценкой положения ключа - а именно $$$(v - k_{l}) / (k_{r}-k_{l} )$$$, где k_l и k_r соответственно означают a[l].key() и a[r].key(). При этом предполагается, что значения ключей являются числовыми и равномерно распределенными.

Можно показать, что при интерполяционном поиске в файлах со случайными ключами для каждого поиска (успешного или неудачного) используется менее lg lg N + 1 сравнений. Доказательство этого утверждения выходит далеко за рамки этой книги. Эта функция растет очень медленно, и на практике ее можно считать постоянной: если N равно 1 миллиарду, то lg lg N < 5. Таким образом, любой элемент можно найти, выполнив лишь несколько обращений (в среднем) - это существенное достижение по сравнению с бинарным поиском. Для ключей, которые распределены не вполне случайно, производительность интерполяционного поиска еще выше. А его граничным случаем является метод распределяющего поиска, описанный в разделе 12.2.

Однако интерполяционный поиск в значительной степени основывается на предположении, что ключи распределены во всем интервале более или менее равномерно - в противном случае, что обычно и имеет место на практике, метод окажется гораздо менее эффективным. Кроме того, для его реализации требуются дополнительные вычисления. Для небольших значений N затраты на обычный бинарный поиск (lg N) достаточно близки к затратам интерполяционного поиска (lg lg N), и поэтому интерполяцию вряд ли стоит использовать. Однако интерполяционный поиск определенно заслуживает внимания при работе с большими файлами, в приложениях, в которых сравнения очень дорогостоящи, и при использовании внешних методов, сопряженных с большими затратами на доступ.

Упражнения

12.34. Приведите нерекурсивную реализацию функции бинарного поиска (см. программу 12.7).

12.35. Нарисуйте деревья, соответствующие рис 12.3 для N = 17 и N = 24.

12.36. Найдите значения N, для которых бинарный поиск в таблице символов размером N становится в 10, 100 и 1000 раз быстрее последовательного поиска. Предскажите значения аналитически и проверьте их экспериментально.

12.37. Пусть вставки в динамическую таблицу символов размера N реализованы как в сортировке вставками, но для выполнения операции найти используется бинарный поиск. Предположим, что поиск выполняется в 1000 раз чаще, чем вставки. Определите в процентах долю времени, затрачиваемую на вставки, для N = 103, 104, 105 и 106 .

12.38. Разработайте реализацию таблицы символов, в которой используются бинарный поиск и " ленивая " вставка и поддерживаются операции создать, подсчитать, найти, вставить и сортировать, с помощью следующей стратегии. Храните большой отсортированный массив для основной таблицы символов и неупорядоченный массив для недавно вставленных элементов. При вызове функции search отсортируйте недавно вставленные элементы (если они есть), слейте их с основной таблицей, а затем воспользуйтесь бинарным поиском.

12.39. Добавьте " ленивое " удаление в реализацию из упражнения 12.38.

12.40. Ответьте на вопрос упражнения 12.37 для реализации из упражнения 12.38.

12.41. Реализуйте функцию, аналогичную бинарному поиску (программа 12.7), которая возвращает количество элементов в таблице символов с ключами, равными данному.

12.42. Напишите программу, которая при заданном значении N создает последовательность N макрокоманд вида compare(l, h), проиндексированных от 0 до N-1, где i-я макрокоманда в списке означает " сравнить ключ поиска со значением в таблице по индексу i; затем при равенстве сообщить, что ключ найден; если он меньше, выполнить l-ю инструкцию, и если больше - h-ю инструкцию " (индекс 0 зарезервируйте для индикации неудачного поиска). Любой поиск с помощью этой последовательности должен выполнять те же сравнения, что и бинарный поиск на этом наборе данных.

12.43. Разработайте расширение макрокоманд, созданных в упражнении 12.42, чтобы программа создавала машинный код, выполняющий бинарный поиск в таблице размером N при наименьшем возможном количестве машинных инструкций на одно сравнение.

12.44. Пусть a[i] == 10*i для значений i в интервале от 1 до N. Сколько позиций в таблице просматриваются интерполяционным поиском при неудачном поиске значения 2k - 1?

12.45. Найдите значения N, для которых интерполяционный поиск в таблице символов размером N выполняется в 1, 2 и 10 раз быстрее бинарного поиска, при условии, что ключи случайны. Предскажите эти значения аналитически и проверьте их экспериментально.

Деревья бинарного поиска

Для преодоления проблемы слишком высоких затрат на вставку в качестве основы для реализации таблицы символов мы будем использовать явную древовидную структуру. Такая структура данных позволяет разрабатывать алгоритмы с высокой средней производительностью операций найти, вставить, выбрать и сортировать. Этот метод рекомендуется для многих приложений и в компьютерных науках считается одним из наиболее фундаментальных.

Мы уже рассматривали деревья в , а сейчас просто вспомним терминологию. Определяющее свойство дерева (tree) заключается в том, что на каждый узел указывает только один другой узел, называемый родительским (parent). Определяющее свойство бинарного дерева (binary tree) - наличие у каждого узла обязательно двух ссылок, называемых левой и правой. Ссылки могут указывать на другие двоичные деревья или на внешние (external) узлы, которые не имеют ссылок. Узлы с двумя ссылками называются также внутренними (internal) узлами. Для выполнения поиска каждый внутренний узел содержит элемент со значением ключа; ссылки на внешние узлы называются пустыми (null) ссылками (то есть внешние узлы - это фиктивные узлы, которых на самом деле нет - прим. перев.). Процесс поиска зависит от результатов сравнения ключа поиска с ключами во внутренних узлах.

В программе 12.8 BST-деревья используются для реализации операций найти, вставить, создать и подсчитать. В ней узлы в BST-дереве определяются как содержащие элемент (с ключом) и левую и правую ссылки. Левая ссылка указывает на BST-дерево с элементами с меньшими (или равными) ключами, а правая - на BST-дерево с элементами с большими (или равными) ключами.

При наличии этой структуры рекурсивный алгоритм поиска ключа в BST-дереве становится очевидным: если дерево пусто, поиск неудачен; если ключ поиска равен ключу в корне, поиск успешен. Иначе выполняется (рекурсивно) поиск в соответствующем поддереве. В программе 12.8 этот алгоритм непосредственно реализуется функцией searchR. Начиная с корня дерева и искомого ключа, мы вызываем рекурсивную функцию, которая принимает дерево в качестве первого параметра и ключ в качестве второго. На каждом шаге гарантируется, что никакие части дерева, кроме текущего поддерева, не могут содержать элементы с искомым ключом. Подобно тому, как в бинарном поиске при каждой итерации размер интервала уменьшается чуть более чем в два раза, текущее поддерево в дереве бинарного поиска также меньше предшествующего (в идеальном случае приблизительно вдвое). Процедура завершается либо когда будет найден элемент с искомым ключом (успешный поиск), либо когда текущее поддерево станет пустым (неудачный поиск).

Пример процесса поиска показан на диаграмме в верхней части рис 12.4. Начиная сверху, процедура поиска в каждом узле приводит к рекурсивному вызову для одного из дочерних узлов этого узла; таким образом, поиск определяет некоторый путь по дереву. При успешном поиске путь завершается в узле, содержащем ключ, а в случае неудачи путь завершается во внешнем узле, как показано на средней диаграмме рис 12.4.

Программа 12.8. Таблица символов на основе дерева бинарного поиска

В этой реализации функции search и insert используют приватные рекурсивные функции searchR и insertR, которые непосредственно отражают рекурсивное определение BST-деревьев. Обратите внимание на передачу аргумента по ссылке в функции insertR (см. текст). Ссылка head указывает на корень дерева.

        template <class Item, class Key>
        class ST
{ private:
    struct node
      { Item item; node *l, *r;
        node(Item x)
{ item = x; l = 0; r = 0; }
      };
      typedef node *link;
      link head;
      Item nullItem;
      Item searchR(link h, Key v)
        { if (h == 0) return nullItem;
Key t = h->item.key();
if (v == t) return h->item;
if (v < t)
  return searchR(h->l, v);
else
  return searchR(h->r, v);
        }
        void insertR(link h, Item x)
{ if (h == 0) { h = new node(x); return; }
  if (x.key() < h->item.key())
    insertR(h->l, x);
  else
    insertR(h->r, x);
}
      public:
        ST(int maxN)
{ head = 0; }
        Item search(Key v)
{ return searchR(head, v); }
        void insert(Item x)
{ insertR(head, x); }
  };
      

Для представления внешних узлов в программе 12.8 используются нулевые ссылки, а приватный член данных head указывает на корень дерева. Для создания пустого BST-дерева в head заносится нулевое значение. Можно также использовать фиктивный узел в корне и еще один для представления всех внешних узлов, как описано в различных вариантах для связных списков в таблица 3.1 (см. упражнение 12.53).

Поиск в программе 12.8 выполняется так же просто, как и обычный бинарный поиск; существенная особенность BST-деревьев заключается в том, что операцию вставить реализовать так же легко, как и операцию найти. Логика рекурсивной функции insertR, вставляющей новый элемент в BST-дерево, аналогична логике функции searchR: если дерево пусто, в h заносится ссылка на новый узел, содержащий этот элемент; если ключ поиска меньше ключа в корне, то элемент вставляется в левое поддерево, иначе элемент вставляется в правое поддерево. То есть аргумент, передаваемый по ссылке, изменяется лишь в последнем рекурсивном вызове, при вставке нового элемента. В разделе 12.8 и в будут рассмотрены более сложные древовидные структуры, которые естественным образом представляются с помощью этой же рекурсивной схемы, но которые чаще изменяют значение аргумента.

В процессе успешного поиска H в этом дереве (вверху) мы перемещаемся от корня вправо (поскольку H больше, чем A), затем влево в правом поддереве (поскольку H меньше S) и т.д., продолжая перемещаться вниз по дереву, пока не встретится H. В процессе неудачного поиска M (в центре) мы перемещаемся от корня вправо (поскольку M больше A), затем влево в правом поддереве корня (поскольку M меньше S) и т.д., продолжая перемещаться вниз по дереву, пока не встретится внешняя ссылка (левая ссылка узла N) в нижней части диаграммы. Для вставки M после неудачного поиска достаточно просто заменить ссылку, прервавшую поиск, указателем на M (внизу).

На рис 12.5 и рис 12.6 продемонстрировано создание BST-дерева с помощью вставок последовательности ключей в первоначально пустое дерево. Новые узлы присоединяются к пустым ссылкам в нижней части дерева, а в остальном структура дерева никак не изменяется. Поскольку каждый узел имеет две ссылки, дерево растет скорее в ширину, нежели в высоту.

При использовании BST-деревьев реализовать операцию сортировать совсем нетрудно. Построение BST-дерева эквивалентно сортировке элементов, поскольку при соответствующем обходе BST-дерево представляет собой отсортированный файл. На приводимых рисунках ключи упорядочены, если просматривать их слева направо (не обращая внимания на их высоту и ссылки). Программа работает только со ссылками, но простой поперечный обход дерева, по определению, обеспечивает выполнение этой задачи, что и демонстрирует рекурсивная реализация функции showR в программе 12.9. Для отображения элементов BST-дерева в порядке возрастания их ключей нужно отобразить левое поддерево в порядке возрастания его ключей (рекурсивно), затем корень, и затем правое поддерево в порядке возрастания его ключей (рекурсивно).

Программа 12.9. Сортировка с помощью BST-дерева

При поперечном обходе BST-дерева элементы посещаются в порядке возрастания их ключей. В этой реализации для вывода элементов в порядке возрастания их ключей используется функция-член show.

private:
  void showR(link h, ostream os)
    { if (h == 0) return;
      showR(h->l, os);
      h->item.show(os);
      showR(h->r, os);
    }
public:
  void show(ostream os)
    { showR(head, os); }
      

Эта последовательность демонстрирует результат вставки ключей A S E R C H I N в первоначально пустое BST-дерево. Каждая вставка следует за неудачным поиском в нижней части дерева.

Эта последовательность демонстрирует вставку ключей .

При необходимости последовательного посещения всех элементов таблицы символов мы будем обращаться к обобщенной операции посетить для таблиц символов. Элементы BST-дерева можно посетить в порядке возрастания их ключей, заменив в только что приведенном описании слово " вывести " на " посетить " и, возможно, обеспечив передачу в качестве параметра функции, выполняющей посещение элемента (см. ).

Несомненно, представляет интерес и нерекурсивный подход к реализации поиска и вставки в BST-деревьях. При нерекусивной реализации процесс поиска состоит из цикла, в котором искомый ключ сравнивается с ключом в корне, затем выполняется перемещение влево, если ключ поиска меньше, и вправо - если он больше ключа в корне. Вставка состоит из индикации неудачного поиска (завершающегося на пустой ссылке) и последующей замены пустой ссылки указателем на новый узел. Этот процесс соответствует явной работе со ссылками вдоль пути вниз по дереву (см. рис 12.4). В частности, чтобы иметь возможность вставить новый узел в нижней части дерева, необходимо сохранять ссылку на родителя текущего узла, как в реализации в программе 12.10. Как обычно, рекурсивная и нерекурсивная версии, по существу, эквивалентны, но изучение обоих подходов способствует нашему лучшему пониманию алгоритмов и структур данных.

В функциях BST-дерева в программе 12.8 нет явных проверок на наличие элементов с повторяющимися ключами. При вставке нового узла, ключ которого равен какому-либо ключу, уже вставленному в дерево, узел помещается справа от присутствующего в дереве узла. Одним из побочных эффектов подобного соглашения является то, что узлы с равными ключами не являются соседями в дереве (см. , существуют и другие возможности обработки элементов с одинаковыми ключами.

Деревья бинарного поиска - аналог быстрой сортировки. Узел в корне дерева соответствует центральному элементу при быстрой сортировке (ключи слева от него не могут быть больше, а ключи справа не могут быть меньше его). В разделе 12.6 будет показано, как это наблюдение связано с анализом свойств деревьев.

Программа 12.10. Вставка в BST-дерево (нерекурсивная)

Вставка элемента в BST-дерево эквивалентна выполнению неудачного поиска этого элемента с последующим присоединением нового узла с этим элементом вместо пустой ссылки в месте завершения поиска. Присоединение нового узла требует запоминания родительского узла p текущего узла q при перемещении вниз по дереву. При достижении нижней части дерева p указывает на узел, ссылка которого должна указывать на новый вставленный узел.

void insert(Item x)
  { Key v = x.key();
    if (head == 0)
      { head = new node(x); return; }
    link p = head;
    for (link q = p; q != 0; p = q ? q : p)
      q = (v < q->item.key()) ? q->l : q->r;
    if (v < p->item.key())
      p->l = new node(x);
    else
    p->r = new node(x);
  }
      

Если BST-дерево содержит записи с одинаковыми ключами (вверху), они оказываются разбросанными по дереву - это видно на примере узлов A. Все одинаковые ключи размещаются вдоль пути поиска ключа от корня до внешнего узла, поэтому они легко доступны. Однако во избежание путаницы при использовании, наподобие " A, который под C, а не под E " , мы используем в примерах различные ключи (внизу).

Упражнения

12.46. Нарисуйте BST-дерево, образованное вставками элементов с ключами E A S Y Q U T I O N в первоначально пустое дерево.

12.47. Нарисуйте BST-дерево, образованное вставками элементов с ключами E A S Y Q U E S T I O N в первоначально пустое дерево.

12.48. Приведите количество сравнений, необходимых для помещения ключей E A S Y Q U E S T

I O N в первоначально пустую таблицу символов на основе BST-дерева. Считайте, что для каждого ключа выполняется операция найти, и затем, если поиск неудачен, операция вставить, как в программе 12.3.

12.49. Вставка ключей . Приведите десять других вариантов порядка этих ключей, которые дадут тот же результат.

12.50. Реализуйте функцию searchinsert для BST-деревьев (программа 12.8). Она должна искать в таблице символов элемент с таким же ключом, как и у данного элемента, а затем вставлять элемент, если такой ключ не найден.

12.51. Напишите функцию, которая возвращает количество элементов в BST-дереве с ключом, равным данному.

12.52. Предположим, что заранее известна частота обращения к ключам поиска в бинарном дереве.

Должны ли ключи вставляться в дерево в порядке возрастания или убывания ожидаемой частоты обращения к ним? Обоснуйте свой ответ.

12.53. Упростите код поиска и вставки в реализации BST-дерева в программе 12.8 с помощью двух фиктивных узлов: узла head, содержащего элемент с сигнальным ключом, который меньше всех остальных ключей, и правая ссылка которого указывает на корень дерева; и узла z, содержащего элемент с сигнальным ключом, который больше всех остальных ключей, и обе ссылки которого указывает на него самого, причем он представляет все внешние узлы (внешние узлы являются ссылками на z). (См. таблица 3.1).

12.54. Измените реализацию BST-дерева в программе 12.8 для хранения элементов с равными ключами в связных списках, размещенных в узлах дерева. Измените интерфейс, чтобы операция найти работала подобно операции сортировать (для всех элементов с искомым ключом).

12.55. В нерекурсивной процедуре вставки, приведенной в программе 12.10, для определения того, какую ссылку узла p необходимо заменить новым узлом, используется лишнее сравнение. Приведите реализацию, в которой это сравнение исключено.

Характеристики производительности деревьев бинарного поиска

Время выполнения алгоритмов, работающих с BST-деревьями, зависит от формы деревьев. В лучшем случае дерево может быть идеально сбалансированным и содержать приблизительно lgN узлов между корнем и каждым из внешних узлов, но в худшем случае путь поиска может содержать N узлов.

Можно также надеяться, что время поиска в среднем также будет логарифмическим, поскольку первый вставляемый элемент становится корнем дерева: если N ключей должны быть вставлены в произвольном порядке, то этот элемент должен поделить ключи пополам (в среднем), что дает логарифмическое время поиска (рассуждая аналогично по всем поддеревьям). Действительно, возможен случай, когда BST-дерево приводит в точности к тем же сравнениям, что и бинарный поиск (см. упражнение 12.58). Этот случай был бы наилучшим для данного алгоритма, гарантируя логарифмическое время выполнения для любого поиска. В действительно произвольной ситуации корнем может быть любой ключ, поэтому идеально сбалансированные деревья встречаются исключительно редко, и сохранять дерево полностью сбалансированным после каждой вставки нелегко. Однако полностью несбалансированные деревья для случайных ключей также встречаются редко, поэтому в среднем деревья достаточно хорошо сбалансированы. В этом разделе мы детализируем это наблюдение.

Оказывается, длина пути и высота бинарных деревьев, рассмотренные в , непосредственно связаны с затратами на поиск в BST-деревьях. Высота определяет затраты на поиск в худшем случае, длина внутреннего пути непосредственно связана с затратами при успешном поиске, а длина внешнего пути непосредственно связана с затратами при неудачном поиске.

В соответствии с леммой 12.6 следует ожидать, что затраты на поиск для BST-деревьев должны быть приблизительно на 39% выше затрат для бинарного поиска для случайных ключей. Но в соответствии с леммой 12.7 эти дополнительные затраты вполне окупаются, поскольку новый ключ может быть вставлен почти при тех же затратах - бинарному поиску подобная гибкость недоступна. На рис 12.8 показано BST-дерево, полученное из длинной последовательности случайных перестановок. Оно содержит несколько длинных и несколько коротких путей, но все-таки его можно считать хорошо сбалансированным: для выполнения любого поиска требуется менее 12 сравнений, а среднее количество сравнений, необходимых для успешного поиска произвольного элемента, равно 7,00, при 5,74 для бинарного поиска.

Леммы 12.6 и 12.7 определяют производительность в среднем при условии, что ключи расположены в произвольном порядке. Если это не так, производительность алгоритма может ухудшиться.

Таким образом, высокая производительность базовой реализации таблиц символов на основе BST-дерева достигается тогда, когда ключи достаточно случайны, и, значит, дерево не содержит длинных путей. К сожалению, на практике худший случай встречается не столь уж редко - он возникает при вставке прямо или обратно упорядоченных ключей в первоначально пустое дерево с применением стандартного алгоритма - т.е. при последовательности операций, которую мы вполне можем предпринять, не получив никакого явного предупреждения по этому поводу.

В этом BST-дереве, которое было построено вставками около 200 произвольных ключей в первоначально пустое дерево, ни один поиск не использует более 12 сравнений. Средняя стоимость успешного поиска приблизительно равна 10.

Если ключи вставляются в BST-дерево в порядке возрастания, дерево вырождается в форму, эквивалентную односвязному списку, что приводит к квадратичному времени создания дерева и к линейному времени поиска.

Множество других вариантов вставки ключей также приводят к вырождению BST-дерева. Однако дерево бинарного поиска, образованное произвольно упорядоченными ключами, скорее всего, окажется хорошо сбалансированным.

В главе 13 будут рассмотрены способы превращения этого худшего случая в крайне маловероятный, полного исключения худшего случая и превращения всех деревьев в деревья как для лучшего случая, где длины всех путей гарантированно логарифмические.

Ни одна из других рассмотренных реализаций таблиц символов не может использоваться для выполнения задачи вставки в таблицу очень большого количества произвольных ключей, а затем поиска каждого из них - время выполнения каждого из методов, описанных в разделах 12.2-12.4, для этой задачи квадратично. Более того, анализ показывает, что среднее расстояние до узла в бинарном дереве пропорционально логарифму количества узлов в дереве - как мы вскоре увидим, это позволяет эффективно выполнять вперемешку операции поиска, вставки и другие операции АТД таблицы символов.

Упражнения

12.56. Напишите рекурсивную программу, которая вычисляет максимальное количество сравнений, требуемых для любого поиска в данном BST-дереве (высоту дерева).

12.57. Напишите рекурсивную программу, которая вычисляет среднее количество сравнений, требуемых для успешного поиска в данном BST-дереве (длину внутреннего пути дерева, деленную на N).

12.58. Приведите такую последовательность вставок ключей E A S Y Q U E S T I O N в первоначально пустое BST-дерево, чтобы созданное при этом дерево было эквивалентно бинарному поиску - в том смысле, что последовательность сравнений, выполняемых при поиске любого ключа в BST-дереве, совпадали бы с последовательностью сравнений, выполняемых при бинарном поиске на том же множестве ключей.

12.59. Напишите программу, которая вставляет набор ключей в первоначально пустое BST-дерево так, чтобы созданное дерево было эквивалентно бинарному поиску, в смысле, описанном в упражнении 12.58.

12.60. Нарисуйте все различные по структуре BST-деревья, которые могут образоваться после вставки N ключей в первоначально пустое дерево, для $$$2 \leq N\leq 5$$$.

12.61. Для каждого из деревьев из упражнения 12.60 определите вероятность того, что оно получится в результате вставки N произвольных различных элементов в первоначально пустое дерево.

12.62. Сколько бинарных деревьев, состоящих из N узлов, имеют высоту N? Сколько существует различных способов вставки N различных ключей в первоначально пустое дерево, приводящих к образованию BST-дерева с высотой N ?

12.63. Докажите методом индукции, что разница между длинами внешнего и внутреннего путей в любом бинарном дереве составляет 2N (см. лемму 5.7).

12.64. Определите эмпирически среднее значение и среднеквадратичное отклонение количества сравнений при успешных и неудачных поисках в BST-дереве, созданном вставкой N случайных ключей в первоначально пустое дерево, для N = 103, 104, 105 и 106 .

12.65. Напишите программу, которая строит t BST-деревьев вставкой N случайных ключей в первоначально пустое дерево и вычисляет максимальную высоту дерева (максимальное количество сравнений, необходимых для неудачного поиска при вставке в любом из этих t деревьев), для N = 103, 104, 105 и 106 при t = 10, 100 и 1000.

Индексные реализации таблиц символов

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

Деревья бинарного поиска можно определить таким образом, чтобы индексы строились в точности так же, как при обеспечении косвенной сортировки в и для пирамидальных деревьев в : мы используем оболочку Index для определения элементов BST-дерева и обеспечим извлечение ключей из элементов, как обычно, через функцию-член key. А для ссылок можно задействовать параллельный массив, как это было сделано для связных списков в . Мы будем использовать три массива: для элементов, левых ссылок и правых ссылок. Ссылки являются (целочисленными) индексами массивов, и обращения вроде

x = x->l
      

во всем коде заменяются на обращения

x = l[x]
      

Этот подход устраняет затраты на динамическое распределение памяти для каждого узла - элементы занимают массив независимо от функции поиска, и для хранения ссылок дерева заранее выделены два целочисленных значения на каждый элемент. Память под ссылки используется не всегда, но она готова для использования подпрограммой поиска, не требуя дополнительного времени на выделение. Другая важная особенность этого подхода заключается в том, что здесь возможно добавление добавочных массивов (содержащих дополнительную связанную с каждым узлом информацию) без какого-либо изменения кода работы с деревом. Когда подпрограмма поиска возвращает индекс элемента, она предоставляет способ немедленного доступа ко всей информации, связанной с этим элементом - ведь этого индекса достаточно для доступа к соответствующему массиву.

Такой способ реализации BST-деревьев как средства упрощения поиска в больших массивах элементов иногда весьма полезен, поскольку исключает дополнительные затраты на копирование элементов во внутреннее представление АТД и излишние действия по их размещению и созданию операцией new. Использование массивов не годится, когда объем памяти играет первостепенную роль, а таблица символов увеличивается и уменьшается в значительных пределах. В особенности это актуально, если заранее трудно оценить максимальный размер таблицы символов. В таком случае неиспользуемые ссылки в массиве элементов могут привести к напрасному расходу памяти.

Важное применение концепции индексирования - поиск ключевых слов в строке текста (см. рис 12.11). Программа 12.11 является примером такого приложения. Она считывает текстовую строку из внешнего файла, а затем, считая, что каждая позиция в этой строке определяет строковый ключ, начинающийся с данной позиции и до конца строки, она вставляет все такие ключи в таблицу символов, используя указатели на строки. Подобное применение строковых ключей отличается от определения типа строкового элемента (например, как в упражнении 12.2), поскольку никакое выделение памяти не выполняется. Используемые ключи имеют произвольную длину, но мы работаем только с указателями на них и просматриваем лишь то количество символов, которое необходимо для определения, какая из двух строк должна следовать первой. Никакие две строки не совпадают (например, все они имеют различную длину), но если изменить операцию ==, чтобы считать строки равными, когда одна из них является префиксом второй, то можно воспользоваться простым вызовом search для таблицы символов, чтобы выяснить, присутствует ли данная строка в тексте.

Программа 12.11. Пример индексирования текстовой строки

В этой программе считается, что в файле Item.cxx определены представление данных char* для строковых ключей в элементах, перегруженная операция <, которая использует функцию strcmp, перегруженная операция ==, которая использует функцию strncmp, и оператор преобразования из Item в char* (см. текст). Главная программа считывает текстовую строку из указанного файла и использует таблицу символов для построения индекса из строк, начинающихся в каждой позиции текстовой строки. Затем она считывает из стандартного ввода запрашиваемые строки и выводит позицию, в которой они найдены в тексте (или выводит строку не найдено). При реализации таблицы символов на основе BST-дерева поиск выполняется быстро даже для очень больших строк.

#include <iostream.h>
#include <fstream.h>
#include "Item.cxx"
#include "ST.cxx"
static char text[maxN];
int main(int argc, char *argv[])
  { int N = 0; char t;
    ifstream corpus; corpus.open(*++argv);
    while (N < maxN  corpus.get(t)) text[N++] = t;
    text[N] = 0;
    ST<Item, Key> st(maxN);
    for (int i = 0; i < N; i++) st.insert(text[i]);
    char query[maxQ]; Item x, v(query);
    while (cin.getline(query, maxQ))
      if ((x = st.search(v.key())).null())
        cout << "не найдено: " << query << endl;
    else
    cout << x-text << ": " << query << endl;
  }
      

В этом примере индекса строки строковый ключ определен так, чтобы он начинался с каждого слова в тексте; затем строится BST-дерево с помощью обращения к ключам по их индексам в строке. В принципе, ключи имеют произвольную длину, но на практике обычно просматриваются только несколько начальных символов. Например, для определения того, встречается ли в этом тексте фраза never mind, она сравнивается с call... в корне (индекс 0), затем с me... в правом дочернем узле корня (индекс 5), затем с some... в правом дочернем узле этого узла (индекс 16), а затем в левом дочернем узле предпоследнего узла (индекс 31) обнаруживается и never mind.

Программа 12.11 последовательно считывает запросы из стандартного ввода, вызывает функцию search для определения присутствия запрашиваемых строк в тексте и выводит позицию первого совпадения с запросом. Если таблица символов реализована на основе BST-дерева, то в соответствии с леммой 12.6 можно ожидать, что для поиска потребуется порядка 2NlnN сравнений. Например, после построения индекса любую фразу в тексте, состоящем приблизительно из 1 миллиона символов, можно найти с помощью около 30 операций сравнения строк. Это приложение равносильно индексированию, поскольку указатели C-строк являются индексами массива символов: если x указывает на text[i], то разность двух указателей x-text равна i.

При построении индексов в реальных приложениях потребуется учесть и множество других моментов. Существует немало способов, использующих конкретные преимущества строковых ключей для ускорения работы алгоритмов. Более сложным методам поиска строк и создания индексов с дополнительными полезными возможностями в основном посвящена часть 5.

В таблица 12.2 сведены результаты экспериментальных исследований, подтверждающие приведенные аналитические рассуждения и демонстрирующие применение деревьев бинарного поиска для работы с динамическими таблицами символов со случайными ключами.

В этой таблице приведены относительные времена создания таблицы символов и затем поиска каждого ключа в таблице. Деревья бинарного поиска обеспечивают быстрые реализации поиска и вставки; при использовании всех других методов для выполнения одной из этих двух задач требуется квадратичное время. Обычно бинарный поиск выполняется несколько быстрее поиска в BST-дереве, но он неприменим к очень большим файлам, если только таблицу нельзя предварительно отсортировать. Стандартная реализация BST-дерева выделяет память для каждого узла дерева, а реализация с использованием индексов предварительно выделяет память для всего дерева (что ускоряет создание), и вместо указателей использует индексы массивов (что замедляет поиск).

Упражнения

12.66. Измените реализацию BST-дерева из программы 12.8, чтобы использовать индексированный массив элементов, а не выделенную память. Сравните производительность полученной программы с производительностью стандартной реализации, воспользовавшись драйвером из упражнения 12.23 или упражнения 12.24.

12.67. Измените реализацию BST-дерева из программы 12.8, чтобы она поддерживала АТД символьной таблицы с клиентскими дескрипторами элементов (см. упражнение 12.7), используя параллельные массивы. Сравните производительность полученной программы с производительностью стандартной реализации, воспользовавшись драйвером из упражнения 12.23 или упражнения 12.24.

12.68. Измените реализацию BST-дерева из программы 12.8 следующим образом: используйте массив элементов с ключами и массив ссылок (по одной для каждого элемента) в узлах дерева. Левая ссылка в BST-дереве соответствует перемещению в следующую позицию в массиве в узле дерева, а правая ссылка в BST-дереве соответствует перемещению в другой узел дерева.

12.69. Приведите пример текстовой строки, где количество строковых сравнений для этапа создания индекса в программе 12.11 квадратично зависит от длины строки.

12.70. Измените реализацию индексирования строки (программа 12.11), чтобы для построения индекса использовались только ключи, начинающиеся на границах слов (см. рис 12.11). (Для книги " Моби Дик " это изменение уменьшает размер индекса более чем в пять раз.)

12.71. Реализуйте версию программы 12.11, в которой используется бинарный поиск в массиве указателей на строки с помощью реализации из упражнения 12.38.

12.72. Сравните время выполнения вашей реализации из упражнения 12.71 с программой 12.11 при построении индекса для случайной текстовой строки из N символов, для N = 10³, 10⁴, 10⁵ и 10⁶, и при выполнении 1000 (неудачных) поисков для случайных ключей в каждом индексе.

Вставка в корень в деревьях бинарного поиска

В стандартной реализации BST-деревьев каждый вновь вставленный узел попадает куда-то в нижнюю часть дерева, заменяя некоторый внешний узел. Это не обязательное требование, а лишь следствие естественного алгоритма с использованием рекурсивных вставок. В этом разделе рассматривается другой метод вставки, при котором каждый новый элемент вставляется в корень, и поэтому недавно вставленные узлы находятся вблизи вершины дерева. Построенные таким образом деревья обладают рядом интересных свойств, но главная причина изучения этого метода в том, что он играет важную роль в двух усовершенствованных алгоритмах, которые будут рассмотрены в .

Предположим, что ключ вставляемого элемента больше ключа в корне. Тогда создание нового дерева можно начать с помещения нового элемента в новый корневой узел, со старым корнем в качестве левого поддерева и правым поддеревом старого корня в качестве правого поддерева. Однако правое поддерево может содержать и меньшие ключи, поэтому для завершения вставки потребуются дополнительные действия.

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

К счастью, существует простое рекурсивное решение этой проблемы, основанное на ротации (rotation) - фундаментальном преобразовании деревьев. По существу, ротация позволяет менять местами роль корня и одного из его потомков, сохраняя BST-упорядоченность ключей в узлах дерева. Ротация вправо затрагивает корень и его левый дочерний узел (см. рис 12.12). Эта ротация перемещает корень вправо, изменяя на обратное направление левой ссылки корня: перед ротацией она указывает от корня на левый дочерний узел, а после ротации - от старого левого потомка (нового корня) на старый корень (правый дочерний узел нового корня). Основная часть, которая обеспечивает работу ротации - копирование правой ссылки левого потомка, чтобы она стала левой ссылкой старого корня. Эта ссылка указывает на все узлы с ключами между двумя узлами, участвующими в ротации. После этого нужно изменить ссылку на старый корень так, чтобы она указывала на новый корень. Описание ротации влево аналогично вышеприведенному, только везде слово " правый " должно быть заменено на " левый " и наоборот (см. рис 12.13).

На этой диаграмме показан результат (внизу) ротации вправо в узле S BST-дерева, приведенного вверху. Узел, содержащий ключ S, перемещается в дереве вниз и становится правым дочерним узлом своего прежнего левого дочернего узла.

Для выполнения ротации мы получаем ссылку на новый корень E из левой ссылки узла S, копируем в левую ссылку S правую ссылку E, в правую ссылку E - указатель на S и заменяем ссылку из A на S указателем на E. Эффект ротации заключается в перемещении узла E и его левого поддерева на один уровень вверх, а узла S и его правого поддерева - на один уровень вниз. Остальная часть дерева остается неизменной.

На этой диаграмме показан результат (внизу) ротации вправо в узле A BST-дерева, приведенного вверху. Узел, содержащий ключ A, перемещается в дереве вниз и становится левым дочерним узлом своего прежнего правого дочернего узла.

Для выполнения ротации мы получаем ссылку на новый корень E из правой ссылки узла A, копируем в правую ссылку A левую ссылку E, в левую ссылку E - указатель на A и заменяем ссылку на A (верхняя ссылка дерева) указателем на E.

Ротация - это локальное изменение, затрагивающее только три ссылки и два узла; оно позволяет перемещать узлы по деревьям без изменения глобальных свойств упорядоченности, которые и делают BST-дерево полезной для поиска структурой (см. программу 12.12). Ротации применяются для перемещения конкретных узлов по дереву и предотвращения разба-лансировки деревьев. В разделе 12.9 с помощью ротаций будут реализованы операции удалить, объединить и другие операции АТД; в они будут применяться для построения деревьев, дающих почти оптимальную производительность.

Программа 12.12. Ротации в BST-деревьях

Эти две симметричные процедуры выполняют операцию ротация в BST-дереве. Ротация вправо делает старый корень правым поддеревом нового корня (старого левого поддерева корня); ротация влево делает старый корень левым поддеревом нового корня (старого правого поддерева корня). Для реализаций, где в узлах содержится поле счетчика (например, для поддержки операции выбрать в ), необходимо также пересчитывать значений этих полей для участвующих в ротации узлах (см. упражнение 12.75).

void rotR(link h)
  { link x = h->l; h->l = x->r; x->r = h; h = x; }
void rotL(link h)
  { link x = h->r; h->r = x->l; x->l = h; h = x; }
      

Операции ротации обеспечивают простую рекурсивную реализацию вставки в корень: необходимо рекурсивно вставить новый элемент в соответствующее поддерево (оставив его, по завершении рекурсивной операции, в корне этого дерева), а затем выполнить ротацию, чтобы сделать этот элемент корнем основного дерева. На рис 12.14 приведен пример, а программа 12.13 является непосредственной реализацией данного метода.

Здесь показан результат вставки узла G в BST-дерево, приведенное на верхнем рисунке, с (рекурсивной) ротацией после вставки, которая перемещает вставленный узел G в корень. Этот процесс эквивалентен вставке G с последующим выполнением последовательности ротаций для перемещения его в корень.

Программа 12.13. Вставка в корень BST-дерева

С помощью функций ротации из программы 12.12 реализация рекурсивной функции, которая вставляет новый узел в корень BST-дерева, очевидна: необходимо вставить новый элемент в корень соответствующего поддерева, а затем выполнить соответствующую ротацию, чтобы перенести его в корень основного дерева.

        private:
void insertT(link h, Item x)
  { if (h == 0) { h = new node(x); return; }
    if (x.key() < h->item.key())
      { insertT(h->l, x); rotR(h); }
    else
      { insertT(h->r, x); rotL(h); }
  }
        public:
void insert(Item item)
  { insertT(head, item); }
      

Эта программа представляет собой убедительный пример больших возможностей рекурсии: любой читатель, которого это не убеждает, может попытаться выполнить упражнение 12.76.

На рис 12.15 и рис 12.16показано создание BST-дерева вставкой последовательности ключей в первоначально пустое дерево с использованием метода вставки в корень. Если последовательность ключей случайна, созданное таким образом BST-дерево обладает в точности теми же стохастическими свойствами, что и BST-дерево, созданное стандартным методом. Например, леммы 12.6 и 12.7 справедливы и для BST-деревьев, построенных вставками в корень. На практике преимущество метода вставки в корень состоит в том, что недавно вставленные ключи располагаются вблизи вершины. Следовательно, затраты на удачный поиск недавно вставленных ключей будут, скорее всего, ниже, чем при стандартном методе. Это важное свойство, поскольку многим приложениям присуща именно такая динамическая смесь операций найти и вставить. Таблица символов может содержать довольно большое количество элементов, но значительная часть поисков может относиться к самым последним вставленным элементам. Например, в системе обработки коммерческих транзакций активные транзакции могут оставаться вблизи вершины и обрабатываться быстро без обращения к старым потерянным транзакциям. Метод вставки в корень автоматически придает структуре данных это и аналогичные свойства.

Эта последовательность демонстрирует результат вставки ключей A S E R C H I в корень первоначально пустого BST-дерева. После вставки в корень каждого нового узла изменяются ссылки, расположенные вдоль его пути поиска, чтобы получилось правильное BST-дерево.

Эта последовательность демонстрирует вставку ключей .

Если изменить еще и функцию найти, чтобы при успешном поиске она помещала найденный узел в корень, то получится метод самоорганизующегося поиска (см. упражнение 12.28), который сдвигает часто посещаемые узлы к вершине дерева. В главе 13 будет показано систематическое применение этой идеи при реализации таблицы символов, обладающей гарантированно быстрой производительностью.

Как и для ряда других методов, упомянутых в этой главе, для реальных приложений трудно точно сравнить производительность метода вставки в корень со стандартным методом вставки, поскольку производительность настолько зависит от смеси различных операций с таблицей символов, что ее трудно проанализировать аналитически. Невозможность проанализировать алгоритм не обязательно должна удерживать от использования вставки в корень, когда известно, что основная масса поисков будет связана с недавно вставленными данными, однако мы всегда пытаемся найти гарантированные показатели производительности. Методы построения BST-деревьев, которые могут предоставить такие гарантии, являются основной темой .

Упражнения

12.73. Нарисуйте BST-дерево, образованное вставками элементов с ключами E A S Y Q U E S T I O N в корень первоначально пустого дерева.

12.74. Приведите последовательность из 10 ключей (используя буквы от A до J), которая требует максимального количества сравнений при создании дерева вставками в корень первоначально пустого дерева. Укажите количество используемых сравнений.

12.75. Добавьте в программу 12.12 код, необходимый для корректного изменения полей счетчиков, которые должны изменяться после ротации.

12.76. Разработайте нерекурсивную реализацию вставки в корень BST-дерева (см. программу 12.13).

12.77. Эмпирически определите среднее значение и среднеквадратичное отклонение количества сравнений, выполняемых при успешных и неудачных поисках в BST-дереве, которое построено вставками N случайных ключей в первоначально пустое дерево. После построения в этом дереве выполняется последовательность N произвольных поисков N/10 самых последних вставленных ключей для N = 103, 104, 105 и 106 . Проведите эксперименты и для стандартного метода вставки, и для метода вставки в корень, а затем сравните полученные результаты.

Реализации других функций АТД с помощью BST -ДЕРЕВА

Рекурсивные реализации из раздела 12.5 для основных операций найти, вставить и сортировать, использующие структуру бинарных деревьев, достаточно просты. В этом разделе мы рассмотрим реализации функций выбрать, объединить и удалить. Одна из них, выбрать, также допускает естественную рекурсивную реализацию, однако для других это может оказаться трудной задачей, приводящей к потере производительности. Операцию выбрать важно рассмотреть потому, что возможность эффективной поддержки операций выбрать и сортировать - одна из причин, по которой для многих приложений BST-деревья оказываются удобнее других структур. Хотя некоторые программисты стараются не использовать BST-деревья, чтобы не возиться с операцией удалить. В этом разделе рассматривается компактная реализация всех этих операций, использующая технику ротации к корню из раздела 12.8.

Обычно эти операции связаны с перемещением вниз по дереву; поэтому для случайных BST-деревьев можно ожидать, что затраты будут логарифмическими. Однако нельзя гарантировать, что BST-деревья останутся случайными после выполнения над ними многочисленных операций. В конце этого раздела мы еще вернемся к данному вопросу.

Для реализации операции выбрать можно использовать рекурсивную процедуру, аналогичную методу выборки на основе быстрой сортировки, описанному в . Для отыскания в BST-дереве элемента с k-ым наименьшим ключом проверяется количество узлов в левом поддереве. Если там к узлов, возвращается корневой элемент. Иначе, если левое поддерево содержит более к узлов, в нем (рекурсивно) отыскивается к-й наименьший узел. Если неверно ни одно из этих условий, то левое поддерево содержит t элементов при t < k, и k-й наименьший элемент в BST-дереве является (k - t - 1)- ым наименьшим элементом в правом поддереве. Программа 12.14 является непосредственной реализацией этого метода. Как обычно, поскольку каждое выполнение функции завершается максимум одним рекурсивным вызовом, очевидна и нерекурсивная версия (см. упражнение 12.78).

Программа 12.14. Выборка с помощью BST-дерева

В этой процедуре предполагается, что каждый узел дерева содержит размер своего поддерева. Сравните эту программу с выборкой с помощью быстрой сортировки в массиве (программа 9.6).

private:
  Item selectR(link h, int k)
  { if (h == 0) return nullItem;
    int t = (h->l == 0) ? 0: h->l->N;
    if (t > k) return selectR(h->l, k);
    if (t < k) return selectR(h->r, k-t-1);
    return h->item;
  }
public:
  Item select(int k)
  { return selectR(head, k); }
      

Реализация операции выбрать - основная алгоритмическая причина включения поля размера поддерева во все узлы BST-дерева. С помощью этого поля можно также обеспечить тривиальную " энергичную " реализацию операции подсчитать (возврат значения поля счетчика в корневом узле); в будет продемонстрировано еще одно применение. Недостатки присутствия поля счетчика заключаются в использовании дополнительной памяти для каждого узла и необходимости обновления поля каждой функцией, изменяющей дерево. Использование поля размера поддерева может не окупаться в некоторых приложениях, в которых основным операциями являются вставить и найти, но эта плата может оказаться незначительной, если в динамической таблице символов важна поддержка операции выбрать.

Эту реализацию операции выбрать можно преобразовать в операцию разбить (на части - partition), которая реорганизует дерево для помещения к-го наименьшего элемента в корень, используя точно такую же рекурсивную технику, которая использовалась для вставки в корень в разделе 12.8: если мы (рекурсивно) помещаем требуемый узел в корень одного из поддеревьев, его затем с помощью единственной ротации можно сделать корнем всего дерева. Программа 12.15 содержит реализацию этого метода. Подобно ротациям, разбиение не является операцией АТД, поскольку эта функция преобразует конкретное представление таблицы символов и должна быть прозрачной для клиентов. Скорее, это вспомогательная процедура, которую можно использовать для реализации операций АТД либо для повышения их эффективности. На рис 12.17 приведен пример, показывающий, аналогично трис 12.14, что этот процесс эквивалентен спуску по пути от корня до требуемого узла дерева, а затем подъему обратно с выполнением ротаций для перемещения этого узла в корень.

Программа 12.15. Разбиение BST-дерева

Добавление ротаций после рекурсивных вызовов преобразует функцию выборки из программы 12.14 в функцию, которая помещает к-й наименьший узел BST-дерева в его корень.

void partR(link h, int k)
  { int t = (h->l == 0) ? 0 : h->l->N;
    if (t > k)
      { partR(h->l, k); rotR(h); }
    if (t < k)
      { partR(h->r, k-t-1); rotL(h); }
  }
      

Здесь показан результат (внизу) разбиения BST-дерева (вверху) по медианному ключу; при этом выполняется (рекурсивно) ротация - точно так же, как и при вставке в корень.

Чтобы удалить из BST-дерева узел с заданным ключом, вначале необходимо проверить, находится ли он в одном из поддеревьев. Если да, мы заменяем это поддерево результатом (рекурсивного) удаления из него данного узла. Если удаляемый узел находится в корне, дерево заменяется результатом объединения двух поддеревьев в одно. Для выполнения такого объединения существует несколько возможностей. Один из возможных подходов проиллюстрирован на рис 12.18, а реализация представлена в программе 12.16.

Здесь показан результат (внизу) удаления корня из BST-дерева (вверху). Вначале после удаления корневого узла остаются два поддерева (второй сверху рисунок). Затем мы разбиваем правое поддерево для помещения его наименьшего элемента в корень (третий сверху рисунок) - при этом левая ссылка указывает на пустое поддерево.

И, наконец, мы заменяем эту ссылку указателем на левое поддерево исходного дерева (внизу).

Программа 12.16. Удаление узла с заданным ключом из BST-дерева

В данной реализации операции удалить выполняется удаление из BST-дерева первого найденного узла с ключом v. Проходя сверху вниз, программа выполняет рекурсивные вызовы для соответствующего поддерева до тех пор, пока удаляемый узел не окажется в корне. Потом этот узел заменяется результатом объединения двух его поддеревьев: наименьший узел в правом поддереве становится корнем, а в его левую ссылку заносится указатель на левое поддерево.

private:
  link joinLR(link a, link b)
  { if (b == 0) return a;
    partR(b, 0); b->l = a;
    return b;
  }
void removeR(link h, Key v)
  { if (h == 0) return;
    Key w = h->item.key();
    if (v < w) removeR(h->l, v);
    if (w < v) removeR(h->r, v);
    if (v == w)
      { link t = h; h = joinLR(h->l, h->r);
      delete t; }
  }
public:
  void remove(Item x)
    { removeR(head, x.key()); }
      

Если все ключи одного BST-дерева меньше ключей второго, то для объединения этих деревьев ко второму дереву применяется операция разбить, чтобы переместить наименьший элемент этого дерева в корень. После этого левое поддерево корня второго дерева должно быть пустым (иначе в нем располагался бы элемент, меньший элемента в корне), и задачу можно завершить, заменив эту ссылку указателем на первое дерево. На рис 12.19 показан пример дерева и последовательность удалений, иллюстрирующих некоторые из возможных ситуаций.

Здесь показан результат удаления узлов с ключами L, H и E из BST-дерева, показанного на верхнем рисунке. Вначале L просто удаляется, поскольку он расположен внизу. Затем H заменяется его правым дочерним узлом I, поскольку левый дочерний узел I пуст. И, наконец, E заменяется своим потомком G.

Этот подход асимметричен и в одном отношении произволен: почему в качестве корня нового дерева используется наименьший ключ второго дерева, а не наибольший ключ первого дерева? Другими словами, почему удаляемый узел заменяется следующим узлом в поперечном обходе дерева, а не предыдущим? Возможны и другие подходы. Например, если у удаляемого узла левая ссылка пуста, почему бы просто не сделать новым корнем его правый дочерний узел, а не узел с наименьшим ключом в правом поддереве? Было предложено много аналогичных модификаций базовой процедуры удаления. К сожалению, всем им присущ один и тот же недостаток: после удаления дерево перестает быть случайным, даже если оно было случайным до этого. Кроме того, было показано, что если дерево подвергается большому количеству случайных пар операций удаления-вставки, то программа 12.16 склонна оставлять дерево слегка несбалансированным (средняя высота пропорциональна $$$\sqrt{N}$$$ ) (см. упражнение 12.84).

Эти различия могут быть не заметны в реальных приложениях, если только N не очень велико. Тем не менее, такое сочетание не очень элегантного алгоритма с неудовлетворительными характеристиками производительности не радует. В будут рассмотрены два различных способа исправления этой ситуации.

Для алгоритмов поиска типична ситуация, когда для удаления требуются более сложные реализации, чем для поиска. Значения ключей играют важную роль в формировании структуры, поэтому удаление ключа может быть сопряжено со сложными исправлениями. Одна из возможных альтернатив - использование " ленивой " стратегии удаления, оставляющей удаленные узлы в структуре данных, но помечающей их как " удаленные " , которые будут игнорироваться при поиске.

В реализации поиска в программе 12.8 эту стратегию можно реализовать, не выполняя проверку на равенство для таких узлов. Необходимо обеспечить, чтобы большое количество помеченных узлов не привело к непомерным затратам времени или памяти, хотя если удаления выполняются не слишком часто, эти дополнительные затраты могут не играть особой роли. Помеченные узлы можно использовать в будущих вставках, когда это удобно (например, это легко сделать для узлов в нижней части дерева). Или же можно периодически перестраивать всю структуру данных, отбрасывая помеченные узлы.

Подобные соображения применимы не только к таблицам символов, но и к любой структуре данных, сопряженной со вставками и удалениями.

В завершение этой главы мы рассмотрим реализацию операции удалить с использованием дескрипторов и операции объединить для реализаций АТД таблицы символов, использующих BST-деревья. Мы предполагаем, что дескрипторы - это ссылки, и опускаем дальнейшие рассуждения на тему оформления, чтобы сосредоточиться на этих двух базовых алгоритмах.

Основная сложность в реализации функции для удаления узла с данным дескриптором (ссылкой) та же, что и для связных списков: необходимо изменить указатель в структуре, который указывает на удаляемый узел. Существует, по меньшей мере, четыре способа решения этой проблемы. Во-первых, в каждый узел дерева можно добавить третью ссылку, указывающую на его родителя. Недостаток этого метода заключается в том, что, как уже неоднократно отмечалось, поддерживать дополнительные ссылки весьма обременительно. Во-вторых, можно использовать ключ элемента для выполнения поиска в дереве, прекращая его после того, как найден соответствующий указатель. Недостаток этого подхода в том, что обычно узел находится в нижней части дерева, и, следовательно, этот подход требует лишнего прохода по дереву. В-третьих, можно воспользоваться ссылкой или указателем на указатель узла в качестве дескриптора. Этот метод работает в языках C++ и C, но не годится для многих других языков. В-четвертых, можно применить " ленивый " подход, как-то помечая удаленные узлы и периодически перестраивая структуру данных, как описано выше.

Последняя операция для АТД таблиц символов, которую мы рассмотрим - операция объединить. В реализации на основе BST-дерева она сводится к слиянию двух деревьев. Как объединить два дерева бинарного поиска в одно? Существуют различные алгоритмы для выполнения этой задачи, но каждому из них присущи определенные недостатки. Например, можно выполнить обход первого BST-дерева, вставляя каждый из его узлов во второе BST-дерево (этот алгоритм можно записать одной строкой: в параметра подпрограммы обхода первого BST-дерева нужно передавать функцию вставки во второе BST-дерево). Время выполнения подобного решения не линейно, поскольку для каждой вставки может требоваться линейное время. Другой вариант - обход обоих BST-деревьев, занесение всех элементов в массив, их объединение и затем построение нового BST-дерева. Эту операцию можно выполнить за линейное время, но для нее нужен потенциально большой массив.

Программа 12.17 - компактная рекурсивная реализация операции объединить с линейным временем выполнения. Вначале мы вставляем корень первого BST-дерева во второе BST-дерево, используя метод вставки в корень. Эта операция дает два поддерева, ключи которых меньше этого корня, и два поддерева, ключи которых больше этого корня, поэтому требуемый результат получается (рекурсивным) объединением первой пары в левое поддерево корня, а второй пары - в правое поддерево корня (!). При каждом рекурсивном вызове каждый узел может оказаться корневым максимум один раз, поэтому общее время линейно. Пример работы этого алгоритма показан на , эта проблема легко устраняется рандомизацией. Обратите внимание, что в худшем случае количество сравнений, использованных для выполнения операции объединить, должно быть по крайней мере линейным; иначе можно было бы разработать алгоритм сортировки с менее чем NlgN сравнений, применяя такой подход, как восходящая сортировка слиянием (см. упражнение 12.88).

Программа 12.17. Объединение двух BST-деревьев

Если одно из BST-деревьев пустое, второе является результатом. Иначе два BST-дерева объединяются путем (произвольного) выбора корня первого дерева в качестве результирующего корня, вставки этого корня в корень второго дерева, а затем (рекурсивного) объединения пары левых поддеревьев и пары правых поддеревьев.

private:
  link joinR(link a, link b)
  { if (b == 0) return a;
    if (a == 0) return b;
    insertT(b, a->item);
    b->l = joinR(a->l, b->l);
    b->r = joinR(a->r, b->r);
    delete a; return b;
  }
public:
  void join(ST<Item, Key> b)
    { head = joinR(head, b.head); }
      

В программу не включен код, необходимый для поддержки полей счетчиков в узлах BST-дерева во время выполнения операций объединить и удалить - он может понадобиться в приложениях, где требуется и операция выбрать (программа 12.14). Концептуально эта задача проста, однако требует определенных усилий. Один из стандартных способов ее выполнения - реализация небольшой вспомогательной процедуры, которая устанавливает значение поля счетчика в узле на единицу больше, чем сумма полей счетчиков в его дочерних узлах, а затем вызов этой процедуры для каждого узла, у которого изменены ссылки. В частности, это можно выполнить для обоих узлов в процедурах rotL и rotR из программы 12.12, что достаточно для преобразований в программах 12.13 и 12.15, поскольку они преобразуют деревья исключительно путем ротаций. Для функций joinLR и removeR в программе 12.16 и join в программе 12.17 достаточно вызвать процедуру обновления счетчика для возвращаемого узла непосредственно перед оператором return.

Здесь показан результат (внизу) объединения двух BST-деревьев (вверху). Вначале мы вставляем корень G первого дерева во второе дерево, используя вставку в корень (второй сверху рисунок). У нас остаются два поддерева, ключи которых меньше G, и два поддерева с ключами, большими G. Объединение обеих пар (рекурсивно) дает конечный результат (внизу).

Базовые операции найти, вставить и сортировать для BST-деревьев легко реализуются и быстро работают даже при малой случайности в последовательности операций, поэтому BST-деревья широко используются для динамических таблиц символов. Они допускают также простые рекурсивные решения для поддержки других операций, как было показано в этой главе на примере операций выбрать, удалить и объединить, и как еще будет показано на многочисленных примерах далее в этой книге.

Несмотря на всю полезность, существует два основных недостатка использования BST-деревьев в приложениях. Во-первых, они требуют существенного дополнительного объема памяти под ссылки. Часто ссылки и записи имеют практически одинаковые размеры (скажем, одно машинное слово) - если это так, реализация с использованием BST-дерева использует две трети выделенного для него объема памяти под ссылки и только одну треть под ключи. Этот эффект менее важен в приложениях с большими записями и более важен в средах, в которых указатели велики. Если же память играет первостепенную роль, лучше вместо BST-деревьев предпочесть один из методов хеширования с открытой адресацией, описанных в .

Второй недостаток использования BST-деревьев - возможность того, что деревья могут стать плохо сбалансированными и в результате ухудшить производительность. В будут рассмотрены несколько подходов, гарантирующих хорошую производительность. При наличии достаточного объема памяти под ссылки эти алгоритмы делают BST-деревья весьма привлекательными в качестве основы для реализации АТД таблиц символов, поскольку обеспечивают гарантированно высокую производительность для большого набора полезных операций АТД.

Упражнения

12.78. Реализуйте нерекурсивную функцию выбрать для BST-дерева (см. программу 12.14).

12.79. Нарисуйте BST-дерево, образованное вставками элементов с ключами E A S Y Q U T I O N в первоначально пустое дерево и последующим удалением Q.

12.80. Нарисуйте BST-дерево, образованное вставками элементов с ключами E A S Y в первоначально пустое дерево, вставками элементов с ключами Q U E S T I O N в другое первоначально пустое дерево и последующего объединения результатов.

12.81. Реализуйте нерекурсивную функцию удалить для BST-дерева (см. программу 12.16).

12.82. Реализуйте версию операции удалить для BST-деревьев (программа 12.16), которая удаляет все узлы дерева с ключами, равными данному.

12.83. Измените реализации таблиц символов, основанные на BST-дереве, чтобы они поддерживали клиентские дескрипторы элементов (см. упражнение 12.7); добавьте реализации деструктора, конструктора копирования и перегруженной операции присваивания (см. упражнение 12.6); добавьте операции удалить и объединить; воспользуйтесь программой-драйвером из упражнения 12.22 для проверки полученных интерфейса и реализации АТД первого класса для таблицы символов.

12.84. Экспериментально определите увеличение высоты BST-дерева при выполнении длинной последовательности чередующихся случайных операций вставки и удаления в случайном дереве с N узлами, для N = 10, 100 и 1000, если для каждого значения N выполняется до N² пар вставок-удалений.

12.85. Реализуйте версию функции remove (см. программу 12.16), которая принимает случайное решение, заменять ли удаляемый узел его узлом-предком или узлом-потомком в дереве. Проведите экспериментальное исследование этой версии, как описано в упражнении 12.84.

12.86. Реализуйте версию функции remove, которая использует рекурсивную функцию для перемещения удаляемого узла в нижнюю часть дерева при помощи ротации, подобно вставке в корень (программа 12.13). Нарисуйте дерево, образованное в результате удаления этой программой корня из полного дерева, содержащего 31 узел.

12.87. Экспериментально определите увеличение высоты BST-дерева при многократной вставке элемента из корня в дерево, образованное объединением поддеревьев корня в случайное дерево из N узлов, для N = 10, 100 и 1000.

12.88. Реализуйте версию восходящей сортировки слиянием, основанной на операции объединить. Начните с помещения ключей в N деревьев, состоящих из одного узла, затем объедините эти деревья в пары для получения N/2 деревьев из двух узлов, далее объедините их для получения N/4 деревьев из четырех узлов и т.д.

12.89. Реализуйте версию функции join (см. программу 12.17), которая принимает случайное решение, использовать ли корень первого или второго дерева в качестве корня результирующего дерева. Проведите экспериментальное исследование этой версии, как описано в упражнении 12.87.