What is the name of this tree?

Question

I am looking for the name of this simple tree, this is a fairly simple generalization of the binary search tree.

This is a description. Each tree node has a fixed number of maximum MI keys and a minimum number of keys of only 1. The keys are ordered. Each node has MI + 1 external links to child elements, more or less similar to a b-tree. The child nodes only have keys in the range of the parent two close keys, again, like a b-tree.

What is the difference between the work of insertion and deletion.

INSERTS:

We start from the root.

If there is a space in the node, we check, since it does not have MI keys, so it is not filled, we add our key to the correct position.

If the node is populated, we check it. If there is no child for this range, we only create it with our key. And so on.

REMOVAL:

When deleting, if I had “ACE” in node and I need to delete “E”, but there is a child between “C” and “E”, I get the largest element of the child and replace it with “E” ( I may need to review here, since deleting an element may, in turn, need to move another element from a child to a parent). This is a little more complicated than that, but in general, you need to move an element from a child to the node that owns the remote key.

I understand that this is very informally stated, but I could not find the name of what seems to be a trivial generalization of the binary tree.

Answer 1

I think your algorithm is for a non-automatic "multi-track tree". Take a look here .

B-trees are therefore one option for self-balancing. The terminology is not entirely consistent. The meaning in which Wikipedia uses the same name is different (equivalent to multi-rai), but I saw the above interpretation in enough places to use it.

Answer 2

Perhaps this is a k-ary tree .