Логарифмический поиск в динамических таблицах
Здесь мы рассмотрим организацию в виде деревьев для таблиц, в которых часто встречаются включения и исключения. Что происходит с временем поиска в дереве, которое модифицировалось путем включения и исключения? Если включенные и исключенные имена выбраны случайно, то оказывается, что в среднем время поиска мало изменяется; но в худшем случае поведение плохое - деревья могут вырождаться в линейные списки, поиск в которых нужно осуществлять последовательно. Проблема вырождения дерева в линейный список, приводящая к времени поиска
вместо
в практических применениях выражена более резко, чем это указывается теоретическим анализом. Такой анализ обычно предполагает, что включения и исключения появляются случайным образом, но на практике часто это не так.
Случайные деревья бинарного поиска. Как ведут себя деревья бинарного поиска без ограничений в качестве динамических деревьев? Другими словами, предположим, что дерево бинарного поиска меняется при случайных включениях и исключениях.
Для включения
мы используем незначительную модификацию алгоритма 13.5. Если
не было найдено, мы получаем для
новую ячейку и связываем ее с последним узлом, пройденным во время безуспешного поиска
. Соответствующее предложение нельзя однако просто добавить в конце алгоритма 13.5, поскольку при нормальном окончании цикла
указатель
не указывает больше на последний пройденный узел, а вместо этого имеет значение
. В связи с этим мы должны производить включение до того, как выполняется предположение
или
; мы можем осуществить это, сделав процедуру включения рекурсивной. Процедура
выдает в качестве значения указатель на дерево, в которое добавлено
. Таким образом,
используется для включения
в
.
Алгоритм 13.6. Включение в дерево бинарного поиска
Исключение гораздо сложнее включения, и мы изложим здесь только основную идею. Если подлежащее удалению имя
имеет самое большее одного сына, то при исключении
его сын (если он вообще есть) объявляется сыном отца
. Если
имеет двух сыновей, его прямо удалить нельзя.
Вместо этого мы находим в таблице либо имя
, которое непосредственно предшествует
, либо имя
, которое непосредственно следует за
в естественном порядке. Оба имени принадлежат узлам, которые имеют не больше одного сына, и, таким образом,
можно исключить заменой его либо именем
, либо
, и затем исключением узла, который содержал
или
, соответственно.
Содержание раздела
