stringtranslate.com

Árbol binario

Un árbol binario etiquetado de tamaño 9 y altura 3, con un nodo raíz cuyo valor es 1. El árbol anterior no está equilibrado y no está ordenado.
Un árbol binario etiquetado de tamaño 9 (la cantidad de nodos del árbol) y altura 3 (la altura de un árbol definida como la cantidad de aristas o enlaces desde el nodo superior o raíz hasta el nodo hoja más alejado), con un nodo raíz cuyo valor es 1. El árbol anterior no está equilibrado y no está ordenado.

En informática , un árbol binario es una estructura de datos en forma de árbol en la que cada nodo tiene como máximo dos hijos , denominados hijo izquierdo e hijo derecho . Es decir, es un árbol k -ario con k = 2. Una definición recursiva que utiliza la teoría de conjuntos es que un árbol binario es una tupla ( L , S , R ), donde L y R son árboles binarios o el conjunto vacío y S es un conjunto singleton que contiene la raíz. [1] [2]

Desde una perspectiva de teoría de grafos , los árboles binarios como se definen aquí son arborescencias . [3] Por lo tanto, un árbol binario también puede llamarse arborescencia bifurcada , [3] un término que aparece en algunos libros de programación tempranos [4] antes de que prevaleciera la terminología de la informática moderna. También es posible interpretar un árbol binario como un grafo no dirigido , en lugar de dirigido , en cuyo caso un árbol binario es un árbol ordenado y con raíz . [5] Algunos autores usan árbol binario con raíz en lugar de árbol binario para enfatizar el hecho de que el árbol tiene raíz, pero como se definió anteriormente, un árbol binario siempre tiene raíz. [6]

En matemáticas, lo que se denomina árbol binario puede variar significativamente de un autor a otro. Algunos utilizan la definición que se utiliza habitualmente en informática [7] , pero otros lo definen como todo árbol que no sea una hoja y que tenga exactamente dos hijos, y no necesariamente los etiquetan como izquierdo y derecho [8] .

En informática, los árboles binarios se pueden utilizar de dos maneras muy diferentes:

Definiciones

Definición recursiva

Para definir un árbol binario, se debe reconocer la posibilidad de que sólo uno de los hijos esté vacío. Para ello se necesita un artefacto , que en algunos libros de texto se denomina árbol binario extendido . Por tanto, un árbol binario extendido se define recursivamente como: [11]

Otra forma de imaginar esta construcción (y entender la terminología) es considerar en lugar del conjunto vacío un tipo diferente de nodo: por ejemplo, nodos cuadrados si los regulares son círculos. [12]

Utilizando conceptos de teoría de grafos

Un árbol binario es un árbol con raíz que también es un árbol ordenado (también conocido como árbol plano) en el que cada nodo tiene como máximo dos hijos. Un árbol con raíz naturalmente imparte una noción de niveles (distancia desde la raíz); por lo tanto, para cada nodo, se puede definir una noción de hijos como los nodos conectados a él un nivel inferior. El ordenamiento de estos hijos (por ejemplo, dibujándolos en un plano) permite distinguir un hijo izquierdo de un hijo derecho. [13] Pero esto todavía no distingue entre un nodo con un hijo izquierdo pero no derecho de un nodo con un hijo derecho pero no izquierdo.

La distinción necesaria se puede hacer primero dividiendo los bordes; es decir, definiendo el árbol binario como triplete (V, E 1 , E 2 ), donde (V, E 1 ∪ E 2 ) es un árbol con raíz (equivalentemente arborescencia) y E 1 ∩ E 2 está vacío, y también requiriendo que para todo j ∈ { 1, 2 }, cada nodo tenga como máximo un hijo E j . [14] Una forma más informal de hacer la distinción es decir, citando la Enciclopedia de Matemáticas , que "cada nodo tiene un hijo izquierdo, un hijo derecho, ninguno, o ambos" y especificar que estos "son todos árboles binarios diferentes". [7]

Tipos de árboles binarios

