Внешний поиск a

Ссылки для части IV

Основные источники для этого раздела — книги Кнута (Knuth); Баеса-Ятеса (Baeza-Yates) и Гонне (Gonnet); Мельхорна (Mehlhorn); и Кормена (Cormen), Ляйзерзона (Leiserson) и Райвеста (Rivest). В этих книгах подробно рассматриваются многие из приведенных в этой части алгоритмов, вместе с математическим анализом и предложениями по практическому применению. Классические методы подробно изложены в книге Кнута; более поздние методы описаны в остальных книгах, в них же приводятся ссылки на другую литературу. В этих четырех источниках, а также в книге Седжвика (Sedgewick) и Флажоле (Flajolet) описан практически весь материал, который упоминался как "выходящий за рамки этой книги".
Материал, приведенный в "Сбалансированные деревья" , взят из статьи Роура (Roura) и Мартинеса (Martinez) за 1996 г., статьи Слитора (Sleator) и Тарьяна (Tarjan) за 1985 г. и статьи Гиба (Guibas) и Седжвика за 1978 г. Как видно из дат публикации этих статей, исследование сбалансированных деревьев продолжается. Перечисленные источники содержат подробные доказательства свойств RB-деревьев и аналогичных им структур, а также ссылки на более современные работы.
Трактовка trie-деревьев, приведенная в "Поразрядный поиск" , является классической (хотя в литературе редко можно встретить реализации на языке C++). Материал по TST-деревьям взят из статьи Бентли (Bentley) и Седжвика за 1997 г.
B-деревья впервые рассматриваются в статье Байера (Bayer) и Мак-Крейта (McCreight) за 1972 г., а алгоритм расширяемого хеширования, представленный в главе 16, взят из статьи Фагина (Fagin), Нивергельта (Nievergelt), Пиппенгера (Pippenger) и Стронга (Strong), опубликованной в 1979 г. Аналитические результаты по расширяемому хешированию были получены Флажоле в 1983 г. С этими статьями следует обязательно ознакомиться всем, кто желает получить более подробную информацию по методам внешнего поиска. Практическое применение этих методов обусловлено распространенностью систем управления базами данных. С введением в эту область можно ознакомиться, например, в книге Дейта (Date).
1. R. Baeza-Yates and G. H. Gonnet, НаМЬоок of Algorithms and Data Structures, second edition, Addison-Wesley, Reading, MA, 1984.
2. J. L. Bentley and R. Sedgewick, "Sorting and searching strings," Eighth Symposium on Discrete Algorithms, New Orleans, January, 1997.
3. R. Bayer and E. M. McCreight, "Organization and maintenance of large ordered indexes," Acta Informatica 1, 1972.
4. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн, Алгоритмы: построение и анализ, 2-е издание, ИД "Вильямс", 2009 г.
5. К. Дж. Дейт, Введение в системы баз данных, 7-е издание, ИД "Вильямс", 2001 г.
6. 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. 7. P Flajolet, "On the performance analysis of extendible hashing and trie search," Acta Informatica 20, 1983.
8. L. Guibas and R. Sedgewick, "A dichromatic framework for balanced trees," in 19th Annual Symposium on Foundations of Computer Science, IEEE, 1978. Также в A Decade of Progress 1970-1980, Xerox PARC, Palo Alto, CA.
9. Д.Э. Кнут, Искусство программирования, том 3. Сортировка и поиск, 2-е издание, ИД "Вильямс", 2008 г.
10. K. Mehlhorn, Data Structures and Algorithms 1: Sorting and Searching, Spiinger-Vferlag, Berlin, 1984.
11. S. Roura and C. Martinez, "Randomization of search trees by subtree size," Fourth European Symposium on Algorithms, Barcelona, September, 1996.
12. R. Sedgewick and P Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.
13. D. Sleator and R. E. Tarjan, "Self-adjusting binary search trees," Journal of the ACM 32, 1985.