stringtranslate.com

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. [1] Los nodos en el exterior del árbol ( nodos hoja ) no tienen hijos y tienen uno o dos elementos de datos. [2] [3] John Hopcroft inventó 2 o 3 árboles en 1970. [4]

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 de 2 nodos si tiene un elemento de datos y dos hijos.

Decimos que un nodo interno es de 3 nodos 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.

Decimos que T es un árbol 2-3 si y sólo si se cumple una de las siguientes afirmaciones: [5]

Propiedades

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. Sea T un árbol 2-3 y d sea el elemento de datos que queremos encontrar. Si T está vacío, entonces d no está en T y terminamos.
  2. Sea t la raíz de T.
  3. Supongamos 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.
  4. Supongamos que t es un nodo de 2 con hijo izquierdo p y 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 listo.
    • Si es así , establezca T en p , que por definición es un árbol 2-3, y vuelva al paso 2.
    • Si es así , establezca T en q y vuelva al paso 2.
  5. Supongamos que t es un nodo de 3 con el hijo izquierdo p , el hijo del medio q y el hijo derecho r . Sean a y b los dos elementos de datos de t , donde . Hay cuatro casos:
    • Si d es igual a aob , entonces d está en T y listo.
    • Si es , entonces configure T en p y regrese al paso 2.
    • Si es así , establezca T en q y vuelva al paso 2.
    • Si es , entonces configure T en r y regrese al paso 2.

Inserción

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

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

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

Inserción de un número en un árbol 2-3 para 3 casos posibles

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.

Supresión

Se puede eliminar una clave de un nodo que no es hoja reemplazándola por su predecesor o sucesor inmediato y luego eliminando el predecesor o sucesor de un nodo hoja. Eliminar una clave de un nodo hoja es fácil si la hoja tiene 3 nodos. De lo contrario, puede ser necesario crear un nodo 1 temporal que puede absorberse reorganizando el árbol, o puede viajar repetidamente hacia arriba antes de poder ser absorbido, como lo haría un nodo 4 temporal en el caso de la inserción. Alternativamente, es posible utilizar un algoritmo que sea tanto de arriba hacia abajo como de abajo hacia arriba, creando 4 nodos temporales en el camino hacia abajo que luego se destruyen a medida que regresa. Los métodos de eliminación se explican con más detalle en las referencias. [5] [6]

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.

Ver también

Referencias

  1. ^ Knuth, Donald M (1998). "6.2.4". El arte de la programación informática . vol. 3 (2 ed.). Addison Wesley. ISBN 978-0-201-89685-5. Los 2 o 3 árboles definidos al final de la Sección 6.2.3 son equivalentes a árboles B de orden 3.
  2. ^ R. Hernández; JC Lázaro; R. Dormido; S. Ros (2001). Estructura de Datos y Algoritmos . Prentice Hall. ISBN 84-205-2980-X.
  3. ^ Ah, 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
  4. ^ Cormen, Thomas (2009). Introducción a los algoritmos . Londres: The MIT Press. págs.504. ISBN 978-0-262-03384-8.
  5. ^ a b C Sedgewick, Robert; Wayne, Kevin. "3.3". Algoritmos (4 ed.). Addison Wesley. ISBN 978-0-321-57351-3.
  6. ^ "2-3 árboles", Lyn Turbak, folleto n.º 26, notas del curso, CS230 Data Structures, Wellesley College, 2 de diciembre de 2004. Consultado el 11 de marzo de 2024.

enlaces externos