ба (Guibas) и Седжвика 1978 г. Как видно из дат публикации этих статей, исследование сбалансированных деревьев продолжается. Перечисленные труды содержат подробные обоснования свойств RB-деревьев и аналогичных им структур, а также ссылки на более современные работы.

Трактовка trie-деревьев, приведенная в главе 15, является классической (хотя в литературе редко можно встретить реализации на языке С++), Материал по TST-де-ревьям взят из статьи Бентли (Bentley) и Седжвика, опубликованной в 1997 г.

В статье Байера (Bayer) и Мак-Крейта (McCreight), опубликованной в 1972 г., рассматриваются В-деревья; алгоритм расширяемого хеширования, представленный в главе 16, взят из статьи Фагина (Fagin), Нивергельта (Nievergelt), Пиппенгера (Pippenger) и Стронга (Strong), опубликованной в 1979 г. Аналитические результаты в отношении расширяемого хеширования были получены Флажолетом в 1983 г. С этими статьями обязательно следует ознакомиться всем, кто желает получить более подробную информацию по методам внешнего поиска. Практическое применение этих методов обусловлено контекстом систем баз данных. С введением в эту область можно ознакомиться, например, в книге Дейта (Date).

R. Baeza-Yates and G. Н. Gonnet, Handbook of Algorithms and Data Structures, second edition, Addison-Wesley, Reading,MA, 1984.

J. L. Bentley and R. Sedgewick, Sorting and searching strings, Eighth Symposium on Discrete Algorithms, New Orleans, January, 1997.

R. Bayer and E. M. McCreight, Organization and maintenance of large ordered indexes, Acta Informatica 1, 1972.

T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press, 1990.

C. J. Date, An Introduction to Database Systems, sixth edition, Addison-Wesley, Reading, MA, 1995.

R. Fagin, J. Nievergelt, N. Pippenger and H. R. Strong, Extendible hashing-a fast access method for dynamic files, ACM Transactions on Database Systems 4, 1979.

P. Flajolet, On the performance analysis of extendible hashing and trie search, Acta Informatica 20, 1983.

L. Guibas and R. Sedgewick, A dichromatic framework for balanced trees, in 19th Annual Symposium on Foundations of Computer Science, IEEE, 1978. Also in A Decade of Process 1970-1980, Xerox PARC, Palo Alto, CA.

D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching, second edition, Addison-Wesley, Reading, MA, 1997.

K. Mehlhom, Data Structures and Algorithms T. Sorting and Searching, Springer-Verlag, Berlin, 1984.

S. Roura and C. Martinez, Randomization of search trees by subtree size, Fourth European Symposium on Algorithms, Barcelona, September, 1996.

R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.

D. Sleator and R. E. Tarjan, Self-adjusting binary search trees, Journal of the ACM 31, 1985.

Предметный указатель

символы

:: 155 132 == 132

Абстрактные операции 26

find (поиск) 26, 31, 36

union (объединение) 26, 33, 36 Абстрактный объект 136 Абстрактный тип данных (АТД) 127,164

дек (double-ended queue). См. Очередь: двухсторонняя

Автоматическое распределение памяти 181 Алгоритм 21, 42, 110, 185, 190, 197, 296, 299, 316, 331. 402, 440, 603, 645

амортизации 525

амортизационного анализа 595

анализ 23, 42, 47

быстрого объединения 29. См. также Метод:

быстрого объединения быстрого поиска 27, 28. См. также Метод:

быстрого поиска быстрой сортировки 299. См. также Метод:

быстрой сортировки вероятностный 316

взвешенного быстрого объединения 32 вставки 603 Горнера 185, 572 Евклида 193

индексирования текстовых строк 640 обменного слияния 333 обхода дерева 235 объединения-поиска (union-find) 36 оперативный 36 оптимизации 525

пирамидальной сортировки (heapsort) 331

поиска 603, 645

поиска максимума 200

поразрядной сортировки 402. См. также

Поразрядная сортировка разделяй и властвуй 197, 207. См. также

Рекурсия

Алгоритм

рандомизированный 71 рандомизации 525 распределяющего подсчета 296 рекурсивный 190 сборка мусора 110

сжатия пути. См. Метод: сжатия пути (path compression)

случайного хеширования 590

сортировки 440 неадаптивный 440

хеширования 578 Амортизация 525 Анализ 23, 44

алгоритмов 42, 47

производительности 70

эмпирический 44 Аппроксимация 91

нормальная 91

функций 60 Асимптотическое выражение 57 Ассоциативная память 476

База данных 646 Байт 111, 401 Балансировка BST-дерева 524 Библиотека стандартных шаблонов С++ 22 Бинарный поиск 66, 493 Бит 404

Битонная (bitonic) последовательность 335 Бор (forest) 33, 219, 223. См. также Дерево Быстрая сортировка 299, 407 двоичная 407

нерекурсивная реализация 310 с разделением на три части 322 Быстрый поиск (quick-find) 28

Вектор 324

Вершина (vertex) 120, 219 Виртуальная память 467, 646

Внешний поиск 645 Внешняя сортировка 454 Вставка

в 2-3-4-дерево 541

в В-дерево 658

в BST-дерево 502

в RB-дерево 548, 549

в каталог расширяемого хеширования 673

в расширяемую хеш-таблицу 672

в списке пропусков 556

с расширением 536

со скосом 534 Выборка 326, 327, 330

медианы 327

нерекурсивная 327 Выражение 57

асимптотическое 57

Гармонические числа 54 Граф 26, 120, 224

насыщенный 123

неориентированный 121

обход графа 240

представление в виде списков смежности 122 разреженный 123 связный (connected) 225

Данные 45

ошибочные 45

реальные 45

случайные 45

структура 76, 86

тип 76 Данные-члены 129 Двоичное представление 62 Двоичный логарифм 53, 54 Двойное хеширование 588 Дек 164

Дерево 26, 29, 77, 189, 219, 311, 337, 358.

386, 477, 603 2-3- 552 2-3-4

нисходящее 540

построение 543

разделение 542

сбалансированное 540

Дерево В 652, 654

BST 505, 509, 515, 524

двойная ротация 535

рандомизованное 527

сбалансированное 524 М-арное 221 patricia 617 RB 545 trie 608

многопутевое 628 TST 629

бинарного поиска 238. 477, 498, 533

расширенное 533 бинарное 221, 236, 391 биномиальное 391 быстрой сортировки 311 главное 223 корень 30 красно-черное 545 неупорядоченное 224 обход дерева 190, 230 объединение дерева 530 остовное 26

разделяй и властвуй 337, 338

с корнем 220, 224

свободное 220

сортирующее 358, 363 индексное 386

суффиксов 640

упорядоченное 220

цифрового поиска (DST) 603 бинарное 604 Дескриптор 519. См. также Ссылка Деструктор 175

Динамические хеш-таблицы 594 Динамическое программирование 216 Динамическое распределение памяти 108 Доступ 649

индексированный последовательный 649 Драйвер

комплексных чисел 172

сортировки массивов 279