Árbol binario

En informática , un árbol binario es una estructura de datos 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 donde $k = 2.$ Una definición recursiva que utiliza la teoría de conjuntos es que un árbol binario es una terna ( L , S , R ) , donde L y R son árboles binarios o el conjunto vacío y S es un conjunto unitario (un conjunto de un solo elemento) que contiene la raíz. ^{[ 1 ]}^{[ 2 ]}

Desde la perspectiva de la teoría de grafos , los árboles binarios, tal como se definen aquí, son arborescencias . ^{[ 3 ]} Un árbol binario también puede denominarse arborescencia bifurcada , ^{[ 3 ]} un término que aparece en algunos libros de programación antiguos ^{[ 4 ]} antes de que prevaleciera la terminología moderna de la informática. También es posible interpretar un árbol binario como un grafo no dirigido , en lugar de un grafo dirigido , en cuyo caso un árbol binario es un árbol ordenado y enraizado . ^{[ 5 ]} Algunos autores utilizan "árbol binario enraizado" 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 comúnmente empleada en informática, ^{[ 7 ]} pero otros lo definen como aquel en el que cada nodo no hoja tiene exactamente dos hijos y no necesariamente los denominan izquierdo y derecho. ^{[ 8 ]}

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

Primero, como medio para acceder a los nodos en función de algún valor o etiqueta asociada a cada nodo. ^{[ 9 ]} Los árboles binarios etiquetados de esta manera se utilizan para implementar árboles de búsqueda binaria y montículos binarios , y se utilizan para búsqueda y ordenación eficientes . La designación de nodos que no son la raíz como hijo izquierdo o derecho, incluso cuando solo hay un hijo presente, importa 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 forma parte de la información conceptual. Por ejemplo, en un árbol de búsqueda binaria normal, la ubicación de los nodos depende casi por completo del orden en que se agregaron, y se puede reorganizar (por ejemplo, mediante balanceo ) sin cambiar el significado.
En segundo lugar, como representación de datos con una estructura bifurcada relevante. En estos casos, la disposición particular de los nodos debajo, a la izquierda o a la derecha de otros nodos forma parte de la información (es decir, modificarla alteraría su significado). Ejemplos comunes se encuentran en 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

Definición de árbol completo recursivo

Una forma sencilla e informal de describir un árbol binario podría ser la siguiente:

Un árbol binario tiene un nodo raíz, que tiene 0 o 2 nodos hijos (que a su vez pueden tener 0 o 2 hijos, y así sucesivamente).

De forma más formal:

(caso base) Existe un árbol completo que consta de un solo nodo;
(paso recursivo) Si T ₁ y T ₂ son árboles binarios completos que no comparten ningún nodo, y r es un nodo que no pertenece a T ₁ ni a T ₂ , entonces la tripleta ordenada (r, T ₁ , T ₂ ) es un árbol binario completo. ^{[ 11 ]}

Esta definición implica dos limitaciones: un árbol binario completo contiene al menos un nodo, y ningún nodo puede tener un solo hijo. Esto se resuelve con la siguiente definición.

Definición de árbol extendido recursivo

La definición extendida de árbol parte de la suposición de que el árbol puede estar vacío.

(caso base) Un conjunto vacío de nodos es un árbol binario extendido.
(paso recursivo) Si T ₁ y T ₂ son árboles binarios extendidos que no comparten ningún nodo, y r es un nodo que no pertenece a ninguno de ellos, entonces la tripleta ordenada (r, T ₁ , T ₂ ) es un árbol binario extendido. ^{[ 12 ]}^{[ 11 ]}

Para ser completas desde el punto de vista gráfico, ambas definiciones de árbol deben ampliarse con una definición de los conjuntos de ramas correspondientes. De manera informal, el conjunto de ramas puede describirse como un conjunto de todos los pares ordenados de nodos (r, s), donde $r$ es un nodo raíz de cualquier subárbol que aparezca en la definición, y $s$ es un nodo raíz de cualquiera de sus subárboles T1 _y T2 ₍ en caso de que el subárbol correspondiente no esté vacío).

