Изменения

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

B-дерево

10 байт убрано, 18:51, 12 июня 2012
м
Перемещение ключа
==== Перемещение ключа ====
<wikitex>[[Файл:BTMv.png|thumb|left|350px|Перемещение ключа в B-дереве]]Если выбранное для нисходящего прохода поддерево содержит минимальное количеcтво ключей $t-1$, и предшествующие и следующие узлы-братья имеют по меньшей мере $t$ ключей, то ключ перемещается в выбранный узел. Поиск выбрал для спуска $x.c_2$ ($x.k_1<k_{delete}<x.k_2$). Этот узел имеет лишь $t-1$ ключ (красная стрелка). Так как следующий брат $x.c_3$ содержит достаточное количество ключей, самый маленький ключ $x.c_3.k_1$ может перемещаться оттуда в родительский узел, чтобы перемещатьперестить, в свою очередь, ключ $x.k_2$ как дополнительный ключ в выбранный для спуска узел. Левое поддерево $x.c_3.k_1$ — новое правое поддерево перемещённого ключа $x.k_2$.  [[Файл:BTMv.png|450px|Перемещение ключа в B-дереве]]Легко убедиться в том, что эти повороты поддерживают структуру B-дерева: для всех ключей $k$ на отложенном поддереве до и после перенесения выполняется условие $x.k_2 \leqslant k \leqslant x.c_3.k_1$. Симметричная операция может производиться для перенесения ключа из предшествующего брата.</wikitex>
==== Слияние ====
285
правок

Навигация