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