Otra forma de imaginar esta construcción (y comprender 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. ^{[ 13 ]}

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 llamado árbol plano) en el que cada nodo tiene como máximo dos hijos. Un árbol con raíz proporciona de forma natural 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 más abajo. El ordenamiento de estos hijos (por ejemplo, dibujándolos en un plano) permite distinguir un hijo izquierdo de un hijo derecho. ^{[ 14 ]} Pero esto todavía no distingue entre un nodo con un hijo izquierdo pero no con un hijo derecho y un nodo con un hijo derecho pero sin hijo izquierdo.

La distinción necesaria puede hacerse dividiendo primero las aristas; es decir, definiendo el árbol binario como una tripleta (V, E ₁ , E ₂ ), donde (V, E ₁ ∪ E ₂ ) es un árbol con raíz (equivalentemente arborescencia) y E ₁ ∩ E ₂ es vacío, y también exigiendo que para todo j ∈ { 1, 2 }, cada nodo tenga como máximo un hijo E _j . ^{[ 15 ]} 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 diferentes" árboles binarios. ^{[ 7 ]}

Tipos de árboles binarios

La terminología relativa a los árboles no está bien estandarizada y, por lo tanto, puede variar entre los ejemplos que aparecen en la bibliografía disponible.

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

AUn árbol binario completo (a veces denominadoárbol binariopropio,^{[ 16 ]} planooestricto^{) [ 17 ]}^{[ 18 ]} es un árbol en el que cada nodo tiene 0 o 2 hijos. Otra forma de definir un árbol binario completo es mediante unadefinición recursiva. Un árbol binario completo es:^{[ 12 ]}
- Un único vértice (un único nodo como nodo raíz).
- Un árbol cuyo nodo raíz tiene dos subárboles, ambos árboles binarios completos.
AUn árbol binario perfecto es un árbol binario en el que todos los nodos internos tienen dos hijosytodas las hojas tienen la mismaprofundidado el mismonivel(el nivel de un nodo se define como el número de aristas o enlaces desde el nodo raíz a un nodo).^{[ 19 ]} 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.^{[ 20 ]} Por lo tanto, un árbol perfecto siempre es completo, pero un árbol completo no siempre es perfecto. Algunos autores usan el término"completo"para 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 completoocasi completo.^{[ 21 ]}^{[ 22 ]} Un árbol binario completo se puede representar eficientemente usando una matriz.^{[ 20 ]}

El árbol binario completo infinito es un árbol con ${\aleph _{0}}$ 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 ${\aleph _{0}}$ (contablemente infinito). El número cardinal del conjunto de todos los caminos (las "hojas", por así decirlo) es incontable, teniendo la cardinalidad del continuo .
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 más alto hasta el nodo más alejado en un subárbol) en no más de 1 (o la asimetría no es mayor que 1). ^{[ 23 ]} También se pueden considerar árboles binarios donde ninguna hoja está mucho más lejos de la raíz que cualquier otra hoja. (Los diferentes esquemas de equilibrio permiten diferentes definiciones de "mucho más lejos". ^{[ 24 ]} )
Un árbol degenerado (o patológico ) es aquel en el que cada nodo padre tiene solo un nodo hijo asociado. ^{[ 25 ]} Esto significa que el árbol se comportará como una estructura de datos de lista enlazada . En este caso, la 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 'O()' es la notación Big O ) 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 balanceado normalmente se espera.

Propiedades de los árboles binarios

