Изменения

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

B-дерево

682 байта добавлено, 20:00, 9 апреля 2012
Перемещение ключа
Для удаления требуется время $O(t log_t n)$ и $O(h)$ дисковых операций.</wikitex>
=== Перемещение ключа ===
<wikitex>Если выбранное для нисходящего прохода поддерево содержит минимальное количе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 | Dazu wird der linke Unterbaum von x.c_3.k_1 zum neuen rechten Unterbaum des verschobenen Schlüssels x.k_2./
...</wikitex>
285
правок

Навигация