Árbol binario

Forma limitada de estructura de datos de árbol

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:

• En primer lugar, como un medio para acceder a los nodos en función de algún valor o etiqueta asociada con cada nodo. ^[9] Los árboles binarios etiquetados de esta manera se utilizan para implementar árboles binarios de búsqueda y montones binarios , y se utilizan para una búsqueda y clasificación eficientes . La designación de nodos no raíz como hijo izquierdo o derecho incluso cuando solo hay un hijo presente es importante en algunas de estas aplicaciones, en particular, es significativa en los árboles de búsqueda binaria. ^[10] Sin embargo, la disposición de nodos particulares en el árbol no es parte de la información conceptual. Por ejemplo, en un árbol binario de búsqueda normal, la colocación de los nodos depende casi por completo del orden en el que se agregaron, y se puede reorganizar (por ejemplo, equilibrando ) sin cambiar el significado.
• En segundo lugar, como representación de datos con una estructura de bifurcación relevante. En tales casos, la disposición particular de los nodos debajo y/o a la izquierda o derecha de otros nodos es parte de la información (es decir, cambiarla cambiaría el significado). Ejemplos comunes ocurren con la codificación de Huffman y los cladogramas . La división cotidiana de documentos en capítulos, secciones, párrafos, etc. es un ejemplo análogo con árboles n -arios en lugar de árboles binarios.

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]

• El conjunto vacío es un árbol binario extendido
• si T ₁ y T ₂ son árboles binarios extendidos, entonces denotamos por T ₁ • T ₂ el árbol binario extendido obtenido sumando una raíz r conectada a la izquierda con T ₁ y a la derecha con T ₂ ^{[ aclaración necesaria: ¿dónde fue la 'r' en el símbolo 'T ₁ • T ₂ '? ]} agregando aristas cuando estos subárboles no están vacíos.

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 ₁ , E ₂ ), donde (V, E ₁ ∪ E ₂ ) es un árbol con raíz (equivalentemente arborescencia) y E ₁ ∩ E ₂ 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.

• AUn árbolbinario enraizado tiene unnodo raízy cada nodo tiene como máximo dos hijos.

Un árbol binario completo

Un cuadro de ascendencia que puede representarse en un árbol binario perfecto de cuatro niveles.

• AUn árbol binario completo (a veces denominadopropio,plano^[15] oestricto)^[16][17]es un árbol en el que cada nodo tiene 0 o 2 hijos. Otra forma de definir un árbol binario completo es unadefinición recursiva. Un árbol binario completo es:^[11]
  • Un solo vértice (un solo nodo como nodo raíz).
  • Un árbol cuyo nodo raíz tiene dos subárboles, ambos de los cuales son árboles binarios completos.
• AUn árbol binario perfecto es un árbol binario en el que todos los nodos interiores tienen dos hijosytodas las hojas tienen la mismaprofundidado el mismonivel(el nivel de un nodo definido como el número de aristas o enlaces desde el nodo raíz a un nodo).^[18]Un árbol binario perfecto es un árbol binario completo.
• AUn árbol binario completo es un árbol binario en el que cada nivel,excepto posiblemente el último, está completamente lleno, y todos los nodos del último nivel están lo más a la izquierda posible. Puede tener entre 1 y 2 ^h nodos en el último nivelh.^[19]Por lo tanto, un árbol perfecto siempre está completo, pero un árbol completo no siempre es perfecto. Algunos autores usan el términocompletopara referirse en cambio a unperfectocomo se definió anteriormente, en cuyo caso llaman a este tipo de árbol (con un último nivel posiblemente no lleno) uncasi completooárbol binariocasi completo^[20][21]Un árbol binario completo se puede representar de manera eficiente usando una matriz.^[19]

Un árbol binario completo (que no está lleno)

