4.14. РЕЗЮМЕ
На рис. 4.36 приведены различные структуры данных, рассмотренные в этой главе, типы операций, которые можно совершать на их основе, и принимаемые нами соглашения о размере и природе того универсального множества, откуда брались элементы.
Рис. 4.36. (см. скан) Сводка свойств структур данных.
(см. скан)
Замечания по литературе
Информацию о разнообразии методов расстановки можно почерпнуть в книгах Морриса [1968], Ахо, Ульмана [1973] и Кнута [1973а]. Последняя содержит
также информацию о деревьях двоичного поиска. Алгоритм 4.2 для построения статического дерева двоичного поиска заимствован у Гилберта, Мура [1959]. Алгоритм сложности 
для той же задачи можно найти у Кнута [1971], где содержится также и решение упр. 4.6. Ху, Таккер [1971] показали, что время 
и память 
достаточны, чтобы построить оптимальное дерево двоичного поиска, в котором данные появляются только на листьях. Кнут [1973а] дал реализацию этого алгоритма за время 
Рейнгольд [1972] приводит оптимальные алгоритмы для многих основных преобразований множеств, таких, как объединение и пересечение. Алгоритм 4.3 для задачи 
был, по-видимому, впервые применен Мак-Илроем и Моррисом. Кнут [1969] приписывает сжатие путей Триттеру. Теорема 4.4 взята у Хопкрофта, Ульмана [1974], а теорема 
Тарьяна [1974]. Приложение к приравниванию идентификаторов и вычислению смещения, обсуждавшиеся в разд. 4.8, заимствованы у Галлера, Фишера [1964]. Приложение 3 об эквивалентности конечных автоматов взято из статьи Хопкрофта, Карпа [1971]. Упр. 4.16 и 4.17, касающиеся сложности алгоритма 4.3 без сжатия путей, взяты у Фишера [1972] и Патерсона [1973] соответственно.
АВЛ-деревья даны по Адельсону-Вельскому, Ландису [1962], а ответы на упр. 4.31 и 4.32 можно найти у Крейна [1972]. Понятие 
-сбалансированного дерева изложено по Нивергельту, Рейнгольду [1973]. Читатель может обратиться к этой работе по поводу упр. 4.34-4.37. Дальнейшие применения 2-3-деревьев можно найти в работе Ульмана [1974].
Упр. 4.22 представляет собой раннее решение задачи 
оно приведено Стирнзом, Розенкранцем [1969]. Упр. 4.38 содержится 
Хопкрофта, Ульмана [1974].
Различие между префиксным и свободным режимами работы алгоритмов ввели Хартманис, Льюис, Стирнз [1965]. Рабин [1963] изучил важный частный случай префиксных вычислений, называемый вычислением в реальное время.
Алгоритм разбиения и приложение к минимизации числа состояний конечного автомата взяты из статьи Хопкрофта [1971].
