2-3 árboles

En informática, un árbol 2–3 es una estructura de datos de árbol, donde cada nodo con hijos (nodo interno) tiene dos hijos (2 nodos) y un elemento de datos o tres hijos. (3 nodos) y dos elementos de datos. Un árbol 2-3 es un árbol B de orden 3. Los nodos en el exterior del árbol (nodos hoja) no tienen hijos y tienen uno o dos elementos de datos. John Hopcroft inventó entre 2 y 3 árboles en 1970.

Se requieren 2 o 3 árboles para estar equilibrados, lo que significa que cada hoja está al mismo nivel. De ello se deduce que cada subárbol derecho, central e izquierdo de un nodo contiene la misma o casi la misma cantidad de datos.

Definiciones

Decimos que un nodo interno es un 2 nodos si tiene un elemento de datos y dos hijos.

Decimos que un nodo interno es un 3 nodos si tiene dos elementos de datos y tres hijos.

Se puede crear temporalmente un 4 nodos, con tres elementos de datos, durante la manipulación del árbol, pero nunca se almacena de forma persistente en el árbol.

• 

  2 nodos

• 

  3 nodos

Decimos que T es un árbol 2–3 si y sólo si uno de los se mantienen las siguientes afirmaciones:

• T está vacío. En otras palabras, T no tiene nodos.
• T es un 2-nodo con elemento de datos a. Si T ha dejado a un niño p y el niño derecho q, entonces
  • p y q son 2-3 árboles de la misma altura;
  • a es mayor que cada elemento en p; y
  • a es menos que cada elemento de datos en q.
• T es un 3-nodo con elementos de datos a y b, donde a . b. Si T ha dejado a un niño p, niño medio q, y niño derecho r, entonces
  • p, q, y r son 2-3 árboles de igual altura;
  • a es mayor que cada elemento de datos en p y menos que cada elemento de datos q; y
  • b es mayor que cada elemento de datos en q y menos que cada elemento de datos r.

Propiedades

• Cada nodo interno es de 2 nudos o de 3 nudos.
• Todas las hojas están al mismo nivel.
• Todos los datos se guardan en orden ordenado.

Operaciones

Buscando

Buscar un elemento en un árbol 2 o 3 es similar a buscar un elemento en un árbol de búsqueda binario. Dado que los elementos de datos en cada nodo están ordenados, se dirigirá una función de búsqueda al subárbol correcto y, finalmente, al nodo correcto que contiene el elemento.

1. Vamos T ser un árbol 2-3 y d ser el elemento de datos que queremos encontrar. Si T está vacío, entonces d no está T y hemos terminado.
2. Vamos t ser la raíz de T.
3. Suppose t es una hoja.
   • Si d no está t, entonces d no está T. De lo contrario, d está dentro T. No necesitamos más pasos y hemos terminado.
4. Suppose t es un 2-nodo con el niño izquierdo p y el niño derecho q. Vamos a ser el elemento de datos en t. Hay tres casos:
   • Si d es igual a a, entonces hemos encontrado d dentro T y hemos terminado.
   • Si ${displaystyle d wona}$, entonces listo T a p, que por definición es un árbol 2-3, y volver al paso 2.
   • Si ${displaystyle d espíritua}$, entonces listo T a q y volver al paso 2.
5. Suppose t es un 3-nodo con niño izquierdo p, niño medio q, y niño derecho r. Vamos a y b ser los dos elementos de datos t, donde ${displaystyle a meantb}$. Hay cuatro casos:
   • Si d es igual a a o b, entonces d está dentro T y hemos terminado.
   • Si ${displaystyle d wona}$, entonces listo T a p y volver al paso 2.
   • Si ${displaystyle accionado$, entonces listo T a q y volver al paso 2.
   • Si ${displaystyle d espíritub}$, entonces listo T a r y volver al paso 2.

Inserción

La inserción mantiene la propiedad equilibrada del árbol.

Para insertar en un nodo de 2, la nueva clave se agrega al nodo de 2 en el orden apropiado.

Para insertar en un nodo de 3, es posible que se requiera más trabajo dependiendo de la ubicación del nodo de 3. Si el árbol consta solo de 3 nodos, el nodo se divide en tres 2 nodos con las claves y los hijos apropiados.

Si el nodo de destino es un nodo de 3 cuyo padre es un nodo de 2, la clave se inserta en el nodo de 3 para crear un nodo de 4 temporal. En la ilustración, la clave 10 se inserta en el nodo 2 con 6 y 9. La clave del medio es 9 y se promueve al nodo 2 principal. Esto deja un nodo de 3 de 6 y 10, que se divide en dos nodos de 2 que se mantienen como hijos del nodo de 3 padre.

Si el nodo de destino es de 3 nodos y el padre es de 3 nodos, se crea un nodo temporal de 4 y luego se divide como se indica arriba. Este proceso continúa por el árbol hasta la raíz. Si la raíz debe dividirse, entonces se sigue el proceso de un solo 3 nodos: una raíz temporal de 4 nodos se divide en tres 2 nodos, uno de los cuales se considera la raíz. Esta operación aumenta la altura del árbol en uno.

Operaciones paralelas

Dado que 2 o 3 árboles tienen una estructura similar a los árboles rojo-negro, también se pueden aplicar algoritmos paralelos para árboles rojo-negro a 2 o 3 árboles.