2011г.
Количество страниц: 704

Второе издание одной из самых авторитетных книг Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. Лафоре по программированию посвящено использованию структур данных и алгоритмов. Алгоритмы — это основа программирования, определяющая, каким образом разрабатываемое программное обеспечение будет использовать структуры данных. На четких и простых программных примерах автор объясняет эту сложную тему, предлагая читателям написать собственные программы и на практике освоить полученные знания. Рассматриваемые примеры написаны на языке Java, хотя для усвоения материала читателю не обязательно хорошо знать его — достаточно владеть любым языком программирования, например C++. Первая часть книги представляет собой введение в алгоритмизацию и структуры данных, а также содержит изложение основ объектно-ориентированного программирования. Следующие части посвящены различным алгоритмам и структурам данных, рассматриваемым от простого к сложному: сортировка, абстрактные типы данных, связанные списки, рекурсия, древовидные структуры данных, хеширование, пирамиды, графы. Приводятся рекомендации по использованию алгоритмов и выбору той или иной структуры данных в зависимости от поставленной задачи.

Оглавление книги

Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. Лафоре

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Второе издание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Дополнительные темы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

О чем эта книга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Чем эта книга отличается от других . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

Доступность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

Приложения Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

Примеры кода Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

Для кого написана эта книга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Что необходимо знать читателю . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Необходимые программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Как организован материал книги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Вперед! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Глава 1. Общие сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Зачем нужны структуры данных и алгоритмы? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Хранение реальных данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

Инструментарий программиста . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

Моделирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Обзор структур данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

База данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

Запись . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

Поле . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

Ключ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Объектно-ориентированное программирование . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Недостатки процедурных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Объекты в двух словах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

Создание объектов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

Вызов методов объекта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

Пример объектно-ориентированной программы . . . . . . . . . . . . . . . . . . . . . . 33

Наследование и полиморфизм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

Программотехника . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Java для программистов C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

В Java нет указателей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Ввод/вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Структуры данных библиотеки Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

Глава 2. Массивы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

Приложение Array Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

Вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

Поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

Удаление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Проблема дубликатов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Не слишком быстро . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

Поддержка массивов в Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

Создание массива . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

Обращение к элементам массива . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

Инициализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

Пример массива . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

Деление программы на классы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

Классы LowArray и LowArrayApp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

Интерфейсы классов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

Не слишком удобно . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Кто чем занимается? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Пример highArray.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

Удобство пользователя . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

Абстракция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

Приложение Ordered Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

Линейный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

Двоичный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

Реализация упорядоченного массива на языке Java . . . . . . . . . . . . . . . . . . . . . . . 67

Двоичный поиск с методом find() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

Класс OrdArray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

Преимущества упорядоченных массивов . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

Логарифмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

Формула . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

Операция, обратная возведению в степень . . . . . . . . . . . . . . . . . . . . . . . . . . 74

Хранение объектов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Класс Person . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Программа classDataArray.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

O-синтаксис . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

Вставка в неупорядоченный массив: постоянная сложность . . . . . . . . . . . . 80

Линейный поиск: сложность пропорциональна N . . . . . . . . . . . . . . . . . . . . . . 80

Двоичный поиск: сложность пропорциональна log(N) . . . . . . . . . . . . . . . . . . 80

Константа не нужна . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

Почему бы не использовать только массивы? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

Глава 3. Простая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Как это делается? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Пузырьковая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

Пример пузырьковой сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

Приложение BubbleSort Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

Реализация пузырьковой сортировки на языке Java . . . . . . . . . . . . . . . . . . . 94

Инварианты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

Сложность пузырьковой сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

Сортировка методом выбора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

Пример сортировки методом выбора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

Приложение SelectSort Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

Реализация сортировки методом выбора на языке Java . . . . . . . . . . . . . . . 101

Инвариант . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

Сложность сортировки методом выбора . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

Сортировка методом вставки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

Пример сортировки методом вставки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

Приложение InsertSort Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

Сортировка 10 столбцов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

Реализация сортировки методом вставки на языке Java . . . . . . . . . . . . . . 108

Инварианты сортировки методом вставки . . . . . . . . . . . . . . . . . . . . . . . . . . 111

Сложность сортировки методом вставки . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

Сортировка объектов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

Реализация сортировки объектов на языке Java . . . . . . . . . . . . . . . . . . . . . 112

Лексикографические сравнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

Устойчивость сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

Сравнение простых алгоритмов сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

Глава 4. Стеки и очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

Другие структуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

Инструменты программиста . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

Ограничение доступа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

Абстракция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

Стеки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

Почтовая аналогия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

Приложение Stack Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

Реализация стека на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

Пример использования стека № 1. Перестановка букв в слове . . . . . . . . . 129

Пример № 2. Поиск парных скобок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

Эффективность стеков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

Очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

Приложение Queue Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

Циклическая очередь . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

Реализация очереди на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

Эффективность очередей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

Дек . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

Приоритетные очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