La terminología de los árboles no está bien estandarizada y por eso varía en la literatura.

Un árbol binario completo
Un cuadro de ascendencia que puede representarse en un árbol binario perfecto de cuatro niveles.
Un árbol binario completo (que no está lleno)

Propiedades de los árboles binarios

Combinatoria

En combinatoria , se considera el problema de contar el número de árboles binarios completos de un tamaño dado. Aquí los árboles no tienen valores asociados a sus nodos (esto simplemente multiplicaría el número de árboles posibles por un factor fácilmente determinable), y los árboles se distinguen solo por su estructura; sin embargo, se distinguen el hijo izquierdo y derecho de cualquier nodo (si son árboles diferentes, entonces intercambiarlos producirá un árbol distinto del original). El tamaño del árbol se toma como el número n de nodos internos (aquellos con dos hijos); los otros nodos son nodos hoja y hay n + 1 de ellos. El número de tales árboles binarios de tamaño n es igual al número de formas de poner entre paréntesis una cadena de n + 1 símbolos (que representan hojas) separados por n operadores binarios (que representan nodos internos), para determinar las subexpresiones de argumento de cada operador. Por ejemplo, para n = 3, uno tiene que poner entre paréntesis una cadena como ⁠ ⁠ , lo cual es posible de cinco formas:

La correspondencia con árboles binarios debería ser obvia, y no se permite (o al menos no se cuenta como producción de una nueva posibilidad) la adición de paréntesis redundantes (alrededor de una expresión ya entre paréntesis o alrededor de la expresión completa).

Existe un único árbol binario de tamaño 0 (que consta de una sola hoja), y cualquier otro árbol binario se caracteriza por el par de sus hijos izquierdo y derecho; si estos tienen tamaños i y j respectivamente, el árbol completo tiene tamaño i + j + 1 . Por lo tanto, el número de árboles binarios de tamaño n tiene la siguiente descripción recursiva , y para cualquier entero positivo n . Se deduce que es el número Catalan de índice n .

Las cadenas entre paréntesis anteriores no deben confundirse con el conjunto de palabras de longitud 2 n en el lenguaje Dyck , que consisten únicamente en paréntesis de tal manera que están correctamente balanceados. El número de tales cadenas satisface la misma descripción recursiva (cada palabra Dyck de longitud 2 n está determinada por la subpalabra Dyck encerrada por el '(' inicial y su ')' correspondiente junto con la subpalabra Dyck que queda después de ese paréntesis de cierre, cuyas longitudes 2 i y 2 j satisfacen i + j + 1 = n ); este número es, por lo tanto, también el número catalán . Por lo tanto, también hay cinco palabras Dyck de longitud 6:

()()(), ()(()), (())(), (()()), ((()))

Estas palabras de Dyck no corresponden a los árboles binarios de la misma manera. En cambio, están relacionadas por la siguiente biyección definida recursivamente: la palabra de Dyck igual a la cadena vacía corresponde al árbol binario de tamaño 0 con una sola hoja. Cualquier otra palabra de Dyck se puede escribir como ( ) , donde , son en sí mismas palabras de Dyck (posiblemente vacías) y donde los dos paréntesis escritos coinciden. La biyección se define entonces dejando que las palabras y correspondan a los árboles binarios que son los hijos izquierdo y derecho de la raíz.

Una correspondencia biyectiva también se puede definir de la siguiente manera: encierre la palabra Dyck en un par de paréntesis adicional, de modo que el resultado pueda interpretarse como una expresión de lista Lisp (con la lista vacía () como el único átomo que aparece); entonces la expresión de par de puntos para esa lista propia es una expresión completamente entre paréntesis (con NIL como símbolo y '.' como operador) que describe el árbol binario correspondiente (que es, de hecho, la representación interna de la lista propia).

La capacidad de representar árboles binarios como cadenas de símbolos y paréntesis implica que los árboles binarios pueden representar los elementos de un magma libre en un conjunto singleton.

