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. [1] Los nodos en el exterior del árbol ( nodos de hojas ) no tienen hijos y tienen uno o dos elementos de datos. [2] [3] John Hopcroft inventó 2-3 árboles en 1970. [4]
2-3 árboles | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | árbol | ||||||||||||||||||||
Inventado | 1970 | ||||||||||||||||||||
Inventado por | John Hopcroft | ||||||||||||||||||||
Complejidad del tiempo en notación O grande | |||||||||||||||||||||
|
Se requieren 2-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 cantidad de datos o casi la misma.
Definiciones
Decimos que un nodo interno es un nodo de 2 si tiene un elemento de datos y dos hijos.
Decimos que un nodo interno es un nodo de 3 si tiene dos elementos de datos y tres hijos.
Se puede crear temporalmente un nodo de 4 , con tres elementos de datos, durante la manipulación del árbol, pero nunca se almacena de forma persistente en el árbol.
2 nodo
3 nodo
Decimos que T es un árbol 2-3 si y solo si se cumple una de las siguientes afirmaciones: [5]
- T está vacío. En otras palabras, T no tiene ningún nodo.
- T es un nodo de 2 con el elemento de datos a . Si T tiene el hijo izquierdo py el hijo derecho q , entonces
- p y q son 2-3 árboles de la misma altura ;
- a es mayor que cada elemento de p ; y
- a es menor que cada elemento de datos en q .
- T es un 3-nodo con elementos de datos una y b , donde un < b . Si T tiene el hijo izquierdo p , el hijo del medio q y el hijo derecho r , entonces
- p , q , y r son 2-3 árboles de la misma altura;
- a es mayor que cada elemento de datos en py menor que cada elemento de datos en q ; y
- b es mayor que cada elemento de datos en q y menor que cada elemento de datos en r .
Propiedades
- Cada nodo interno es de 2 o 3 nodos.
- Todas las hojas están al mismo nivel.
- Todos los datos se mantienen ordenados.
Operaciones
buscando
Buscar un elemento en un árbol 2-3 es similar a buscar un elemento en un árbol de búsqueda binaria . 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.
- Sea T un árbol 2-3 y d el elemento de datos que queremos encontrar. Si T está vacío, entonces d no está en T y hemos terminado.
- Vamos t ser la raíz de T .
- Suponga que t es una hoja.
- Si d no está en t , entonces D no está en T . De lo contrario, d está en T . No necesitamos más pasos y hemos terminado.
- Suponga que t es un nodo de 2 con el hijo izquierdo p y el hijo derecho q . Sea a el elemento de datos en t . Hay tres casos:
- Si d es igual a a , entonces hemos encontrado d en T y hemos terminado.
- Si , A continuación, establezca T a P , que por definición es un árbol 2-3, y volver al paso 2.
- Si , luego ajuste T en q y vuelva al paso 2.
- Suponga que t es un nodo de 3 con el hijo izquierdo p , el hijo del medio q y el hijo derecho r . Deje una y b sea los dos elementos de datos de t , donde. Hay cuatro casos:
- Si d es igual a una o b , entonces d es en T y hemos terminado.
- Si , A continuación, establezca T a P y volver al paso 2.
- Si , luego ajuste T en q y vuelva al paso 2.
- Si , A continuación, establezca T a r y volver al paso 2.
Inserción
La inserción mantiene la propiedad equilibrada del árbol. [5]
Para insertar en un 2-nodo, la nueva clave se agrega al 2-nodo en el orden apropiado.
Para insertarlo 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 3 cuyo padre es un nodo 2, la clave se inserta en el nodo 3 para crear un nodo 4 temporal. En la ilustración, la clave 10 se inserta en el 2-nodo con 6 y 9. La clave del medio es 9, y se promueve al 2-nodo principal. Esto deja un 3-nodo de 6 y 10, que se divide para ser dos 2 nodos mantenidos como hijos del 3-nodo principal.
Si el nodo de destino es un nodo de 3 y el padre es un nodo de 3, se crea un nodo temporal de 4 y luego se divide como se indicó anteriormente. Este proceso continúa subiendo por el árbol hasta la raíz. Si la raíz debe dividirse, 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-3 árboles son similares en estructura a los árboles rojo-negro , los algoritmos paralelos para árboles rojo-negro también se pueden aplicar a 2-3 árboles.
Ver también
Referencias
- ^ Knuth, Donald M (1998). "6.2.4". El arte de la programación informática . 3 (2 ed.). Addison Wesley. ISBN 9780201896855.
Los 2-3 árboles definidos al final de la Sección 6.2.3 son equivalentes a B-Trees de orden 3.
- ^ Gross, R. Hernández, JC Lázaro, R. Dormido, S. Ros (2001). Estructura de Datos y Algoritmos . Prentice Hall. ISBN 84-205-2980-X.
- ^ Aho, Alfred V .; Hopcroft, John E .; Ullman, Jeffrey D. (1974). El diseño y análisis de algoritmos informáticos . Addison-Wesley., págs. 145-147
- ^ Cormen, Thomas (2009). Introducción a los algoritmos . Londres: The MIT Press. págs. 504 . ISBN 978-0262033848.
- ^ a b Sedgewick, Robert; Wayne, Kevin. "3.3". Algoritmos (4 ed.). Addison Wesley. ISBN 9780321573513.