Изменения

Перейти к: навигация, поиск

B-дерево

5 байт убрано, 18:53, 12 июня 2012
м
Слияние
==== Слияние ====
<wikitex>[[Файл:BTMg.png|thumb|right|350px|Слияние узла братом]] Ниже будет рассмотрено слияние узлов при удалении ключей, то есть слияние узлов равной степени и высоты. Для произвольных же слияний потребуется приведение сливаемых деревьев к одной степени и высоте.  Итак, если выбранное для спуска поддерево $x.c_2$ и предшествующий и следующий узел-брат содержит минимальное количество ключей, то перемещение не возможно. На иллюстрации приводится слияние выбранного поддерева с предшествующим или следующим братом для такого случая. Для этого откладывается ключ из родительского узла $x$, который разделяет ключи на два сливаемых узла, в то время средний ключ перемещается в слитый узел. Ссылки на слитые дочерние узлы заменяются ссылкой на новый узел.  [[Файл:BTMg.png|450px|Слияние узла с братом]]Так как алгоритм гарантирует, что узел, в который будет совершаться спуск, содержит по меньшей мере $t$ ключей вместо требуемых условиями B-дерева $t - 1$ ключей, родительский узел $x$ содержит достаточное количество ключей, чтобы выделить ключ для слияния. Это условие может быть нарушено, только в том случае, если два ребенка корня сливаются, так как поиск начинается с этого узла. По условиям B-дерева у корня должен быть как минимум один ключ, если дерево не пусто. При слиянии двух последних детей корня последний ключ перемещается во вновь возникшего единственного ребёнка, что приводит к пустому корневому узлу в не пустом дереве. В этом случае пустой узел корня удаляется и заменяется на единственного ребенка.</wikitex>
== Вариации B-дерева ==
285
правок

Навигация