algorithm - trees - ¿Cuál es el nombre de este árbol?

trees data structure

Question

Estoy buscando el nombre de este árbol simple, que es una generalización bastante sencilla de un árbol de búsqueda binario.

Esta es la descripción. Cada nodo del árbol tiene un número fijo de teclas máximas MI y un número mínimo de teclas de solo 1. Las claves se ordenan. Cada nodo tiene MI + 1 enlaces externos a los niños, más o menos como un b-tree. Los nodos secundarios solo contienen claves en el intervalo de las dos teclas cercanas de los padres, una vez más, como un b-tree.

Lo que es diferente es cómo funciona la inserción y eliminación.

INSERCIÓN:

Comenzamos desde la raíz.

Si hay espacio en el nodo que estamos verificando, ya que no tiene teclas MI, entonces no está lleno, agregamos nuestra clave en la posición correcta.

Si el nodo está lleno, registramos el niño. Si no hay un niño para este rango, creamos uno solo con nuestra clave. Etcétera.

SUPRESIÓN:

En la eliminación, si tenía por ejemplo "ACE" en un nodo, y tengo que eliminar "E", pero en el intervalo entre "C" y "E" hay un niño, obtengo el elemento más grande del niño y sustitúyalo por "E" (es posible que necesite recurrir aquí ya que la eliminación del elemento puede a su vez necesitar mover otro elemento desde el hijo al padre). Es un poco más complejo que esto, pero en general hay que mover un elemento del niño al nodo que posee la clave eliminada.

Entiendo que esto está muy informalmente especificado, pero no pude encontrar el nombre de lo que parece ser una generalización trivial de un árbol binario.

Answer 1

Tal vez sea el árbol kary .

Answer 2

Creo que su algoritmo es para "árbol multidireccional" que no se equilibra a sí mismo. Mira aquí .

B-trees son consecuentemente una variante de auto-equilibrio. La terminología no es exactamente consistente. El sentido en el que Wikipedia usa el mismo nombre es diferente (equivalente a multi-aria), pero he visto la interpretación anterior en suficientes lugares para usarla.