Изменения

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

B-дерево

2 байта убрано, 21:44, 26 марта 2012
B-дерево
== B-дерево ==
<wikitex>'''B-дерево''' — сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за $O(\log n)$. B-деревья схожи с [[Красно-черное дерево|красно-черными деревьями]] в том, что B-дерево с $n$ узлами имеют высоту $O(\lg n)$, но отличаются от [[Красно-черное дерево|них]] количеством детей узлов — от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). Сама высота B-дерева может быть значительно меньше чем у [[Красно-черное дерево|красно-черного дерева]], из-за его ветвистости, и, следовательно, основание логарифма, выражающего высоту дерева, может быть намного больше. Таким образом, В-деревья также могут использоваться для реализации
многих операций над динамическими множествами за время $O(\lg n)$
B-дерево было впервые предложено Р. Бэйером и Е. МакКрейтом в 1970 году.</wikitex>
== Структура ==
285
правок

Навигация