El número de nodos $n$ en un árbol binario completo es al menos $2h+1$ y como máximo $2^{h+1}-1$ (es decir, el número de nodos en un árbol binario perfecto ), donde $h$ es la altura del árbol. Un árbol que consta solo de un nodo raíz tiene una altura de 0. El número mínimo de nodos se obtiene agregando solo dos nodos hijos por cada altura agregada, por lo que $2h+1$ (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 $1+2+4+\ldots +2^{h}=2^{h+1}-1$ , donde la última igualdad proviene de la suma de la serie geométrica .
El número de nodos hoja $l$ en un árbol binario perfecto es $l=(n+1)/2$ (donde $n$ es el número de nodos en el árbol) porque $n={{2}^{h+1}}-1$ (utilizando la propiedad anterior) y el número de hojas es $2^{h}$ entonces $n=2\cdot {{2}^{h}}-1=2l-1\to l=\left(n+1\right)/2$ También significa que $n=2l-1$ En términos de la altura del árbol $h$ , $l=(2^{h+1}-1+1)/2=2^{h}$ .
Para cualquier árbol binario no vacío con $l$ nudos de hojas y $i_{2}$ nodos de grado 2 (nodos internos con dos nodos hijos), $l=i_{2}+1$ . ^{[ 26 ]} La prueba es la siguiente. Para un árbol binario perfecto, el número total de nodos es $n=2^{h+1}-1$ (un árbol binario perfecto es también un árbol binario completo) y $l=2^{h}$ , entonces $i=nl=(2^{h+1}-1)-2^{h}=2^{h}-1=l-1\to l=i+1$ Para crear un árbol binario completo a partir de un árbol binario perfecto, se eliminan uno a uno pares de nodos hermanos. Esto da como resultado la eliminación de dos nodos hoja y un nodo interno, y que el nodo interno eliminado se convierta en un nodo hoja. Por lo tanto, se elimina un nodo hoja y un nodo interno por cada dos nodos hermanos eliminados. Como resultado, $l=i+1$ Esto también se aplica a un árbol binario completo. Para crear un árbol binario con un nodo hoja sin su hermano, se elimina un solo nodo hoja de un árbol binario completo, luego se elimina "un nodo hoja" y "un nodo interno con dos hijos eliminados", por lo que $l=i+1$ También se cumple. Esta relación ahora abarca todos los árboles binarios no vacíos.
Con $n$ nodos dados, la altura mínima posible del árbol es $h_{\min }=\log _{2}(n+1)-1$ con el cual el árbol es un árbol completo equilibrado o un árbol perfecto. Con una altura dada $h$ , el número de nodos no puede exceder el $2^{h+1}-1$ como el número de nodos en un árbol perfecto. Por lo tanto $n\leq 2^{h+1}-1\to h\geq \log _{2}(n+1)-1$ .
Un árbol binario con $l$ hojas tiene al menos la altura $h_{m}=\log _{2}(l)$ Con una altura $h$ dada , el número de hojas a esa altura no puede exceder $2^{h}$ como el número de hojas a la altura de un árbol perfecto. Por lo tanto $l\leq 2^{h}\to h\geq \log _{2}(l)$ .
En un árbol binario no vacío, si $n$ es el número total de nodos y $e$ es el número total de aristas, entonces $e=n-1$ Esto es obvio porque cada nodo requiere una arista, excepto el nodo raíz.
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 $\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 el 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$ hay que poner entre paréntesis una cadena como $X*X*X*X$ ⁠ , lo cual es posible de cinco maneras:

((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 los árboles binarios debería ser obvia, y la adición de paréntesis redundantes (alrededor de una expresión ya entre paréntesis o alrededor de la expresión completa) no está permitida (o al menos no se considera que produzca una nueva posibilidad).

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 $C_{n}$ de árboles binarios de tamaño n tiene la siguiente descripción recursiva $C_{0}=1$ , y $\textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}$ para cualquier entero positivo n . De ello se deduce que $C_{n}$ es el número catalán de índice n . ^{[ 18 ]}

Las cadenas entre paréntesis anteriores no deben confundirse con el conjunto de palabras de longitud 2n en el lenguaje Dyck , que consisten únicamente en paréntesis dispuestos de forma equilibrada. El número de dichas cadenas satisface la misma descripción recursiva (cada palabra Dyck de longitud 2n está determinada por la subpalabra Dyck encerrada entre el paréntesis inicial '(' y su correspondiente ')' junto con la subpalabra Dyck restante después de ese paréntesis de cierre, cuyas longitudes 2i y 2j satisfacen i $+ j + 1 = n$ ); por lo tanto, este número es también el número de Catalan. $C_{n}$ . ^{[ 27 ]} Así que también hay cinco palabras de Dyck de longitud 6:

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

Estas palabras de Dyck no se corresponden con 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 ( $w_{1}$ ) $w_{2}$ , dónde $w_{1}$ , $w_{2}$ 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 $w_{1}$ y $w_{2}$ corresponden a los árboles binarios que son los hijos izquierdo y derecho de la raíz.

Una correspondencia biyectiva también puede definirse de la siguiente manera: encerrar la palabra de Dyck en un par de paréntesis adicionales, de modo que el resultado pueda interpretarse como una expresión de lista de Lisp (con la lista vacía () como único átomo que aparece); entonces la expresión de par punteado 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 unitario.

Métodos para almacenar árboles binarios

Los árboles binarios se pueden construir a partir de primitivas de lenguajes de programación de varias maneras.

Nodos y referencias

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

Este método de almacenamiento de árboles binarios desperdicia bastante 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 . ^{[ 28 ]}

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

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 arreglos , 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 $2i+1$ (para el niño izquierdo) y $2i+2$ (a la derecha), mientras que su padre (si lo hay) se encuentra en el índice $\left\lfloor {\frac {i-1}{2}}\right\rfloor$ (suponiendo que la raíz tiene índice cero). Alternativamente, con una matriz indexada desde 1, la implementación se simplifica con los hijos encontrados en $2i$ y $2i+1$ y padre encontrado en $\lfloor i/2\rfloor$ . ^{[ 30 ]}

Este método se beneficia de un almacenamiento más compacto y una mejor localidad de referencia , particularmente durante un recorrido en preorden. Se utiliza frecuentemente para montículos binarios . ^{[ 31 ]}

Codificaciones

Codificaciones sucintas

Una estructura de datos concisa es aquella que ocupa un espacio mínimo posible, según lo establecido por los límites inferiores de la teoría de la información . El número de árboles binarios diferentes en $n$ nodos es $\mathrm {C} _ {n}$ , el $n$ Número catalán (suponiendo que consideramos idénticos a los árboles con estructura idéntica). Para grandes $n$ , esto es sobre $4^{n}$ ; por lo tanto necesitamos al menos aproximadamente $\log _{2}4^{n}=2n$ bits para codificarlo. Por lo tanto, un árbol binario sucinto ocuparía 2 n +o( n ) bits (donde 'o()' es la notación Little-o ).

Una representación sencilla que cumple con este límite consiste en recorrer los nodos del árbol en preorden, generando "1" para un nodo interno y "0" para una hoja. ^{[ 32 ]} Si el árbol contiene datos, podemos almacenarlos simultáneamente en un arreglo consecutivo en preorden. Esta función logra esto:

función EncodeSuccinct( nodo n, estructura de cadena de bits , datos de matriz ) { si n = nil entonces agregar 0 a la estructura; demás agregar 1 a la estructura; agregar n.data a data; EncodeSuccinct(n.left, estructura, datos); EncodeSuccinct(n.right, estructura, datos); }

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

función DecodeSuccinct( estructura de cadena de bits , datos de matriz ) { elimina el primer bit de la estructura y colócalo en b si b = 1 entonces crea un nuevo nodo n elimina el primer elemento de los datos y colócalo en n.data n.left = DecodeSuccinct(estructura, datos) n.right = DecodeSuccinct(estructura, datos) Devuelve n, de lo contrario, devuelve nil. }

Las representaciones concisas más sofisticadas permiten no solo un almacenamiento compacto de árboles, sino incluso operaciones útiles directamente sobre ellos mientras aún se encuentran en su forma concisa.

Codificación de árboles ordenados como árboles binarios

Existe una correspondencia natural biunívoca entre árboles ordenados y árboles binarios. Esto 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 se corresponden:

En el árbol binario que se muestra en la imagen, las aristas negras de la izquierda representan al primer hijo , mientras que las aristas azules de la derecha representan al siguiente hermano .

Esta representación se denomina árbol binario hijo izquierdo-hermano derecho .

Operaciones comunes

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

Existen diversas operaciones que se pueden realizar en árboles binarios. Algunas son operaciones de modificación , mientras que otras simplemente devuelven información útil sobre el árbol.

Inserción

En los árboles binarios, los nodos se pueden insertar entre otros dos nodos o agregarse después de un nodo hoja . Al insertar un nodo, se especifica de quién será hijo.

Nodos hoja

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

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

Supresión

La eliminación es el proceso mediante el cual se elimina un nodo del árbol. Solo ciertos nodos en un árbol binario pueden eliminarse de forma inequívoca. ^{[ 33 ]}

Nodo con cero o un hijo

Supongamos que el nodo a eliminar es el nodo A. Si A no tiene hijos, la eliminación se realiza estableciendo el hijo del padre de A en nulo . Si A tiene un hijo, se establece el padre del hijo de A en el padre de A y 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. ^{[ 33 ]} Sin embargo, en ciertos árboles binarios (incluidos los árboles de búsqueda binaria ) estos nodos se pueden eliminar, aunque con una reorganización de la estructura del árbol.

Recorrido

Los recorridos en preorden, en orden y en postorden visitan cada nodo de un árbol de forma recursiva, recorriendo cada nodo de los subárboles izquierdo y derecho de la raíz. A continuación se describen brevemente los recorridos mencionados.

Hacer un pedido

En el recorrido en preorden, siempre visitamos el nodo actual; luego, recorremos recursivamente el subárbol izquierdo del nodo actual y, finalmente, el subárbol derecho. El recorrido en preorden es topológicamente ordenado , ya que un nodo padre se procesa antes que cualquiera de sus nodos hijos.

En orden

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

Pedido posterior

En el recorrido en postorden, siempre recorremos recursivamente el subárbol izquierdo del nodo actual; luego, recorremos recursivamente el subárbol derecho del nodo actual y, finalmente, volvemos al nodo actual. El recorrido en postorden puede ser útil para obtener la expresión postfija de un árbol de expresiones binarias . ^{[ 34 ]}

Orden en profundidad

En la búsqueda en profundidad, siempre intentamos visitar el nodo más alejado posible de la raíz, con la salvedad de que debe ser hijo de un nodo que ya hemos visitado. A diferencia de la búsqueda en profundidad en grafos, no es necesario recordar todos los nodos visitados, ya que un árbol no puede contener ciclos. El preorden es un caso especial de esto. Consulte la sección sobre búsqueda en profundidad para obtener más información.

Orden en amplitud

A diferencia del orden en profundidad, el orden en amplitud siempre intenta visitar el nodo más cercano a la raíz que aún no haya visitado. Consulte la búsqueda en amplitud para obtener más información. También se denomina recorrido por niveles .

En un árbol binario completo, el índice de amplitud de un nodo ( i − ( ^2d − 1)) puede usarse como instrucciones de recorrido desde la raíz. Leyendo bit a bit de izquierda a derecha, comenzando en el bit d − 1, donde d es la distancia del nodo a la raíz ( d = ⌊log ₂ ( i + 1)⌋) y el nodo en cuestión no es la raíz misma ( d > 0). Cuando el índice de amplitud está enmascarado en el bit d − 1, los valores de bit 0 y 1 significan avanzar a la izquierda o a 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 entre tiempo y espacio al iterar un árbol binario completo de esta manera y al tener cada nodo punteros a sus hermanos.

Referencias

Citas

↑ Rowan Garnier; John Taylor (2009). Matemáticas discretas: demostraciones, estructuras y aplicaciones, tercera edición . CRC Press. pág. 620. ISBN 978-1-4398-1280-8.
↑ Steven S Skiena (2009). Manual de diseño de algoritmos . Springer Science & Business Media. pág. 77. ISBN 978-1-84800-070-4.
1 2 Knuth (1997). El arte de la programación informática, Volumen 1, 3.ª ed . Pearson Education. pág. 363. ISBN 0-201-89683-4.
↑ Iván Flores (1971). Sistema de programación informática/360 . Prentice-Hall. pág. 39.
↑ Kenneth Rosen (2011). Matemáticas discretas y sus aplicaciones, 7.ª edición . McGraw-Hill Science. pág. 749. ISBN 978-0-07-338309-5.
↑ David R. Mazur (2010). Combinatoria: Una visita guiada . Asociación Matemática de América. pág. 246. ISBN 978-0-88385-762-5.
1 2 "Árbol binario" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]También publicado como Michiel Hazewinkel (1997). Enciclopedia de Matemáticas. Suplemento I. Springer Science & Business Media. pág. 124. ISBN 978-0-7923-4709-5.
↑ LR Foulds (1992). Aplicaciones de la teoría de grafos . Springer Science & Business Media. pág. 32. ISBN 978-0-387-97599-3.
↑ David Makinson (2009). Conjuntos, lógica y matemáticas para la computación . Springer Science & Business Media. pág. 199. ISBN 978-1-84628-845-6.
↑ Jonathan L. Gross (2007). Métodos combinatorios con aplicaciones informáticas . CRC Press. pág. 248. ISBN 978-1-58488-743-0.
1 2 Long, Chengjiang (26 de octubre de 2018), Lección 22: Definiciones recursivas e inducción estructural (PDF)
1 2 Kenneth Rosen (2011). Matemáticas discretas y sus aplicaciones, 7.ª edición . McGraw-Hill Science. págs. 352–353 . ISBN 978-0-07-338309-5.
↑ Te Chiang Hu; Man-tak Shing (2002). Algoritmos combinatorios . Courier Dover Publications. pág. 162. ISBN 978-0-486-41962-6.
↑ 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.
↑ J. Flum; M. Grohe (2006). Teoría de la complejidad parametrizada . Springer. pág. 245. ISBN 978-3-540-29953-0.
↑ 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: varios nombres: lista de autores ( enlace )
↑ "árbol binario completo" . NIST .
1 2 Richard Stanley, Combinatoria enumerativa, volumen 2, pág. 36
↑ "árbol binario perfecto" . NIST .
1 2 "árbol binario completo" . NIST.
↑ "árbol binario casi completo" . Archivado del original el 4 de marzo de 2016. Consultado el 11 de diciembre de 2015 .
↑ "Árbol binario casi completo" (PDF) . Archivado (PDF) del original el 09/10/2022.
↑ Aaron M. Tenenbaum, et al. Estructuras de datos usando C, Prentice Hall, 1990 ISBN 0-13-199746-7
↑ Paul E. Black (ed.), entrada para estructura de datos en el Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología de EE . UU. 15 de diciembre de 2004. Versión en línea . Consultado el 19 de diciembre de 2010.
↑ Parmar, Anand K. (22 de enero de 2020). "Diferentes tipos de árboles binarios con coloridas ilustraciones" . Medium . Recuperado el 24 de enero de 2020 .
↑ Mehta, Dinesh; Sartaj Sahni (2004). Manual de estructuras de datos y aplicaciones . Chapman and Hall . ISBN 1-58488-435-5.
↑ Knuth, Donald E. El arte de la programación informática, Volumen 4A : Algoritmos combinatorios, Parte 1 .
↑ D. Samanta (2004). Estructuras de datos clásicas . PHI Learning Pvt. Ltd. págs. 264–265 . ISBN 978-81-203-1874-8.
↑ Michael L. Scott (2009). Pragmática del lenguaje de programación (3.ª ed.). Morgan Kaufmann. pág. 347. ISBN 978-0-08-092299-7.
↑ Introducción a los algoritmos . Cormen, Thomas H., Cormen, Thomas H. (2.ª ed.). Cambridge, Mass.: MIT Press. 2001. p. 128. ISBN 0-262-03293-7OCLC 46792720 {{cite book}}: CS1 mantenimiento: otros ( enlace )
↑ Laakso, Mikko. "Cola de prioridad y montón binario" . Universidad de Aalto . Consultado el 11 de octubre de 2023 .
↑ Demaine, Erik. "6.897: Estructuras de datos avanzadas Primavera 2003 Lección 12" (PDF) . MIT CSAIL. Archivado del original (PDF) el 24 de noviembre de 2005. Recuperado el 14 de abril de 2022 .
1 2 Dung X. Nguyen (2003). "Estructura de árbol binario" . rice.edu . Recuperado el 28 de diciembre de 2010 .
↑ Wittman, Todd (13 de febrero de 2015). "Lección 18: Recorridos de árboles" (PDF) . Archivado del original (PDF) el 13 de febrero de 2015. Consultado el 29 de abril de 2023 .

Bibliografía

Donald Knuth . El arte de la programación informática, vol. 1. Algoritmos fundamentales , tercera edición. Addison-Wesley, 1997. ISBN 0-201-89683-4. Sección 2.3, especialmente los apartados 2.3.1–2.3.2 (págs. 318–348).

Enlaces externos

Árboles binarios Archivado el 23/09/2020 en la entrada de Wayback Machine en la base de datos FindStat
Prueba de árbol binario por inducción. Archivado el 7 de abril de 2019 en Wayback Machine.
Árbol de búsqueda binaria balanceado en un array Cómo crear de abajo hacia arriba una lista de Ahnentafel, o un árbol de búsqueda binaria balanceado en un array
Árboles binarios e implementación de los mismos con ejemplos de código funcionales.
Visualizador de árboles binarios y gráficos
Implementación de un árbol binario en JavaScript con código fuente
Vista superior de un árbol binario
Vista inferior del árbol binario
Vista izquierda del árbol binario

[GarnierTaylor2009-1] Rowan Garnier; John Taylor (2009). Matemáticas discretas: demostraciones, estructuras y aplicaciones, tercera edición . CRC Press. pág. 620. ISBN 978-1-4398-1280-8.

[Skiena2009-2] Steven S Skiena (2009). Manual de diseño de algoritmos . Springer Science & Business Media. pág. 77. ISBN 978-1-84800-070-4.

[Knuth1997-3] 1 2 Knuth (1997). El arte de la programación informática, Volumen 1, 3.ª ed . Pearson Education. pág. 363. ISBN 0-201-89683-4.

[Flores1971-4] Iván Flores (1971). Sistema de programación informática/360 . Prentice-Hall. pág. 39.

[5] Kenneth Rosen (2011). Matemáticas discretas y sus aplicaciones, 7.ª edición . McGraw-Hill Science. pág. 749. ISBN 978-0-07-338309-5.

[Mazur2010-6] David R. Mazur (2010). Combinatoria: Una visita guiada . Asociación Matemática de América. pág. 246. ISBN 978-0-88385-762-5.

[oem-7] 1 2 "Árbol binario" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]También publicado como Michiel Hazewinkel (1997). Enciclopedia de Matemáticas. Suplemento I. Springer Science & Business Media. pág. 124. ISBN 978-0-7923-4709-5.