Métodos para almacenar árboles binarios

Los árboles binarios se pueden construir a partir de primitivos del lenguaje de programación de varias maneras.

Nodos y referencias

En un lenguaje con registros y referencias , los árboles binarios se construyen normalmente con una estructura de nodos de árbol que contiene algunos datos y referencias a sus hijos izquierdo y derecho. A veces, también contiene una referencia a su padre único. Si un nodo tiene menos de dos hijos, algunos de los punteros de los hijos pueden configurarse en un valor nulo especial o en un nodo centinela especial .

Este método de almacenar árboles binarios desperdicia una buena cantidad de memoria, ya que los punteros serán nulos (o apuntarán al centinela) más de la mitad del tiempo; una alternativa de representación más conservadora es el árbol binario enhebrado . [26]

En lenguajes con uniones etiquetadas como ML , un nodo de árbol es a menudo una unión etiquetada de dos tipos de nodos, uno de los cuales es una tupla de 3 datos, hijo izquierdo y hijo derecho, y el otro es un nodo "hoja", que no contiene datos y funciona de forma muy similar al valor nulo en un lenguaje con punteros. Por ejemplo, la siguiente línea de código en OCaml (un dialecto ML) define un árbol binario que almacena un carácter en cada nodo. [27]

tipo  chr_tree  =  Vacío  |  Nodo  de  char  *  chr_tree  *  chr_tree

Matrices

Los árboles binarios también se pueden almacenar en orden de amplitud como una estructura de datos implícita en matrices y, si el árbol es un árbol binario completo, este método no desperdicia espacio. En esta disposición compacta, si un nodo tiene un índice i , sus hijos se encuentran en los índices (para el hijo izquierdo) y (para el derecho), mientras que su padre (si lo hay) se encuentra en el índice (asumiendo que la raíz tiene índice cero). Alternativamente, con una matriz indexada en 1, la implementación se simplifica con los hijos encontrados en y y el padre encontrado en . [28]

Este método se beneficia de un almacenamiento más compacto y una mejor localidad de referencia , particularmente durante un recorrido de preorden. Se utiliza a menudo para montículos binarios . [29]

Un pequeño árbol binario completo almacenado en una matriz
Un pequeño árbol binario completo almacenado en una matriz

Codificaciones

Codificaciones sucintas

Una estructura de datos sucinta es aquella que ocupa cerca del mínimo espacio posible, como lo establecen los límites inferiores de la teoría de la información . El número de árboles binarios diferentes en los nodos es , el ésimo número de Catalan (suponiendo que consideramos a los árboles con estructura idéntica como idénticos). Para , esto es aproximadamente ; por lo tanto, necesitamos al menos aproximadamente bits para codificarlo. Por lo tanto, un árbol binario sucinto ocuparía bits.

Una representación sencilla que cumple con este límite es visitar los nodos del árbol en preorden, generando como salida "1" para un nodo interno y "0" para una hoja. [30] Si el árbol contiene datos, podemos simplemente almacenarlos simultáneamente en una matriz consecutiva en preorden. Esta función logra esto:

función EncodeSuccinct( nodo n, estructura de cadena de bits , datos de matriz ) { si n = nulo  entonces añadir 0 a la estructura; demás apéndice 1 a la estructura; añadir n.data a datos; EncodeSuccinct(n.left, estructura, datos); EncodeSuccinct(n.right, estructura, datos);}

La estructura de cadena solo tiene bits al final, donde es el número de nodos (internos); ni siquiera tenemos que almacenar su longitud. Para demostrar que no se pierde información, podemos convertir la salida de nuevo al árbol original de la siguiente manera:

función DecodeSuccinct( estructura de cadena de bits , datos de matriz ) { eliminar el primer bit de la estructura y colocarlo en b  si b = 1 entonces crear un nuevo nodo n eliminar el primer elemento de datos y colocarlo en n.data n.left = DecodeSuccinct(estructura, datos) n.right = DecodeSuccinct(estructura, datos) devuelve n en caso contrario  devuelve nil}

