2-3 дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 23: Строка 23:
 
Есть два варианта вставки в 2-3 дерево.
 
Есть два варианта вставки в 2-3 дерево.
  
1)Чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто добавить его как второй ключ к узлу.
+
1) Чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто добавить его как второй ключ к узлу.
  
 
[[Файл:23treeadd3.png|440px|border]]  [[Файл:23treeadd4.png|400px|border]]  
 
[[Файл:23treeadd3.png|440px|border]]  [[Файл:23treeadd4.png|400px|border]]  
  
2)Если же в узле уже содержатся два ключа, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к тому, что придется делить родительский узел. Тогда таким же образом проходим до корня дерева.
+
2) Если же в узле уже содержатся два ключа, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к тому, что придется делить родительский узел. Тогда таким же образом проходим до корня дерева.
  
 
[[Файл:23treeadd1.png|490px|border]]  [[Файл:23treeadd2.png|400px|border]]
 
[[Файл:23treeadd1.png|490px|border]]  [[Файл:23treeadd2.png|400px|border]]
Строка 34: Строка 34:
 
При удалении ключа из узла возникают три варианта.
 
При удалении ключа из узла возникают три варианта.
  
1)Если после удаления ключа в узле содержится два ключа, то после удаления ничего не меняется.
+
1) Если после удаления ключа в узле содержится два ключа, то после удаления ничего не меняется.
  
2)Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Вершину, оставшуюся без детей, удаляем рекурсивно.  
+
2) Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Вершину, оставшуюся без детей, удаляем рекурсивно.  
  
 
[[Файл:23treedel1.png|330px|border]]  [[Файл:23treedel2.png|300px|border]] [[Файл:23treedel5.png|300px|border]]
 
[[Файл:23treedel1.png|330px|border]]  [[Файл:23treedel2.png|300px|border]] [[Файл:23treedel5.png|300px|border]]
  
3)Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключами.
+
3) Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключами.
  
 
[[Файл:23treedel3.png|300px|border]]  [[Файл:23treedel4.png|320px|border]] [[Файл:23treedel6.png|300px|border]]  
 
[[Файл:23treedel3.png|300px|border]]  [[Файл:23treedel4.png|320px|border]] [[Файл:23treedel6.png|300px|border]]  
Строка 47: Строка 47:
 
Возможно два варианта слияния двух деревьев.
 
Возможно два варианта слияния двух деревьев.
  
1)Если два дерева одной высоты, то слияние представляет собой добавление общей вершины.
+
1) Если два дерева одной высоты, то слияние представляет собой добавление общей вершины.
  
 
[[Файл:23treemerge1.png|400px|border]]  [[Файл:23treemerge2.png|400px|border]]  
 
[[Файл:23treemerge1.png|400px|border]]  [[Файл:23treemerge2.png|400px|border]]  
  
2)Если два дерева разной высоты, то при слиянии меньшее добавляем как поддерево к одной из вершин большего.Если возникает ситуация,когда у необходимого узла уже есть три ребенка, то делим его на два узла с двумя поддеревьями и проверяем родителя.Таким образом проходим по дереву вверх до полной сбалансировки.
+
2) Если два дерева разной высоты, то при слиянии меньшее добавляем как поддерево к одной из вершин большего.Если возникает ситуация,когда у необходимого узла уже есть три ребенка, то делим его на два узла с двумя поддеревьями и проверяем родителя.Таким образом проходим по дереву вверх до полной сбалансировки.
  
 
[[Файл:23treemerge3.png|400px|border]]  [[Файл:23treemerge4.png|400px|border]]
 
[[Файл:23treemerge3.png|400px|border]]  [[Файл:23treemerge4.png|400px|border]]
  
 
== Cсылки ==
 
== Cсылки ==
* [http://is.ifmo.ru/vis/tree23/tree23_ru.html is.ifmo.ru - Визуализатор 2-3 дерева - 1]
+
* [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://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 дерево]
+
* [http://ru.wikipedia.org/wiki/2-3-дерево Википедия 2-3 дерево]
 
* Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4
 
* Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4
 
== См. также ==
 
== См. также ==

Версия 20:03, 30 марта 2012

Пример 2-3 дерева

2-3 дерево — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. 2-3 дерево можно обобщить до B+-дерева.

Структура

  • Все данные хранятся в листьях, в вершинах хранится вспомогательная информация,необходимая для организации поиска по поддеревьям.
  • Сыновья упорядочены по значению максимума поддерева сына.
  • Нелистовые вершины содержат 1 или 2 ключа, указывающие на диапазон значений в их поддеревьях.
  • Если нелистовая вершина имеет двух сыновей, то вершина хранит минимум поддерева; если трех, то первый ключ равен минимуму среднего поддерева, а второй ключ равен минимуму правого поддерева.
  • 2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.
  • Высота 2-3 дерева [math]O(\log{n})[/math], где [math] n [/math] - количество элементов в дереве, поэтому операции поиска, добавления, удаления, слияния выполняются за время [math]O(\log{n})[/math].

Операции

Поиск

Для поиска в 2-3 дереве необходимо последовательно просматривать ключи, хранящиеся во внутренних ячейках, спускаясь от корня к листьям. Вначале ключ искомого элемента сравнивается с первым ключом ячейки и, если искомый ключ не больше первого, то осуществляется переход в левое поддерево. Иначе, сравниваем искомый ключ со вторым ключом в ячейке (если второго ключа нет — поддерева всего два, то сразу переходим во второе поддерево) и если наш ключ не превосходит второй ключ, то осуществляется переход в среднее поддерево, а если превосходит, то идем в правое поддерево.

Вставка элемента

Есть два варианта вставки в 2-3 дерево.

1) Чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто добавить его как второй ключ к узлу.

23treeadd3.png 23treeadd4.png

2) Если же в узле уже содержатся два ключа, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к тому, что придется делить родительский узел. Тогда таким же образом проходим до корня дерева.

23treeadd1.png 23treeadd2.png

Удаление элемента

При удалении ключа из узла возникают три варианта.

1) Если после удаления ключа в узле содержится два ключа, то после удаления ничего не меняется.

2) Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Вершину, оставшуюся без детей, удаляем рекурсивно.

23treedel1.png 23treedel2.png 23treedel5.png

3) Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключами.

23treedel3.png 23treedel4.png 23treedel6.png

Слияние двух деревьев

Возможно два варианта слияния двух деревьев.

1) Если два дерева одной высоты, то слияние представляет собой добавление общей вершины.

23treemerge1.png 23treemerge2.png

2) Если два дерева разной высоты, то при слиянии меньшее добавляем как поддерево к одной из вершин большего.Если возникает ситуация,когда у необходимого узла уже есть три ребенка, то делим его на два узла с двумя поддеревьями и проверяем родителя.Таким образом проходим по дереву вверх до полной сбалансировки.

23treemerge3.png 23treemerge4.png

Cсылки

См. также