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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
''' 2-3 дерево ''' — структура данных являющаяся [[B-дерево|B-деревом]] cтепени 1, каждая вершина которого может содержать двух или трех потомков.  
+
''' 2-3 дерево ''' — структура данных, предложенная в 1970 году Джоном Хопкрофтом,и представляющая собой [[B-дерево|B-дерево]] cтепени 1, такое что из каждого узла может выходить две или три ветви; при этом требуется, чтобы все внешние узлы находились на одном уровне. Каждый внутренний узел содержит либо один, либо два ключа.
  
 
== Структура ==
 
== Структура ==
Строка 9: Строка 9:
 
* Все листовые вершины находятся на одном уровне (на нижнем уровне) и содержат 1 или 2 поля.
 
* Все листовые вершины находятся на одном уровне (на нижнем уровне) и содержат 1 или 2 поля.
 
* Все данные отсортированы
 
* Все данные отсортированы
 +
* 2-3 дерево - сливаемое дерево
  
 
== Операции ==
 
== Операции ==
* Добавление элемента:
+
* Вставка элемента:
 +
Есть два варианта вставки в 2-3 дерево.
 +
 
 +
Чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто вставить его как второй ключ.
 +
 
 +
Если же в узле уже содержатся два ключа, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к тому, что придется делить родительский узел. Если же родительский узел - корень дерева - разбиваем на два поддерева и добавляем вершину.
 +
 
 
* Удаление элемента:
 
* Удаление элемента:
 +
При удалении ключа из узла возникают три варианта.
 +
 +
Если до удаления ключа в узле содержалось три ключа, то после удаления ничего не меняется.
 +
Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключами.

Версия 06:32, 28 марта 2011

2-3 дерево — структура данных, предложенная в 1970 году Джоном Хопкрофтом,и представляющая собой B-дерево cтепени 1, такое что из каждого узла может выходить две или три ветви; при этом требуется, чтобы все внешние узлы находились на одном уровне. Каждый внутренний узел содержит либо один, либо два ключа.

Структура

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

Свойства

  • Все нелистовые вершины содержат одно поле и 2 поддерева или 2 поля и 3 поддерева.
  • Все листовые вершины находятся на одном уровне (на нижнем уровне) и содержат 1 или 2 поля.
  • Все данные отсортированы
  • 2-3 дерево - сливаемое дерево

Операции

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

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

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

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

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

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

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