30
Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
4.4. Алгоритмический поиск в динамических таблицах
4.4.1. Бинарный поиск в динамических таблицах
Динамическими называют такие таблицы, в которых происходит
включение и исключение имён. Очевидно, любое включение и исключение
нарушает построенное дерево бинарного поиска.
4.4.1.1. Включение
Пример
До включения:
i
1
2
3
4
5
x
i
2
5
8
11
16
Этой таблице может соответствовать следующее дерево поиска:
3
4
5
2
1
Рис. 21. Дерево поиска до включения
i
– номер вершины;
λ
- ссылка на лист, т.е. неуспех;
,
i i
l r
- левые и правые ключи;
x
i
- ключи.
1...,22,23,24,25,26,27,28,29,30,31 33,34,35,36,37,38,39,40,41,42,...106