Какой элемент является "средним" в B-дереве четного порядка?
Если у меня есть B-дерево порядка 4 со следующими данными в нем...
и мне нужно добавить 2 к дереву; я...
- добавьте 2 к узлу (сделав его недействительным, поскольку теперь у него 4 ключа), затем разделите узел, взяв значение 2 в качестве среднего значения и распространяя его вверх
ИЛИ ЖЕ
- мне не добавить 2, взять 3 в качестве среднего значения, распространить 3 вверх, а затем добавить 2 в правильный узел?
Извините за плохую диаграмму.
2 ответа
Вы выполняете первый вариант. Для B-дерева любого порядка вы всегда добавляете узел, а затем выполняете разбиения, которые распространяются вверх. Для отличной интерактивной демонстрации различных базовых операций (вставка, удаление, поиск) над структурами данных есть полезная страница визуализации алгоритма, на которую я захожу, здесь. Найдите страницу B-дерева, и вы обнаружите, что она выполняет опцию 1.
Как найти, какой элемент нажать вверх:
1) Вставьте элемент в правильное положение Btree и проверьте, не произошло ли переполнение.
Если затем, выполните шаги 2 и 3, приведенные ниже.
2) найти потолок((order of Btree+1)/2).
3) Переместите этот индексный элемент вверх, указав два указателя на левое и правое поддерево.
Примечание. Сначала вставьте элемент, затем выполните шаги 2 и 3 в случае переполнения.
Вот в этом примере сначала вставьте 2.
Частичный лист дерева становится |1| 2| 3| 5|.
переполнение происходит потому, что в любом узле может быть только 3 ключа.
Найти потолок ((4+1)/2)= потолок (5/2)= 3 (индекс №)
3-е значение индекса 3 - средний элемент. так распространяйте это. Левый указатель 3 указывает на 1 | 2, а правый указывает на 5.