як і просто процес пошуку (O (logb/2n)). Будь-який можливий при вставці випадок, при якому дерево піддається зміні, має константну трудомісткість. Отже TInsert=O ((logb/2n) + 1)=O (logb/2n).
Приклад вставки елемента з ключем рівним 7 (Рис.3 і Рис.4):
Пошук позиції для вставки елемента;
Т.к. знайдений лист сповнений, додаємо в дерево новий кінцевий вузол у вигляді правого брата листа;
Распределяем записи зі знайденого вузла (+ вставляється елемент) між двома кінцевими елементами дерева;
Ключ першого запису з нового аркуша копіюємо в батьківський вузол.
ДО:
ВУЗОЛ ПОВНИЙ
(Рис.3)
ПІСЛЯ:
.3 Видалення запису
Кроки для видалення елемента з B +-дерева:
Пошук запису, яку необхідно видалити. Цей пошук завершиться в листі L.
Якщо лист L містить більше мінімального числа елементів, то запис може бути безпечно видалена, без подальших дій.
Якщо аркуш містить мінімальну кількість записів, то видаляється елемент замінюється іншим, таким при якому збережеться правильний порядок. Щоб знайти такі записи, ми перевіряємо вузли-брати Lleft і Lright, один з них повинен існувати.
Якщо один з цих кінцевих вузлів має більш ніж мінімальна кількість записів, то записи передаються від цього брата, так що обидва вузла матимуть приблизно однакову кількість елементів. Ключі з батьківського вузла, можливо, повинні бути переглянуті.
Якщо обидва кінцевих вузла Lleft і Lright мають тільки мінімальну кількість записів, то L передає свої елементи одному з братів і видаляється з дерева. Новий лист буде містити не більше, ніж максимальне число дозволених записів.
Якщо останні два дочірніх вузла кореня зливаються в один, то цей об'єднаний вузол стає новим кореневим і дерево втрачає рівень.
Обчислювальна складність даної операції в гіршому випадку TDelete=O (logb/2n), де b - порядок дерева або коефіцієнт розгалуження; n - кількість елементів у дереві.
Доказ. Пошук видаляється елемента має таку ж обчислювальну складність як і просто процес пошуку (O (logb/2n)). Будь-який можливий при видаленні випадок, при якому дерево піддається зміні, має константну трудомісткість. Отже, TDelete=O ((logb/2n) + 1)=O (logb/2n).
Приклад видалення елемента з ключем рівним 7 (Рис.5 і Рис.6):
Пошук видаляється елемента;
Кінцевий вузол, що містить потрібну запис, має більше мінімальної кількості елементів, відбувається видалення запису;
Властивості дерева не порушені - перебудов не відбувається.
ДО:
(Рис.5)
ПІСЛЯ:
(Рис.6)
.4 Пошук по діапазону
+-дерева є одними з кращих для роботи з якоюсь областю значень.
Процес роботи операції:
Пошук першого елемента з діапазону в дереві
Після цього, інша частина за...
