ВУЗ:
Составители:
124
Быстрый поиск в массивах, в которых используется связанное пред-
ставление данных, возможен в том случае, когда структура данных имеет вид
двоичного дерева. В таких массивах сочетается быстрый поиск и удобное веде-
ние.
Поиск в структуре, имеющей вид двоичного дерева, ведется в направ-
лении, задаваемом указателями. Правый указатель узла ведет к
записи с боль-
шим ключом, левый – к записи с меньшим ключом. Вычисления номера и адре-
са очередной записи при этом не требуется.
Первое обращение происходит к корню дерева. При этом и каждом по-
следующем обращении осуществляется сравнение аргумента поиска с ключом
записи текущего узла и определение направления следующего обращения. Если
в
результате сравнения выяснилось, что значение аргумента поиска больше
ключа записи текущего узла, то следующее обращение осуществляется по пра-
вому адресу связи, в противном случае следует обращение к порожденному уз-
лу левого поддерева.
Наименьшее число сравнений и наименьшее время потребуется при по-
иске в двоичном сбалансированном дереве, показанном на рис. 9.3.
Рис. 9.3. Сбалансированное двоичное дерево
Среднее число сравнений в сбалансированном дереве пропорционально
log
2
N, где N – число узлов дерева. В хорошо сбалансированном дереве макси-
мальное число сравнений равно числу уровней дерева.
В процессе поиска по двоичному дереву может быть осуществлена
вставка нового элемента. Например, в массив записей, имеющий структуру де-
рева, показанного на рис. 9.3, необходимо вставить запись с ключом 12. Эта
запись окажется включенной в
массив, если правый указатель записи с ключом
11 будет установлен на ячейку памяти с записью 12.
Наихудшие оценки поиска получаются для дерева упорядоченной по-
следовательности, изображенного на рис. 9.4. Среднее число сравнений для не-
го равно N/2, а максимальное число сравнений – N, т.е. поиск становится анало-
гичен последовательному.
6
3
7 10
2 5
4
9
8
1
11
1 2 3 5 6 7 8 9 10 114
Страницы
- « первая
- ‹ предыдущая
- …
- 122
- 123
- 124
- 125
- 126
- …
- следующая ›
- последняя »
