144
правки
Изменения
Нет описания правки
== Операции ==
* === ''' Поиск ==='''
Для поиска в 2-3 дереве необходимо последовательно просматривать ключи,
хранящиеся во внутренних ячейках, спускаясь от корня к листьям. Вначале ключ искомого
в среднее поддерево, а если превосходит, то идем в правое поддерево.
* === ''' Слияние двух деревьев (merge()) ==='''
Т.к. вся информация в 2-3 деревьях хранится в листьях, а в вершинах хранится вспомогательная информация, то слияние двух деревьев представляет собой добавление общей вершины.
* === ''' Вставка элемента === '''
Есть два варианта вставки в 2-3 дерево.
Если же в узле уже содержатся два ключа, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к тому, что придется делить родительский узел. Если же родительский узел - корень дерева - разбиваем на два поддерева и добавляем вершину.
* === ''' Удаление элемента ==='''
При удалении ключа из узла возникают три варианта.
Если до удаления ключа в узле содержалось три ключа, то после удаления ничего не меняется.
Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключами.