Las representaciones sucintas más sofisticadas permiten no sólo el almacenamiento compacto de árboles sino incluso realizar operaciones útiles sobre esos árboles directamente mientras aún están en su forma sucinta.

Codificación de árboles ordenados como árboles binarios

Existe una correspondencia natural biunívoca entre árboles ordenados y árboles binarios. Permite que cualquier árbol ordenado se represente de forma única como un árbol binario y viceversa:

Sea T un nodo de un árbol ordenado y sea B la imagen de T en el árbol binario correspondiente. Entonces, el hijo izquierdo de B representa al primer hijo de T , mientras que el hijo derecho de B representa al siguiente hermano de T.

Por ejemplo, el árbol ordenado de la izquierda y el árbol binario de la derecha corresponden:

Un ejemplo de conversión de un árbol n-ario a un árbol binario
Un ejemplo de conversión de un árbol n-ario a un árbol binario

En el árbol binario ilustrado, los bordes negros de la izquierda representan al primer hijo , mientras que los bordes azules de la derecha representan al siguiente hermano .

Esta representación se llama árbol binario de hijo izquierdo y hermano derecho .

Operaciones comunes

Las rotaciones de árboles son operaciones internas muy comunes en árboles binarios autoequilibrados .

Existe una variedad de operaciones diferentes que se pueden realizar en árboles binarios. Algunas son operaciones de mutación , mientras que otras simplemente devuelven información útil sobre el árbol.

Inserción

Los nodos se pueden insertar en árboles binarios entre otros dos nodos o se pueden agregar después de un nodo hoja . En los árboles binarios, se especifica de qué nodo se trata cuando se inserta.

Nodos de hojas

Para agregar un nuevo nodo después del nodo hoja A, A asigna el nuevo nodo como uno de sus hijos y el nuevo nodo asigna al nodo A como su padre.

Nodos internos

El proceso de inserción de un nodo en un árbol binario

La inserción en nodos internos es ligeramente más compleja que en nodos hoja. Digamos que el nodo interno es el nodo A y que el nodo B es el hijo de A. (Si la inserción es para insertar un hijo derecho, entonces B es el hijo derecho de A, y lo mismo con una inserción de hijo izquierdo). A asigna su hijo al nuevo nodo y el nuevo nodo asigna su padre a A. Luego, el nuevo nodo asigna su hijo a B y B asigna su padre como el nuevo nodo.

Supresión

La eliminación es el proceso por el cual se elimina un nodo del árbol. Solo ciertos nodos de un árbol binario pueden eliminarse sin ambigüedades. [31]

Nodo con cero o un hijo

El proceso de eliminar un nodo interno en un árbol binario

Supongamos que el nodo a eliminar es el nodo A. Si A no tiene hijos, la eliminación se logra estableciendo el hijo del padre de A en null . Si A tiene un hijo, establezca el padre del hijo de A en el padre de A y establezca el hijo del padre de A en el hijo de A.

Nodo con dos hijos

En un árbol binario, un nodo con dos hijos no se puede eliminar de forma inequívoca. [31] Sin embargo, en ciertos árboles binarios (incluidos los árboles binarios de búsqueda ) estos nodos se pueden eliminar, aunque con una reorganización de la estructura del árbol.

Travesía

Los recorridos en preorden, en orden y posorden visitan cada nodo de un árbol visitando recursivamente cada nodo en los subárboles izquierdo y derecho de la raíz. A continuación se presentan breves descripciones de los recorridos mencionados anteriormente.

Hacer un pedido

En el orden previo, siempre visitamos el nodo actual; luego, recorremos recursivamente el subárbol izquierdo del nodo actual y, luego, recorremos recursivamente el subárbol derecho del nodo actual. El recorrido en orden previo está ordenado topológicamente , porque se procesa un nodo principal antes de que se procese cualquiera de sus nodos secundarios.

En orden