• El árbol binario completo infinito es un árbol con niveles, donde para cada nivel d el número de nodos existentes en el nivel d es igual a 2 ^d . El número cardinal del conjunto de todos los niveles es (infinito contable). El número cardinal del conjunto de todos los caminos (las "hojas", por así decirlo) es incontable, teniendo la cardinalidad del continuo . ${\displaystyle {\aleph _{0}}}$ ${\displaystyle {\aleph _{0}}}$
• Un árbol binario equilibrado es una estructura de árbol binario en la que los subárboles izquierdo y derecho de cada nodo difieren en altura (el número de aristas desde el nodo superior al nodo más alejado en un subárbol) en no más de 1 (o la desviación no es mayor que 1). ^[22] También se pueden considerar árboles binarios en los que ninguna hoja está mucho más alejada de la raíz que cualquier otra hoja. (Los diferentes esquemas de equilibrio permiten diferentes definiciones de "mucho más lejos". ^[23] )
• Un árbol degenerado (o patológico ) es aquel en el que cada nodo padre tiene solo un nodo hijo asociado. ^[24] Esto significa que el árbol se comportará como una estructura de datos de lista enlazada . En este caso, una ventaja de usar un árbol binario se reduce significativamente porque es esencialmente una lista enlazada cuya complejidad temporal es O( n ) ( n como el número de nodos) y tiene más espacio de datos que la lista enlazada debido a dos punteros por nodo, mientras que la complejidad de O(log ₂ n ) para la búsqueda de datos en un árbol binario equilibrado normalmente se espera.

Propiedades de los árboles binarios

• El número de nodos en un árbol binario completo es al menos y como máximo (es decir, el número de nodos en un árbol binario perfecto ), donde es la altura del árbol. Un árbol que consta solo de un nodo raíz tiene una altura de 0. El menor número de nodos se obtiene agregando solo dos nodos secundarios por sumando altura (1 para contar el nodo raíz). El número máximo de nodos se obtiene llenando completamente los nodos en cada nivel, es decir, es un árbol perfecto. Para un árbol perfecto, el número de nodos es , donde la última igualdad es de la suma de la serie geométrica . ${\displaystyle n}$ ${\displaystyle 2h+1}$ ${\displaystyle 2^{h+1}-1}$ ${\displaystyle h}$ ${\displaystyle 2h+1}$ ${\displaystyle 1+2+4+\ldots +2^{h}=2^{h+1}-1}$
• El número de nodos de hojas en un árbol binario perfecto es (donde es el número de nodos en el árbol) porque (usando la propiedad anterior) y el número de hojas es así que . También significa que . En términos de la altura del árbol , . ${\displaystyle l}$ ${\displaystyle l=(n+1)/2}$ ${\displaystyle n}$ ${\displaystyle n={{2}^{h+1}}-1}$ ${\displaystyle 2^{h}}$ ${\displaystyle n=2\cdot {{2}^{h}}-1=2l-1\to l=\left(n+1\right)/2}$ ${\displaystyle n=2l-1}$ ${\displaystyle h}$ ${\displaystyle l=(2^{h+1}-1+1)/2=2^{h}}$
• Para cualquier árbol binario no vacío con nodos hoja y nodos de grado 2 (nodos internos con dos nodos hijos), . ^[25] La prueba es la siguiente. Para un árbol binario perfecto, el número total de nodos es (Un árbol binario perfecto es un árbol binario completo.) y , por lo que . Para hacer un árbol binario completo a partir de un árbol binario perfecto, se eliminan un par de dos nodos hermanos uno por uno. Esto da como resultado "dos nodos hoja eliminados" y "un nodo interno eliminado" y "el nodo interno eliminado se convierte en un nodo hoja", por lo que se elimina un nodo hoja y un nodo interno por cada eliminación de dos nodos hermanos. Como resultado, también se cumple para un árbol binario completo. Para hacer un árbol binario con un nodo hoja sin su hermano, se elimina un solo nodo hoja de un árbol binario completo, luego "un nodo hoja eliminado" y "un nodo interno con dos hijos eliminados" por lo que también se cumple. Esta relación ahora cubre todos los árboles binarios no vacíos. ${\displaystyle l}$ ${\displaystyle i_{2}}$ ${\displaystyle l=i_{2}+1}$ ${\displaystyle n=2^{h+1}-1}$ ${\displaystyle l=2^{h}}$ ${\displaystyle i=n-l=(2^{h+1}-1)-2^{h}=2^{h}-1=l-1\to l=i+1}$ ${\displaystyle l=i+1}$ ${\displaystyle l=i+1}$
• Con nodos dados, la altura mínima posible del árbol es con la que el árbol es un árbol completo equilibrado o un árbol perfecto. Con una altura dada , el número de nodos no puede superar el número de nodos en un árbol perfecto. Por lo tanto , . ${\displaystyle n}$ ${\displaystyle h_{min}=\log _{2}(n+1)-1}$ ${\displaystyle h}$ ${\displaystyle 2^{h+1}-1}$ ${\displaystyle n\leq 2^{h+1}-1\to h\geq \log _{2}(n+1)-1}$
• Un árbol binario con hojas tiene al menos una altura . Con una altura dada , el número de hojas a esa altura no puede exceder el número de hojas a la altura en un árbol perfecto. Por lo tanto . ${\displaystyle l}$ ${\displaystyle h_{m}=\log _{2}(l)}$ ${\displaystyle h}$ ${\displaystyle 2^{h}}$ ${\displaystyle l\leq 2^{h}\to h\geq \log _{2}(l)}$
• En un árbol binario no vacío, si es el número total de nodos y es el número total de aristas, entonces . Esto es obvio porque cada nodo requiere una arista, excepto el nodo raíz. ${\displaystyle n}$ ${\displaystyle e}$ ${\displaystyle e=n-1}$
• El número de enlaces nulos (es decir, hijos ausentes de los nodos) en un árbol binario de n nodos es ( n + 1).
• El número de nodos internos en un árbol binario completo de n nodos es . ${\displaystyle \lfloor n/2\rfloor }$

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 ⁠ ⁠ ${\displaystyle X*X*X*X}$ , lo cual es posible de cinco formas:

