Удаление

Задача: удалить запись со значением ключа v.

a) найдем путь от корня дерева к блоку i, содержащую запись с ключом v;

b) если записи нет, то ошибка. Если запись есть удалим эту запись пересортируем. Если после удаления в блоке не менее «е» записей, то если эта запись первая, тогда возможно требуется изменить индексный файл на предыдущих уровнях. Однако коррекции не будет подвергаться отец блока «i» (т.к. у него первая запись не имеет ключа). Но возможно другие предки имеют запись с ключом v, которая не является первой. Т.о. от блока «i» следует двигаться в верх к корню, и в случае, если обнаружится такая запись, то её следует удалить, применив данную процедуру. Реверсивно с константой d. (Хотя удалять и не обязательно, всё равно дерево будет работать как индекс). Если после удаления в блоке «i» менее «е» записей (т.е. е-1 записей), то рассмотрим соседних братьев (в том же уровне) блока «i», имеющих того же отца, что и блок «i». Если среди братьев есть блок «i», с числом записей больше чем «е», то распределить записи этих двух блоков (всего каких записей е< 3/2(е-1) < 2е-1) равномерно между двумя блоками «i» и «i₁», сохраняя отсортированный порядок. При этом возможно необходимо откорректировать предков «i». Если все братья «i» содержат ровно «е» записей, то соединим записи блоков «i» и любого соседнего блока «i₁» (у них всего 2е-1 записей) и т.о. все записи поместятся в один блок. Такое удаление потребует модификации и рекурсивного применения процедуры удаления к предкам «i», заменив константу е на константу d. При этом, возможно, необходимо удалить корень и объединённые блоки на предыдущем корню уровне образуют новый корень – размер дерева уменьшается на единицу.

Пример: d=2, е=2. Дерево содержит квадраты чисел.

Добавим запись с ключом 32.

Ищем блок, в который необходимо добавить – это i₇, но в нем нет места значит делим его на 2:

В i₃ надо добавить 36. В i₃ нет места это вместо 64

Добавляем в i₁ 64, которое ссылается на i₃, добавляем блок i₁₄ и i₁₅

Удалим запись с ключом 64.

Найти блок, это i₈ и удаляем 64. Новый ключ – 81, распределяем вверх изменяем в i₁₅ значение ключа 64 на 81 (всегда изменяем ровно 1 ключ). Но блок i₈ содержит 1 запись, заполнен меньше, чем на половину и имеется блок i₉, в котором меньше, чем 2е-1 запись, т.е. 2 и соединяем его с блоком i₈. У i₁₃ единственный сын необходимо удалить запись с ключом 100 из блока i₁₃ и, следовательно, соединить его с i₄, теперь вторая ссылка в этом блоке должна быть 144. Блок i₁₃ обладает указателями на i₁₀ и i₁₁. Значение ключа, сопровождающее указатель на i₁₁ находится в i₄, тогда как значение ключа 144 для блока i₁₀ в i₁₄. Вообще, если мы объединяем блоки при удалении, необходимое значение ключей содержатся либо в объединяемых блоках, либо в блоке, являющемся их общим отцом. При объединении i₁₃ и i₄ оказывается, что у i₁₄ существует единственный сын, поэтому объединяем i₁₄ с i₁. теперь у i₁₅ один сын. Т.к. он корень, то удаляем его.

и т.д.

Дата добавления: 2014-01-05