Изменения

<wikitex>'''B-дерево''' — сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за $O(\log n)$. B-деревья схожи с [[Красно-черное дерево|красно-черными деревьями]] в том, что B-дерево с $n$ узлами имеют высоту $O(\lg n)$, но отличаются от [[Красно-черное дерево|них]] количеством детей узлов — от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). Сама высота B-дерева может быть значительно меньше чем у [[Красно-черное дерево|красно-черного дерева]], из-за его ветвистости, и, следовательно, основание логарифма, выражающего высоту дерева, может быть намного больше. Таким образом, В-деревья также могут использоваться для реализации

многих операций над динамическими множествами за время $O(\lg n)$

# Если удаление происходит из листа, смотрим на количество ключей в нем. Если ключей больше <tex>t - 1</tex>, то просто удаляем ключ. В противном случае, если существует соседний лист, который содержит больше <tex>t - 1</tex> ключа, удалим ключ из исходного узла, на его место поставим ключ-разделитель между исходным узлом и его соседом, а на его место поставим первый, если сосед правый, или последний, если сосед левый, ключ соседа. Если все соседи содержат по <tex>t - 1</tex> ключу, то объединяем узел с каким-либо из соседей, удаляем ключ и добавляем ключ-разделитель между узлами в объединенный узел. Если в родительском узле осталось меньше <tex>t - 1</tex> ключа, аналогичным образом добавляем в него ключи из соседей или объединяем узел в ними.

# Если удаление происходит не из листа, удаляем самый левый ключ из поддерева следующего дочернего узла или самый правый из поддерева предыдущего дочернего узла и ставим удаленный ключ на место удаляемого ключа в исходном узле.

== Ссылки ==

* T. H. Cormen «Introduction to Algorithms» third edition, Chapter 18

* Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4

* [http://habrahabr.ru/post/114154/ Хабрахабр. B-tree.]

== См. также ==

* [[2-3 дерево]]