Приложение The PriorityQ Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

Реализация приоритетной очереди на языке Java . . . . . . . . . . . . . . . . . . . . 150

Эффективность приоритетных очередей . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

Разбор арифметических выражений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

Постфиксная запись . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

Преобразование инфиксной записи в постфиксную . . . . . . . . . . . . . . . . . . 154

Как мы вычисляем результаты инфиксных выражений . . . . . . . . . . . . . . . . 154

Вычисление результата постфиксного выражения . . . . . . . . . . . . . . . . . . . 170

Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

Глава 5. Связанные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

Строение связанного списка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

Ссылки и базовые типы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

Отношения вместо конкретных позиций . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

Приложение LinkList Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

Вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

Поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184

Удаление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184

Простой связанный список . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

Класс Link . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

Класс LinkList . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

Программа linkList.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

Поиск и удаление заданных элементов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

Метод find() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

Метод delete() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

Другие методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

Двусторонние списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

Эффективность связанных списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

Абстрактные типы данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

Реализация стека на базе связанного списка . . . . . . . . . . . . . . . . . . . . . . . . 201

Реализация очереди на базе связанного списка . . . . . . . . . . . . . . . . . . . . . 204

Типы данных и абстракция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

Списки ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208

Абстрактные типы данных как инструмент проектирования . . . . . . . . . . . . 209

Сортированные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

Реализация вставки элемента в сортированный список на языке Java . . 211

Программа sortedList.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212

Эффективность сортированных списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214

Сортировка методом вставки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

Двусвязные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217

Перебор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

Вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

Удаление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221

Программа doublyLinked.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

Двусвязный список как база для построения дека . . . . . . . . . . . . . . . . . . . . 226

Итераторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226

Ссылка на элемент списка? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

Итератор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

Другие возможности итераторов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228

Методы итераторов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

Программа interIterator.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230

На что указывает итератор? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236

Метод atEnd() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236

Итеративные операции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236

Другие методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239

Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241

Глава 6. Рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243

Треугольные числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243

Вычисление n-го треугольного числа в цикле . . . . . . . . . . . . . . . . . . . . . . . . 244

Вычисление n-го треугольного числа с применением рекурсии . . . . . . . . 245

Программа triangle.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

Что реально происходит? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248

Характеристики рекурсивных методов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249

Насколько эффективна рекурсия? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250

Математическая индукция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250

Факториал . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250

Анаграммы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

Рекурсивный двоичный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257

Замена цикла рекурсией . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258

Алгоритмы последовательного разделения . . . . . . . . . . . . . . . . . . . . . . . . . 262

Ханойская башня . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262

Приложение Towers Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263

Перемещение поддеревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264

Рекурсивный алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264

Программа towers.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266

Сортировка слиянием . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267

Слияние двух отсортированных массивов . . . . . . . . . . . . . . . . . . . . . . . . . . . 268

Сортировка слиянием . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270

Приложение MergeSort Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273

Программа mergeSort.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274

Устранение рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281

Что дальше? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287

Интересные применения рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289

Возведение числа в степень . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289

Задача о рюкзаке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

Комбинации и выбор команды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294

Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295

Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

Глава 7. Нетривиальная сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299

Сортировка Шелла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299

Сортировка методом вставок: слишком много копирования . . . . . . . . . . . 300

N-сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300

Сокращение интервалов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302

Приложение Shellsort Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303

Реализация сортировки Шелла на языке Java . . . . . . . . . . . . . . . . . . . . . . . . 305

Другие интервальные последовательности . . . . . . . . . . . . . . . . . . . . . . . . . 307

Эффективность сортировки Шелла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308

Разбиение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

Приложение Partition Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

Остановка и перестановка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313

Быстрая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316

Алгоритм быстрой сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317

Выбор опорного значения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318

Приложение QuickSort1 Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323

Вырожденное быстродействие O(N2

) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327

Определение медианы по трем точкам . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328

Обработка малых подмассивов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333

Устранение рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336

Поразрядная сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339

Проектирование программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340

Эффективность поразрядной сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . 340

Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341

Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343

Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344

Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344

Глава 8. Двоичные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346

Для чего нужны двоичные деревья? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346

Медленная вставка в упорядоченном массиве . . . . . . . . . . . . . . . . . . . . . . . 346

Медленный поиск в связанном списке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347

Деревья приходят на помощь . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347

Что называется деревом? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347

Терминология . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348

Аналогия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351

Как работают двоичные деревья? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352

Приложение Binary Tree Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352

Представление деревьев в коде Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354

Поиск узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356

Поиск узла в приложении Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356

Реализация поиска узла на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358

Эффективность поиска по дереву . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358

Вставка узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359

Вставка узла в приложении Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359

Реализация вставки на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359

Обход дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361

Симметричный обход . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361

Реализация обхода на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362

Обход дерева из трех узлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362

Обход дерева в приложении Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

Симметричный и обратный обход . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365

Поиск минимума и максимума . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367

Удаление узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368

