9.4.4. Алгоритм поиска в дереве сортировки
Следующий алгоритм находит в дереве сортировки узел с указанным ключом, если он там есть.
Алгоритм 9.3. Поиск узла в дереве сортировки
Вход: дерево сортировки Т, заданное указателем на корень; ключ а.
Выход: указатель р на найденный узел или nil, если в дереве нет такого ключа.
р: = Т { указатель на проверяемый узел }
while р nil do
if a < p.i then
p:=p.l { продолжаем поиск слева }
else if a > p.i then
p : = p.r { продолжаем поиск справа }
else
return р { нашли узел }
end if
end while
обоснование
Этот алгоритм работает в точном соответствии с определением дерева сортировки: если текущий узел не искомый, то в зависимости от того, меньше или больше искомый ключ по сравнению с текущим, нужно продолжать поиск слева или справа, соответственно.
- Иркутский государственный технический университет
- 1. Определения графов
- 7.4.5. Массив дуг
- 8.4.2. Трансверсаль
- 8.5.4. Алгоритм нахождения максимального потока
- 8.6.3. Выделение компонент сильной связности
- 8.7.1. Длина дуг
- 8.7.2. Алгоритм Флойда
- 8.7.3. Алгоритм Дейкстры
- Глава 9 Деревья
- 9.1. Свободные деревья
- 9.1.1. Определения
- 9.1 .2. Основные свойства деревьев
- 9.2. Ориентированные, упорядоченные и бинарные деревья
- 9.2.1. Ориентированные деревья
- 9.2.2. Эквивалентное определение ордерева
- 9.2.3. Упорядоченные деревья
- 9.2.4. Бинарные деревья
- 9.3. Представление деревьев в эвм
- 9.3.1. Представление свободных, ориентированных и упорядоченных деревьев
- 9.3.2. Представление бинарных деревьев
- 9.3.3. Обходы бинарных деревьев
- 9.3.4. Алгоритм симметричного обхода бинарного дерева
- 9.4. Деревья сортировки
- 9.4.1. Ассоциативная память
- 9.4.2. Способы реализации ассоциативной памяти
- 9.4.3. Алгоритм бинарного (двоичного) поиска
- 9.4.4. Алгоритм поиска в дереве сортировки
- 9.4.5. Алгоритм вставки в дерево сортировки
- 9.4.6. Алгоритм удаления из дерева сортировки
- 9.4.7. Вспомогательные алгоритмы для дерева сортировки
- 9.4.8. Сравнение представлений ассоциативной памяти
- 9.4.9. Выровненные деревья
- 9.4.10. Сбалансированные деревья
- 9.5. Кратчайший остов
- 9.5.1. Определения
- 9.5.2. Схема алгоритма построения кратчайшего остова
- 9.5.3. Алгоритм Краскала
- Глава 10 Циклы
- 10.1. Фундаментальные циклы и разрезы
- 10.1.1. Циклы и коциклы
- 10.1.2. Независимые множества циклов и коциклов
- 10.1.3. Циклический и коциклический ранг
- 10.2. Эйлеровы циклы
- 10.2.1. Эйлеровы графы
- 10.2.2. Алгоритм построения эйлерова цикла в эйлеровом графе
- 10.2.3. Оценка числа эйлеровых графов
- 10.3. Гамильтоновы циклы
- 10.3.1. Гамильтоновы графы
- 10.3.2. Задача коммивояжера
- Глава 11 Независимость и покрытия
- 11.1. Независимые и покрывающие множества
- 11.1.1. Покрывающие множества вершин и ребер
- 11.1.2. Независимые множества вершин и ребер
- 11.1.3. Связь чисел независимости и покрытий
- 11.2. Построение независимых множеств вершин
- 11.2.1. Постановка задачи отыскания наибольшего независимого множества вершин
- 11.2.2. Поиск с возвратами
- 11.2.3. Улучшенный перебор
- 11.2.4. Алгоритм построения максимальных независимых множеств вершин
- 11.3. Доминирующие множества
- 11.3.1. Определения
- 11.3.2. Доминирование и независимость
- 11.3.3. Задача о наименьшем покрытии
- 11.3.4. Эквивалентные формулировки знп
- 11.3.5. Связь знп с другими задачами
- Глава 12 Раскраска графов
- 12.1. Хроматическое число
- Ух, . . . ,Vn одноцветные классы,доказательство
- 12.2. Планарность
- 12.2.2. Эйлерова характеристика
- 12.2.3. Теорема о пяти красках
- 12.3. Алгоритмы раскрашивания
- 12.3.1. Точный алгоритм раскрашивания
- 12.3.2. Приближенный алгоритм последовательного раскрашивания
- 12.3.3. Улучшенный алгоритм последовательного раскрашивания