Otra posible concesión en vez de equilibrio perfecto es permitir almacenar más de un elemento en cada nodo.

En este caso es posible hacer que todos los subárboles estén perfectamente equilibrados.

Un árbol m-ario ó multicamino cumple:

1. Cada nodo tiene hasta m hijos y guarda hasta m-1 elementos (número de hijos <= (número de elementos +1)).
2. Los valores guardados en un nodo están en orden ascendente.
3. Los valores de los primeros i hijos de A son menores que el elemento  iésimo guardado en A.
4. Los valores de los últimos m-i hijos de A son mayores que el elemento  iésimo guardado en A..

La búsqueda es sencilla.

Un árbol m-ario equilibrado sencillo es el árbol 2-3:

• Es un árbol 3-ario con 0, 2 ó 3 hijos por nodo.
• Todas las hojas están al mismo nivel.

Como un árbol 2-3 de altura h tiene al menos tantos nodos como un árbol binario completo de altura h:

                N   >=  2h+1-1

                h   <=  ceiling(log_2 (N+1) -1)

Otro árbol m-ario equilibrado sencillo es el árbol  2-3-4 (4-ario, 0,2,3 ó 4 hijos por nodo, todas las hojas al mismo nivel):

Vamos a ver los 2-3-4 que son una buena introducción a los árboles B.

Arboles 2-3-4

La altura de un 2-3-4 de N nodos es como mucho la altura de un 2-3 de N nodos, luego

        h<=log(N+1)

        O(3 h) = O(3 log(N+1))=O(log N)

Inserción en un árbol 2-3-4

Los nuevos elementos se insertan siempre en las hojas.

Se atraviesa el árbol hacia abajo hasta encontrar la hoja donde insertar.

Dependiendo de si encontramos nodos llenos tenemos 3 casos:

1. inserción sin subdividir nodos
2. inserción subdividiendo nodos
3. inserción subdividiendo la raiz

Inserción sin subdividir nodos:

No encontramos nodos llenos en el camino de la raiz a la hoja:

Inserción subdividiendo nodos:

Cuando encontramos un nodo lleno en el camino de la raiz a la hoja:

Podemos necesitar varias divisiones si nos encontramos con más de un nodo lleno en el camino de la raiz a la hoja.

El proceso de subdivisión mantiene el árbol equilibrado.

Inserción subdividiendo la raiz:

Esto ocurre cuando nos encontramos la raiz llena. Dividimos la raiz (cuatro hijos) en 3 nodos de dos hijos cada uno.

Ejemplo: Generar un árbol 2-3-4 con la secuencia:

         70, 50, 30, 40, 20, 80, 25, 90, 75, 10

Se puede demostrar que la estructura y las operaciones que se aplican a un árbol 2-3-4 son equivalentes a las de un árbol rojo-negro.