Библиографический список. 1. Вирт Н. Алгоритмы + структуры данных = программы

1. Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир, 1985. – 544 с.

2. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989. – 360 с.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: Издательский дом «Вильямс», 2001. – 384 с.

4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2000. – 960 с.

5. Кнут Д. Искусство программирования. Т.3. Сортировка и поиск. – М.: Вильямс, 2002. – 720 с.

[1] В англоязычной литературе на равных используются термины «sorting» (сортировка) и «ordering» (упорядочение). Хотя слово «упорядочение» лучше отражает суть дела, на русском языке по каким-то причинам (возможно, фонетическим) гораздо чаще применяется термин «сортировка».

[2] Типичная ошибка, которую делают многие студенты, спеша запрограммировать HeapSort, заключается в том, что вместо предварительного выбора большего из сыновей они выполняют сравнение и перестановку a_k с каждым сыном по очереди. Пирамиду в конце концов построить удается, но времени на это уходит много. На рис. 3.1 это означает, что вместо одной ветви приходится перестраивать все поддерево вершины a_k.

[3] В некоторых книгах АВЛ-деревья называют просто «сбалансированными деревьями». Это не совсем справедливо по отношению к другим типам деревьев, упомянутым в предыдущем абзаце, которые тоже неплохо сбалансированы.

[4] Многие полагают, что буква «B» здесь означает «Binary». Так утверждается даже в некоторых серьезных книгах. На самом деле, эти деревья вовсе не бинарные, а буква «B» происходит от фамилии «Bayer».

[5] Интересно отметить, что B+-деревья используются в файловой системе NTFS для представления каталогов. Это позволяет уменьшить время поиска нужного файла, если общее число файлов в одном каталоге достигает нескольких сотен или тысяч.

[6] В знаменитой книге Д.Кнута [5] данная структура названа «trie», это искусственное слово есть гибрид «tree» (дерево) и «retrieve» (находить, извлекать). Переводчик первого издания предложил ввести на русском языке термин «бор», как намек на «дерево» и «выбор». Однако при переводе второго издания был предпочтен термин «нагруженное дерево».