[Foulds1992-8] LR Foulds (1992). Aplicaciones de la teoría de grafos . Springer Science & Business Media. pág. 32. ISBN 978-0-387-97599-3.

[Makinson2009b-9] David Makinson (2009). Conjuntos, lógica y matemáticas para la computación . Springer Science & Business Media. pág. 199. ISBN 978-1-84628-845-6.

[Gross2007-10] Jonathan L. Gross (2007). Métodos combinatorios con aplicaciones informáticas . CRC Press. pág. 248. ISBN 978-1-58488-743-0.

[Long2018-11] 1 2 Long, Chengjiang (26 de octubre de 2018), Lección 22: Definiciones recursivas e inducción estructural (PDF)

[Rosen2011-12] 1 2 Kenneth Rosen (2011). Matemáticas discretas y sus aplicaciones, 7.ª edición . McGraw-Hill Science. págs. 352–353 . ISBN 978-0-07-338309-5.

[HuShing2002-13] Te Chiang Hu; Man-tak Shing (2002). Algoritmos combinatorios . Courier Dover Publications. pág. 162. ISBN 978-0-486-41962-6.

[HsuLin2008-14] 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.

[FlumGrohe2006-15] J. Flum; M. Grohe (2006). Teoría de la complejidad parametrizada . Springer. pág. 245. ISBN 978-3-540-29953-0.