En orden, siempre recorrimos recursivamente el subárbol izquierdo del nodo actual; luego, visitamos el nodo actual y, por último, recorrimos recursivamente el subárbol derecho del nodo actual.

Post-orden

En el orden posterior, siempre recorremos recursivamente el subárbol izquierdo del nodo actual; luego, recorremos recursivamente el subárbol derecho del nodo actual y luego visitamos el nodo actual. El recorrido en orden posterior puede ser útil para obtener la expresión posfija de un árbol de expresión binaria . [32]

Orden de profundidad primero

En el orden de profundidad, siempre intentamos visitar el nodo más alejado del nodo raíz que podamos, pero con la salvedad de que debe ser un nodo secundario de un nodo que ya hayamos visitado. A diferencia de una búsqueda en profundidad en grafos, no es necesario recordar todos los nodos que hemos visitado, porque un árbol no puede contener ciclos. El orden previo es un caso especial de esto. Consulte la búsqueda en profundidad para obtener más información.

Orden de amplitud primero

En contraste con el orden de profundidad, se encuentra el orden de amplitud, que siempre intenta visitar el nodo más cercano a la raíz que aún no haya visitado. Consulte la búsqueda de amplitud para obtener más información. También se denomina recorrido de orden de nivel .

En un árbol binario completo, el índice de amplitud de un nodo ( i − (2 d − 1)) se puede utilizar como instrucciones de recorrido desde la raíz. Se lee bit a bit de izquierda a derecha, comenzando en el bit d − 1, donde d es la distancia del nodo desde la raíz ( d = ⌊log 2 ( i +1)⌋) y el nodo en cuestión no es la raíz en sí ( d > 0). Cuando el índice de amplitud está enmascarado en el bit d − 1, los valores de bit 0 y 1 significan avanzar hacia la izquierda o hacia la derecha, respectivamente. El proceso continúa comprobando sucesivamente el siguiente bit a la derecha hasta que no haya más. El bit más a la derecha indica el recorrido final desde el padre del nodo deseado hasta el nodo mismo. Existe una compensación de tiempo y espacio entre iterar un árbol binario completo de esta manera o que cada nodo tenga puntero(s) a su(s) hermano(s).

Véase también

Referencias

