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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства)
Строка 13: Строка 13:
 
* 2-3 дерево - сливаемое дерево
 
* 2-3 дерево - сливаемое дерево
 
* Все пути от корня до любого листа имеют одинаковую длину
 
* Все пути от корня до любого листа имеют одинаковую длину
 +
* Высота 2-3 дерева лежит между <tex> \log_{2} n </tex> и <tex> \log_{2} n </tex>, где <tex> n </tex> - количество элементов в дереве.
 +
Поэтому операции над ним выполняются за время  <tex>O(\log{n})</tex>.
  
 
== Операции ==
 
== Операции ==

Версия 03:55, 29 марта 2011

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

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

Значения

Все данные хранятся в листьях, в вершинах хранится вспомогательная информация,необходимая для организации поиска по поддеревьям.Нелистовые вершины содержат 1 или 2 ключа, указывающие на диапазон значений в их поддеревьях.

Структура

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

Свойства

  • Все нелистовые вершины содержат один ключ и 2 поддерева или 2 ключа и 3 поддерева.
  • Все листовые вершины находятся на одном уровне (на нижнем уровне) и содержат 1 или 2 ключа.
  • Все данные отсортированы
  • 2-3 дерево - сливаемое дерево
  • Все пути от корня до любого листа имеют одинаковую длину
  • Высота 2-3 дерева лежит между [math] \log_{2} n [/math] и [math] \log_{2} n [/math], где [math] n [/math] - количество элементов в дереве.

Поэтому операции над ним выполняются за время [math]O(\log{n})[/math].

Операции

  • Поиск

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

  • Слияние двух деревьев (merge())

Т.к. вся информация в 2-3 деревьях хранится в листьях, а в вершинах хранится вспомогательная информация, то слияние двух деревьев представляет собой добавление общей вершины.

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

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

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

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

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

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

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