[16] 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: varios nombres: lista de autores ( enlace )

[17] "árbol binario completo" . NIST .

[:0-18] 1 2 Richard Stanley, Combinatoria enumerativa, volumen 2, pág. 36

[19] "árbol binario perfecto" . NIST .

[complete_binary_tree-20] 1 2 "árbol binario completo" . NIST.

[almost_complete_binary_tree-21] "árbol binario casi completo" . Archivado del original el 4 de marzo de 2016. Consultado el 11 de diciembre de 2015 .

[nearly_complete_binary_tree-22] "Árbol binario casi completo" (PDF) . Archivado (PDF) del original el 09/10/2022.

[23] Aaron M. Tenenbaum, et al. Estructuras de datos usando C, Prentice Hall, 1990 ISBN 0-13-199746-7

[24] Paul E. Black (ed.), entrada para estructura de datos en el Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología de EE . UU. 15 de diciembre de 2004. Versión en línea . Consultado el 19 de diciembre de 2010.

[25] Parmar, Anand K. (22 de enero de 2020). "Diferentes tipos de árboles binarios con coloridas ilustraciones" . Medium . Recuperado el 24 de enero de 2020 .

[26] Mehta, Dinesh; Sartaj Sahni (2004). Manual de estructuras de datos y aplicaciones . Chapman and Hall . ISBN 1-58488-435-5.

