B-Tree - ¿Por qué no puede haber un nodo con un número par de llaves?

Question

Estoy tratando de implementar un árbol B de acuerdo con el capítulo "B-Trees" en "Introducción a los algoritmos".

Lo que no acabo de recibo es el "grado mínimo". En el libro se afirma que el grado es un número que expresa la parte inferior / límite superior para el número de teclas de un nodo puede contener . Se dice además que:

1. Cada nodo almacena no root al menos teclas t - 1 y tiene hijos t .
2. Cada nodo almacena en la mayoría de las teclas 2*t - 1 y tiene hijos 2*t .

Para que pueda obtener para t = 2:

1. t - 1 = 1 llaves y t = 2 niños
2. 2*t - 1 = 3 llaves y 4 niños

Para t = 3

1. t - 1 = 2 llaves y t = 3 niños
2. 2*t - 1 = 5 teclas y 6 niños

Ahora aquí está el problema: Parece que los nodos en un árbol B sólo puede almacenar un extraña número de teclas cuando están llenos.

¿Por qué no puede haber un nodo con, digamos que a lo sumo 4 teclas y 5 niños? ¿Tiene algo que ver con la división del nodo?

Answer 1

  

Parece que los nodos en un árbol B sólo puede almacenar un número impar de llaves?

Definitivamente no. Los números que ha escrito es mínimo y el máximo número de teclas ofof respectivamente, por lo que para t = 2, con nodos 1, 2, 3 teclas están permitidos. Para t = 3, los nodos con 2, 3, 4, se permite 5 teclas.

Además, se permite la raíz del árbol de tener sólo 1 llave.

Es posible definir (e implementar) árboles que tienen por ejemplo. 1 o 2 llaves en un nodo (los llamados árboles 2-3). Los árboles B se definen razón para dar cabida a una más, es que esto da lugar a un rendimiento más rápido. En particular, esto permite O(1) amortizado (división recuento y operaciones de unión) borrar e insertar las operaciones.

Answer 2

que no es imposible, pero subóptima. ¿cómo dividir un nodo con un número impar de los niños?