48
правок
Изменения
Нет описания правки
[[Файл:23дерево_new.jpg |right|300px|thumb|Пример 2-3 дерева]]
''' 2-3 дерево ''' — структура данных, предложенная в 1970 году Джоном Хопкрофтом,и представляющая собой [[B-дерево|B-дерево]] cтепени 1, такое что из каждого узла может выходить две или три ветви; при этом требуется, чтобы все внешние узлы находились на одном уровне. Каждый внутренний узел содержит либо один, либо два ключа. ==Значения ==Все данные хранятся в листьях, в вершинах хранится вспомогательная информация,необходимая для организации поиска по поддеревьям.Нелистовые вершины содержат 1 или 2 ключа, указывающие на диапазон значений в их поддеревьях.
== Структура ==
== Свойства ==
* 2-3 дерево - сливаемое дерево
* Все пути от корня до любого листа имеют одинаковую длину
* Высота 2-3 дерева лежит между <tex> O(\log_log{2} n </tex> и <tex> \log_{2} n )</tex>, где <tex> n </tex> - количество элементов в дереве.
Поэтому операции над ним выполняются за время <tex>O(\log{n})</tex>.
== Операции ==
Для поиска в 2-3 дереве необходимо последовательно просматривать ключи,
хранящиеся во внутренних ячейках, спускаясь от корня к листьям. Вначале ключ искомого
в среднее поддерево, а если превосходит, то идем в правое поддерево.
Есть два варианта вставки в 2-3 дерево.
[[Файл:23treeadd1.png|245px|border]] [[Файл:23treeadd2.png|200px|border]]
При удалении ключа из узла возникают три варианта.
[[Файл:23treedel3.png|200px|border]] [[Файл:23treedel4.png|215px|border]]
Возможно два варианта слияния двух деревьев.
[http://ru.wikipedia.org/wiki/2-3-дерево 2-3 дерево]
Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0
