What is the name of this tree?

I'm searching for the name of this simple tree, that is a pretty straightforward generalization of a binary search tree.

This is the description. Every node of the tree has a fixed number of max keys MI and a minimal number of keys of just 1. Keys are ordered. Every node has MI+1 external links to childs, more or less like a b-tree. Child nodes only contain keys in the interval of the parent's two near keys, again, like a b-tree.

What is different is how insertion and deletion works.

INSERTION:

We start from the root.

If there is space in the node we are checking, since it does not have MI keys, so it is not full, we add our key in the right position.

If the node is full, we check in the child. If there is no child for this range, we create one with just our key. And so forth.

DELETION:

On deletion, if I had for instance "A C E" in a node, and I need to delete "E", but in the interval between "C" and "E" there is a child, I get the greatest element of the child and substitute it to "E" (I may 开发者_高级运维need to recurse here since removing the element may in turn need moving another element from the child to the parent). It's a bit more complex than this but in general there is to move an element from the child to the node that owned the deleted key.

I understand this is very informally specified but I was not able to find the name of what appears to be a trivial generalization of a binary tree.

I think your algorithm is for non-self-balancing "multi-way tree". Look here.

B-trees are consequently one self-balancing variant. The terminology is not exactly consistent. The sense in which Wikipedia uses the same name is different (equivalent to multi-ary), but I have seen the above interpretation in sufficiently many places to use it.

Maybe it's the k-ary tree.