Составители:
69
Items[Count].NextNode – на поддерево элементов, больших
Items[Count].Value.
У корневой вершины PreviousNode будет равен nil.
1.4.2.2. Основные операции
Основные операции, производимые с B-деревьями:
– поиск элемента;
– добавление элемента;
– удаление элемента.
При рассмотрении этих основных операций будут разбираться не-
большие деревья, хотя в реальности B-деревья применяются при работе
с большими массивами информации. Кроме того, для наглядности, на
рисунках будут опускаться поля указателей.
Поиск элемента будем начинать с корневой вершины. Если искомый
элемент присутствует в загруженной вершине, то завершаем поиск с
положительным ответом, иначе загружаем следующую вершину, и так
до тех пор, пока либо найдем искомый элемент, либо не окажется сле-
дующей вершины (пришли в лист B-дерева).
Посмотрим на примере, как это реализуется (рис. 20).
Будем искать элемент 11. Сначала загрузим корневую вершину. Эта
вершина содержит элементы 5 и 13. Искомый элемент больше 5, но
меньше 13. Значит, следует идти по ссылке, идущей от элемента 5. Заг-
ружаем следующую вершину (с элементами 8 и 10). Эта вершина тоже
не содержит искомого элемента. Замечаем, что 11 больше 10, следова-
тельно, двигаемся по ссылке, идущей от элемента 10. Загружаем соот-
ветствующую вершину (с элементами 11 и 12), в которой и находим
искомый элемент. Итак, в этом примере, чтобы найти элемент, потре-
бовалось три раза обратиться к внешней памяти для чтения очередной
вершины.
5 13
1 2 4 6 7 9
11 12
14 15 17
3
8 10
16
Рис. 20. Поиск элемента в B-дереве
Страницы
- « первая
- ‹ предыдущая
- …
- 67
- 68
- 69
- 70
- 71
- …
- следующая ›
- последняя »