$${\displaystyle ((X*X)*X)*X,\qquad (X*(X*X))*X,\qquad (X*X)*(X*X),\qquad X*((X*X)*X),\qquad X*(X*(X*X)).}$$

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 . ${\displaystyle C_{n}}$ ${\displaystyle C_{0}=1}$ ${\displaystyle \textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}}$ ${\displaystyle C_{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: ${\displaystyle C_{n}}$

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

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. ${\displaystyle w_{1}}$ ${\displaystyle w_{2}}$ ${\displaystyle w_{1}}$ ${\displaystyle w_{2}}$ ${\displaystyle w_{1}}$ ${\displaystyle w_{2}}$

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] ${\displaystyle 2i+1}$ ${\displaystyle 2i+2}$ ${\displaystyle \left\lfloor {\frac {i-1}{2}}\right\rfloor }$ ${\displaystyle 2i}$ ${\displaystyle 2i+1}$ ${\displaystyle \lfloor i/2\rfloor }$

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

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. ${\displaystyle n}$ ${\displaystyle \mathrm {C} _{n}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 4^{n}}$ ${\displaystyle \log _{2}4^{n}=2n}$ ${\displaystyle 2n+o(n)}$

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: ${\displaystyle 2n+1}$ ${\displaystyle n}$

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

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 ₂ ( 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

• 2–3 árboles
• 2–3–4 árboles
• Árbol AA
• Envoltura de anillas
• Árbol AVL
• Árbol B
• Partición del espacio binario
• Árbol de Huffman
• Árbol K-ario
• La desigualdad de Kraft
• Árbol de búsqueda binaria óptimo
• Árbol binario aleatorio
• Recursión (informática)
• Árbol rojo-negro
• Cuerda (informática)
• Árbol de búsqueda binario autoequilibrado
• Árbol de expansión
• Número de Strahler
• Árbol de ternas pitagóricas primitivas#Métodos alternativos para generar el árbol
• Árbol binario sin raíz

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. 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. "Á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. 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. "á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. 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

• Donald Knuth . The Art of Computer Programming vol 1. Fundamental Algorithms , tercera edición. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Sección 2.3, especialmente las subsecciones 2.3.1–2.3.2 (pp. 318–348). 

Enlaces externos

• Árboles binarios Archivado el 23 de septiembre de 2020 en la entrada Wayback Machine en la base de datos FindStat
• Prueba de árbol binario por inducción
• Árbol binario de búsqueda balanceado en una matriz Cómo crear una lista Ahnentafel de abajo a arriba o un árbol binario de búsqueda balanceado en una matriz
• Árboles binarios e implementación de los mismos con ejemplos de código funcional
• Implementación de árbol binario en JavaScript con código fuente