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