Случай 1. Удаляемый узел не имеет потомков . . . . . . . . . . . . . . . . . . . . . . . 368

Случай 2. Удаляемый узел имеет одного потомка . . . . . . . . . . . . . . . . . . . . 370

Случай 3. Удаляемый узел имеет двух потомков . . . . . . . . . . . . . . . . . . . . . . 372

Эффективность двоичных деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379

Представление дерева в виде массива . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381

Дубликаты ключей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382

Полный код программы tree.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383

Код Хаффмана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391

Коды символов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391

Декодирование по дереву Хаффмана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393

Построение дерева Хаффмана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394

Кодирование сообщения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396

Создание кода Хаффмана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397

Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397

Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399

Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400

Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401

Глава 9. Красно-черные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403

Наш подход к изложению темы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403

Концептуальное понимание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404

Нисходящая вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404

Сбалансированные и несбалансированные деревья . . . . . . . . . . . . . . . . . . . . . . 404

Вырождение до O(N) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405

Спасительный баланс . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406

Характеристики красно-черного дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406

Исправление нарушений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408

Работа с приложением RBTree Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408

Щелчок на узле . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409

Кнопка Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409

Кнопка Ins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409

Кнопка Del . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409

Кнопка Flip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410

Кнопка RoL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410

Кнопка RoR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410

Кнопка R/B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410

Текстовые сообщения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410

Где кнопка Find? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410

Эксперименты с приложением Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411

Эксперимент 1. Вставка двух красных узлов . . . . . . . . . . . . . . . . . . . . . . . . . 411

Эксперимент 2. Повороты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412

Эксперимент 3. Переключение цветов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412

Эксперимент 4. Несбалансированное дерево . . . . . . . . . . . . . . . . . . . . . . . 413

Эксперименты продолжаются . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414

Красно-черные правила и сбалансированные деревья . . . . . . . . . . . . . . . . 414

Пустые потомки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415

Повороты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415

Простые повороты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416

Переходящий узел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416

Перемещения поддеревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417

Люди и компьютеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419

Вставка узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419

Общая схема процесса вставки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419

Переключения цветов при перемещении вниз . . . . . . . . . . . . . . . . . . . . . . . 420

Повороты после вставки узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422

Повороты при перемещении вниз . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427

Удаление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430

Эффективность красно-черных деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431

Реализация красно-черного дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431

Другие сбалансированные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432

Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433

Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433

Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435

Глава 10. Деревья 2-3-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436

Знакомство с деревьями 2-3-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436

Почему деревья 2-3-4 так называются? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437

Структура дерева 2-3-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438

Поиск в дереве 2-3-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439

Вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439

Разбиение узлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440

Разбиение корневого узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441

Разбиение при перемещении вниз . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442

Приложение Tree234 Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442

Кнопка Fill . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443

Кнопка Find . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443

Кнопка Ins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444

Кнопка Zoom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444

Просмотр разных узлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445

Эксперименты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446

Реализация дерева 2-3-4 на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447

Класс DataItem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447

Класс Node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447

Класс Tree234 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448

Класс Tree234App . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449

Полный код программы tree234.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450

Деревья 2-3-4 и красно-черные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457

Преобразование деревьев 2-3-4 в красно-черные деревья . . . . . . . . . . . . 457

Эквивалентность операций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459

Эффективность деревьев 2-3-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461

Скорость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461

Затраты памяти . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462

Деревья 2-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462

Разбиение узлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463

Реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465

Внешнее хранение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466

Обращение к внешним данным . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466

Последовательное хранение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469

B-деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471

Индексирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476

Сложные критерии поиска . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478

Сортировка внешних файлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479

Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482

Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484

Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485

Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485

Глава 11. Хеш-таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487

Хеширование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487

Табельные номера как ключи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488

Индексы как ключи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488

Словарь . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489

Хеширование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492

Коллизии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494

Открытая адресация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495

Линейное пробирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495

Реализация хеш-таблицы с линейным пробированием на языке Java . . . 500

Квадратичное пробирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507

Двойное хеширование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509

Метод цепочек . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517

Приложение HashChain Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517

Реализация метода цепочек на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . 520

Хеш-функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525

Быстрые вычисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526

Случайные ключи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526

Неслучайные ключи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526

Хеширование строк . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528

Свертка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530

Эффективность хеширования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530

Открытая адресация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530

Метод цепочек . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532

Сравнение открытой адресации с методом цепочек . . . . . . . . . . . . . . . . . . 534

Хеширование и внешнее хранение данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535

Таблица файловых указателей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535

Неполные блоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535

Полные блоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536

Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537

Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 538

Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540

Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540

Глава 12. Пирамиды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542

Общие сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543

Приоритетные очереди, пирамиды и ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . 544

Слабая упорядоченность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544

Удаление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545

Вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547

Условные перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548

Приложение Heap Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549

Заполнение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550

Изменение приоритета . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Каталог книг

Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. Лафоре

Доставка Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. Лафоре почтой наложным платежом.