Citas

  1. ^ Rowan Garnier; John Taylor (2009). Matemática discreta: pruebas, estructuras y aplicaciones, tercera edición. CRC Press. pág. 620. ISBN 978-1-4398-1280-8.
  2. ^ Steven S Skiena (2009). Manual de diseño de algoritmos. Springer Science & Business Media. pág. 77. ISBN 978-1-84800-070-4.
  3. ^ ab Knuth (1997). El arte de la programación informática, volumen 1, 3/E . Pearson Education. pág. 363. ISBN 0-201-89683-4.
  4. ^ Iván Flores (1971). Sistema de programación de computadoras/360 . Prentice-Hall. pág. 39.
  5. ^ Kenneth Rosen (2011). Matemática discreta y sus aplicaciones, 7.ª edición . McGraw-Hill Science. pág. 749. ISBN 978-0-07-338309-5.
  6. ^ David R. Mazur (2010). Combinatoria: una visita guiada. Asociación Matemática de Estados Unidos. p. 246. ISBN 978-0-88385-762-5.
  7. ^ ab "Árbol binario", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]También impreso como Michiel Hazewinkel (1997). Enciclopedia de matemáticas. Suplemento I. Springer Science & Business Media. pág. 124. ISBN 978-0-7923-4709-5.
  8. ^ LR Foulds (1992). Aplicaciones de la teoría de grafos. Springer Science & Business Media. pág. 32. ISBN 978-0-387-97599-3.
  9. ^ David Makinson (2009). Conjuntos, lógica y matemáticas para la informática . Springer Science & Business Media. pág. 199. ISBN 978-1-84628-845-6.
  10. ^ Jonathan L. Gross (2007). Métodos combinatorios con aplicaciones informáticas. CRC Press. pág. 248. ISBN 978-1-58488-743-0.
  11. ^ de Kenneth Rosen (2011). Matemática discreta y sus aplicaciones, séptima edición . McGraw-Hill Science. págs. 352-353. ISBN 978-0-07-338309-5.
  12. ^ Te Chiang Hu; Man-tak Shing (2002). Algoritmos combinatorios . Courier Dover Publications. pág. 162. ISBN 978-0-486-41962-6.
  13. ^ Lih-Hsing Hsu; Cheng-Kuan Lin (2008). Teoría de grafos y redes de interconexión. CRC Press. pág. 66. ISBN 978-1-4200-4482-9.
  14. ^ J. Flum; M. Grohe (2006). Teoría de la complejidad parametrizada . Springer. pág. 245. ISBN. 978-3-540-29953-0.
  15. ^ Tamassia, Michael T. Goodrich, Roberto (2011). Diseño de algoritmos: fundamentos, análisis y ejemplos de Internet (2.ª ed.). Nueva Delhi: Wiley-India. pág. 76. ISBN 978-81-265-0986-7.{{cite book}}: CS1 maint: multiple names: authors list (link)
  16. ^ "árbol binario completo". NIST .
  17. ^ Richard Stanley, Combinatoria enumerativa, volumen 2, pág. 36
  18. ^ "árbol binario perfecto". NIST .
  19. ^ ab "árbol binario completo". NIST.
  20. ^ "árbol binario casi completo". Archivado desde el original el 4 de marzo de 2016. Consultado el 11 de diciembre de 2015 .
  21. ^ "árbol binario casi completo" (PDF) . Archivado (PDF) del original el 2022-10-09.
  22. ^ Aaron M. Tenenbaum, et al. Estructuras de datos con C, Prentice Hall, 1990 ISBN 0-13-199746-7 
  23. ^ Paul E. Black (ed.), entrada para estructura de datos en Dictionary of Algorithms and Data Structures . Instituto Nacional de Estándares y Tecnología de EE. UU . . 15 de diciembre de 2004. Versión en línea Archivado el 21 de diciembre de 2010 en Wayback Machine . Consultado el 19 de diciembre de 2010.
  24. ^ Parmar, Anand K. (22 de enero de 2020). «Diferentes tipos de árboles binarios con ilustraciones coloridas». Medium . Consultado el 24 de enero de 2020 .
  25. ^ Mehta, Dinesh; Sartaj Sahni (2004). Manual de estructuras de datos y aplicaciones . Chapman y Hall . ISBN 1-58488-435-5.
  26. ^ D. Samanta (2004). Estructuras de datos clásicas . PHI Learning Pvt. Ltd., págs. 264-265. ISBN 978-81-203-1874-8.
  27. ^ Michael L. Scott (2009). Pragmática del lenguaje de programación (3.ª ed.). Morgan Kaufmann. pág. 347. ISBN 978-0-08-092299-7.
  28. ^ Introducción a los algoritmos . Cormen, Thomas H., Cormen, Thomas H. (2.ª ed.). Cambridge, Mass.: MIT Press. 2001. pág. 128. ISBN 0-262-03293-7.OCLC 46792720  .{{cite book}}: CS1 maint: others (link)
  29. ^ Laakso, Mikko. "Cola de prioridad y montón binario". Universidad de Aalto . Consultado el 11 de octubre de 2023 .
  30. ^ Demaine, Erik. «6.897: Advanced Data Structures Spring 2003 Lecture 12» (PDF) . MIT CSAIL. Archivado desde el original (PDF) el 24 de noviembre de 2005. Consultado el 14 de abril de 2022 .
  31. ^ ab Dung X. Nguyen (2003). "Binary Tree Structure". rice.edu . Consultado el 28 de diciembre de 2010 .
  32. ^ Wittman, Todd (13 de febrero de 2015). «Conferencia 18: Travesías de árboles» (PDF) . Archivado desde el original (PDF) el 13 de febrero de 2015. Consultado el 29 de abril de 2023 .

Bibliografía

Enlaces externos