143
правки
Изменения
Новая страница: «right|300px|thumb|Пример 2-3 дерева ''' 2-3 дерево ''' — структура данных, пред...»
[[Файл:23дерево_new.jpg |right|300px|thumb|Пример 2-3 дерева]]
''' 2-3 дерево ''' — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. 2-3 дерево можно обобщить до [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+-дерева]].
== Структура ==
:*Все данные хранятся в листьях, в вершинах хранится вспомогательная информация,необходимая для организации поиска по поддеревьям.
:*Сыновья упорядочены по значению максимума поддерева сына.
:*Нелистовые вершины содержат 1 или 2 ключа, указывающие на диапазон значений в их поддеревьях.
:*Если нелистовая вершина имеет двух сыновей, то вершина хранит минимум правого поддерева; если трех, то первый ключ равен минимуму среднего поддерева, а второй ключ равен минимуму правого поддерева.
:*2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.
:*Высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> - количество элементов в дереве, поэтому операции поиска, добавления, удаления, слияния выполняются за время <tex>O(\log{n})</tex>.
== Операции ==
=== Поиск ===
Для поиска в 2-3 дереве необходимо последовательно просматривать ключи,
хранящиеся во внутренних ячейках, спускаясь от корня к листьям. Вначале ключ искомого
элемента сравнивается с первым ключом ячейки и, если искомый ключ меньше,
то осуществляется переход в левое поддерево. Иначе, сравниваем искомый ключ со вторым
ключом в ячейке (если второго ключа нет — поддерева всего два, то сразу переходим во
второе поддерево) и если наш ключ не превосходит второй ключ, то осуществляется переход
в среднее поддерево, а если превосходит, то идем в правое поддерево.
=== Вставка элемента ===
Есть два варианта вставки в 2-3 дерево.
1) Чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто добавить его как второй ключ к узлу.
[[Файл:23treeadd3.png|440px|border]] [[Файл:23treeadd4.png|400px|border]]
2) Если же в узле уже содержатся два ключа, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к тому, что придется делить родительский узел. Тогда таким же образом проходим до корня дерева.
[[Файл:23treeadd1.png|490px|border]] [[Файл:23treeadd2.png|400px|border]]
=== Удаление элемента ===
При удалении ключа из узла возникают три варианта.
1) Если после удаления ключа в узле содержится два ключа, то после удаления ничего не меняется.
2) Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Вершину, оставшуюся без детей, удаляем рекурсивно.
[[Файл:23treedel1.png|330px|border]] [[Файл:23treedel2.png|300px|border]] [[Файл:23treedel5.png|300px|border]]
3) Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключами.
[[Файл:23treedel3.png|300px|border]] [[Файл:23treedel4.png|320px|border]] [[Файл:23treedel6.png|300px|border]]
=== Слияние двух деревьев ===
Возможно два варианта слияния двух деревьев.
1) Если два дерева одной высоты, то слияние представляет собой добавление общей вершины.
[[Файл:23treemerge1.png|400px|border]] [[Файл:23treemerge2.png|400px|border]]
2) Если два дерева разной высоты, то при слиянии меньшее добавляем как поддерево к одной из вершин большего. Если возникает ситуация,когда у необходимого узла уже есть три ребенка, то делим его на два узла с двумя поддеревьями, переходим в родителя.Таким образом будем проходим по дереву вверх пока дерево не станет корректным.
[[Файл:23treemerge3.png|400px|border]] [[Файл:23treemerge4.png|400px|border]]
== Cсылки ==
* [http://is.ifmo.ru/vis/tree23/tree23_ru.html is.ifmo.ru - Визуализатор 2-3 дерева — 1]
* [http://rain.ifmo.ru/cat/view.php/vis/trees/2-3-2002 rain.ifmo.ru - Визуализатор 2-3 дерева — 2]
* [http://ru.wikipedia.org/wiki/2-3-дерево Википедия — 2-3 дерево]
* Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4
== См. также ==
* [[B-дерево]]
* [[Splay-дерево]]
* [[АВЛ-дерево]]
* [[Декартово дерево]]
* [[Красно-черное дерево]]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]
''' 2-3 дерево ''' — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. 2-3 дерево можно обобщить до [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+-дерева]].
== Структура ==
:*Все данные хранятся в листьях, в вершинах хранится вспомогательная информация,необходимая для организации поиска по поддеревьям.
:*Сыновья упорядочены по значению максимума поддерева сына.
:*Нелистовые вершины содержат 1 или 2 ключа, указывающие на диапазон значений в их поддеревьях.
:*Если нелистовая вершина имеет двух сыновей, то вершина хранит минимум правого поддерева; если трех, то первый ключ равен минимуму среднего поддерева, а второй ключ равен минимуму правого поддерева.
:*2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.
:*Высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> - количество элементов в дереве, поэтому операции поиска, добавления, удаления, слияния выполняются за время <tex>O(\log{n})</tex>.
== Операции ==
=== Поиск ===
Для поиска в 2-3 дереве необходимо последовательно просматривать ключи,
хранящиеся во внутренних ячейках, спускаясь от корня к листьям. Вначале ключ искомого
элемента сравнивается с первым ключом ячейки и, если искомый ключ меньше,
то осуществляется переход в левое поддерево. Иначе, сравниваем искомый ключ со вторым
ключом в ячейке (если второго ключа нет — поддерева всего два, то сразу переходим во
второе поддерево) и если наш ключ не превосходит второй ключ, то осуществляется переход
в среднее поддерево, а если превосходит, то идем в правое поддерево.
=== Вставка элемента ===
Есть два варианта вставки в 2-3 дерево.
1) Чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто добавить его как второй ключ к узлу.
[[Файл:23treeadd3.png|440px|border]] [[Файл:23treeadd4.png|400px|border]]
2) Если же в узле уже содержатся два ключа, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к тому, что придется делить родительский узел. Тогда таким же образом проходим до корня дерева.
[[Файл:23treeadd1.png|490px|border]] [[Файл:23treeadd2.png|400px|border]]
=== Удаление элемента ===
При удалении ключа из узла возникают три варианта.
1) Если после удаления ключа в узле содержится два ключа, то после удаления ничего не меняется.
2) Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Вершину, оставшуюся без детей, удаляем рекурсивно.
[[Файл:23treedel1.png|330px|border]] [[Файл:23treedel2.png|300px|border]] [[Файл:23treedel5.png|300px|border]]
3) Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключами.
[[Файл:23treedel3.png|300px|border]] [[Файл:23treedel4.png|320px|border]] [[Файл:23treedel6.png|300px|border]]
=== Слияние двух деревьев ===
Возможно два варианта слияния двух деревьев.
1) Если два дерева одной высоты, то слияние представляет собой добавление общей вершины.
[[Файл:23treemerge1.png|400px|border]] [[Файл:23treemerge2.png|400px|border]]
2) Если два дерева разной высоты, то при слиянии меньшее добавляем как поддерево к одной из вершин большего. Если возникает ситуация,когда у необходимого узла уже есть три ребенка, то делим его на два узла с двумя поддеревьями, переходим в родителя.Таким образом будем проходим по дереву вверх пока дерево не станет корректным.
[[Файл:23treemerge3.png|400px|border]] [[Файл:23treemerge4.png|400px|border]]
== Cсылки ==
* [http://is.ifmo.ru/vis/tree23/tree23_ru.html is.ifmo.ru - Визуализатор 2-3 дерева — 1]
* [http://rain.ifmo.ru/cat/view.php/vis/trees/2-3-2002 rain.ifmo.ru - Визуализатор 2-3 дерева — 2]
* [http://ru.wikipedia.org/wiki/2-3-дерево Википедия — 2-3 дерево]
* Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4
== См. также ==
* [[B-дерево]]
* [[Splay-дерево]]
* [[АВЛ-дерево]]
* [[Декартово дерево]]
* [[Красно-черное дерево]]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]
