————————————
————————————
Структура бинарного дерева поиска:
1-й диск ввода-вывода:
2-й диск ввода-вывода:
3-й диск ввода-вывода:
4-й диск ввода-вывода:
Давайте подробно рассмотрим B-дерево (Дерево баланса) B-дерево m-порядка имеет следующие характеристики:
1. Корневой узел имеет не менее двух дочерних узлов.
2. Каждый промежуточный узел содержит k-1 элементов и k потомков, где m/2
3. Каждый листовой узел содержит k-1 элементов, где m/2
4. Все листовые узлы расположены на одном уровне.
5. Элементы в каждом узле упорядочены от меньшего к большему, и k-1 элементов в узле точно соответствуют диапазону значений элементов, содержащихся в k дочерних элементах.
1-й диск ввода-вывода:
Найдите в памяти (сравните с 9):
2-й диск ввода-вывода:
Найдите в памяти (сравните с 2, 6):
3-й диск ввода-вывода:
Найдите в памяти (сравните с 3, 5):
Найдите позицию узла 4 сверху вниз и обнаружите, что 4 должен быть вставлен между элементами узла 3 и 5.
Узлы 3 и 5 уже являются двухэлементными узлами и не могут быть добавлены. Родительские узлы 2 и 6 также являются двухэлементными узлами и не могут быть увеличены. Корневой узел 9 представляет собой одноэлементный узел, который можно модернизировать до двухэлементного узла. тогдарасколотьУзлы 3, 5 и узлы 2, 6, пусть корневой узел 9 модернизируется до двухэлементных узлов 4, 9. Узел 6 независимо является вторым дочерним элементом корневого узла.
Найдите положение узла элемента 11 сверху вниз.
После удаления 11 узел 12 имеет только одного потомка, который не соответствует спецификации B-дерева. Итак, найдите медиану 13 трех узлов 12, 13, 15, замените узел 12, и сам узел 12 переместится вниз, чтобы стать первым потомком. (Этот процесс называетсяЛевша)
Друзья, которым понравилась эта статья, нажмите и удерживайте изображение, чтобы следить за номером подписки.программист маленький серый, смотрите больше захватывающего контента