[27] Knuth, Donald E. El arte de la programación informática, Volumen 4A : Algoritmos combinatorios, Parte 1 .

[Samanta2004-28] D. Samanta (2004). Estructuras de datos clásicas . PHI Learning Pvt. Ltd. págs. 264–265 . ISBN 978-81-203-1874-8.

[Scott2009-29] Michael L. Scott (2009). Pragmática del lenguaje de programación (3.ª ed.). Morgan Kaufmann. pág. 347. ISBN 978-0-08-092299-7.

[30] Introducción a los algoritmos . Cormen, Thomas H., Cormen, Thomas H. (2.ª ed.). Cambridge, Mass.: MIT Press. 2001. p. 128. ISBN 0-262-03293-7OCLC 46792720 {{cite book}}: CS1 mantenimiento: otros ( enlace )

[31] Laakso, Mikko. "Cola de prioridad y montón binario" . Universidad de Aalto . Consultado el 11 de octubre de 2023 .

[32] Demaine, Erik. "6.897: Estructuras de datos avanzadas Primavera 2003 Lección 12" (PDF) . MIT CSAIL. Archivado del original (PDF) el 24 de noviembre de 2005. Recuperado el 14 de abril de 2022 .

[rice-33] 1 2 Dung X. Nguyen (2003). "Estructura de árbol binario" . rice.edu . Recuperado el 28 de diciembre de 2010 .

[34] Wittman, Todd (13 de febrero de 2015). "Lección 18: Recorridos de árboles" (PDF) . Archivado del original (PDF) el 13 de febrero de 2015. Consultado el 29 de abril de 2023 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

) [ 17 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]