Я ищу имя этого простого дерева, то есть довольно простое обобщение двоичного дерева поиска.Как называется это дерево?
Это описание. Каждый узел дерева имеет фиксированное количество максимальных ключей MI и минимальное количество ключей всего 1. Ключи упорядочены. Каждый узел имеет MI + 1 внешние ссылки на дочерние элементы, более или менее похожие на b-дерево. У дочерних узлов только ключи находятся в интервале двух ближайших ключей родителя, опять же, как b-tree.
В чем отличие работы вставки и удаления.
ВСТАВКИ:
Мы начинаем с корня.
Если в узле мы проверяем пробел, так как в нем нет ключей MI, поэтому он не заполнен, мы добавляем наш ключ в нужное положение.
Если узел заполнен, мы проверяем его. Если для этого диапазона нет дочернего элемента, мы создаем его только с нашим ключом. И так далее.
УДАЛЕНИЕ:
на удаление, если бы я был, например, «ACE» в узле, и мне нужно удалить «E», но в промежутке между «С» и «Е» есть ребенок , Я получаю наибольший элемент дочернего элемента и заменяю его на «E» (мне, возможно, придется рекурсивно здесь, так как удаление элемента может в свою очередь необходимо переместить другой элемент из дочернего элемента в родительский). Это немного сложнее, чем это, но в общем случае нужно переместить элемент из дочернего узла в узел, которому принадлежит удаленный ключ.
Я понимаю, что это очень неформально указано, но я не смог найти имя того, что кажется тривиальным обобщением двоичного дерева.
Вы говорите, что узел может иметь ключи MI, но затем вы указываете «ребенок» в вставке. Просьба уточнить, как ребенок выбран в качестве его важной информации. – marcog
@margoc: Думаю, я упомянул, что если текущий узел заполнен, мы перейдем к дочернему элементу, который связан в диапазоне, который ограничен двумя уже имеющимися ключами. Поэтому, если MI равно 4, и я имею в корневом узле «A C M Z», и я должен добавить «E», я создаю попытку перейти к дочернему элементу, связанному в диапазоне A-C. Если его нет, я его создаю. – antirez