Árbol binario

Forma limitada de estructura de datos de árbol.

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

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 y 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 la perspectiva de la teoría de grafos , los árboles binarios tal como se definen aquí son arborescencias . ^[3] Por lo tanto, un árbol binario también puede denominarse arborescencia bifurcada , ^[3] un término que aparece en algunos de los primeros libros de programación ^[4] antes de que prevaleciera la terminología informática moderna. También es posible interpretar un árbol binario como un gráfico no dirigido , en lugar de dirigido , en cuyo caso un árbol binario es un árbol ordenado y con raíces . ^[5] Algunos autores utilizan un árbol binario enraizado en lugar de un árbol binario para enfatizar el hecho de que el árbol está enraizado, pero como se definió anteriormente, un árbol binario siempre está enraizado. ^[6]

En matemáticas, lo que se denomina árbol binario puede variar significativamente de un autor a otro. Algunos usan la definición comúnmente utilizada en informática, ^[7] pero otros la definen como cada no-hoja que tiene exactamente dos hijos y tampoco etiquetan necesariamente a los hijos como izquierda y derecha. ^[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 binarios y montones binarios , y se utilizan para búsquedas y clasificaciones eficientes . La designación de nodos no raíz como hijos izquierdo o derecho incluso cuando solo hay un hijo presente es importante en algunas de estas aplicaciones; en particular, es importante 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 de búsqueda binario normal, la ubicación de los nodos depende casi por completo del orden en que se agregaron y se pueden reorganizar (por ejemplo, equilibrándolos ) sin cambiar el significado.
• En segundo lugar, como representación de datos con una estructura bifurcada 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 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 denotemos por T ₁ • T ₂ el árbol binario extendido obtenido sumando una raíz r conectada a la izquierda de T ₁ y a la derecha de T ₂ ^{[ se necesita aclaración de dónde surgió el ' r' ingresa el símbolo 'T ₁ • T ₂ ' ]} agregando bordes cuando estos subárboles no están vacíos.

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. ^[12]

Usando conceptos de teoría de grafos

Un árbol binario es un árbol enraizado 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 enraizado imparte naturalmente una noción de niveles (distancia desde la raíz); por tanto, para cada nodo, se puede definir una noción de hijos como los nodos conectados a él en un nivel inferior. La ordenación de estos hijos (p. ej., 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 sin hijo izquierdo.

La distinción necesaria se puede hacer dividiendo primero los bordes; es decir, definir el árbol binario como triplete (V, E ₁ , E ₂ ), donde (V, E ₁ ∪ E ₂ ) es un árbol enraizado (equivalentemente arborescencia) y E ₁ ∩ E ₂ está vacío, y también requiere que para todos j ∈ { 1, 2 }, cada nodo tiene 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 diferentes" binarios. árboles. ^[7]

Tipos de árboles binarios

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

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

Un árbol binario completo

Un gráfico de ascendencia que se puede asignar a un árbol binario perfecto de 4 niveles.

• AEl árbol binario completo (a veces denominadoplanopropio,^[15] oárbol binarioestricto^[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 árboles binarios completos.
• AEl á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 todos los niveles,excepto posiblemente el último, están completamente llenos 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 utilizan el términocompletopara referirse a unperfectocomo se define anteriormente, en cuyo caso llaman a este tipo de árbol (con un último nivel posiblemente no lleno) árbolcasi completooárbol binariocasi completo^[20][21]Un árbol binario completo se puede representar eficientemente usando una matriz. ^[19]

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

• En 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 (contablemente infinito). 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 hasta el nodo más lejano en un subárbol) en no más de 1 (o la inclinación). no es mayor que 1). ^[22] También se pueden considerar árboles binarios donde 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 donde cada nodo padre tiene solo un nodo hijo asociado. ^[24] Esto significa que el árbol se comportará como una estructura de datos de lista vinculada . 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 tiene más espacio de datos que la lista enlazada debido a dos punteros por nodo, mientras que normalmente se espera la complejidad de O (log ₂ n ) para la búsqueda de datos en un árbol binario equilibrado.

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 sumando solo dos nodos secundarios por cada altura sumada (1 para contar el nodo raíz). El número máximo de nodos se obtiene llenando completamente los nodos de cada nivel, es decir, es un árbol perfecto. Para un árbol perfecto, el número de nodos es , donde la última igualdad proviene 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 hoja en un árbol binario perfecto es (donde está el número de nodos en el árbol) porque (usando la propiedad anterior) y el número de hojas es así . También significa eso . 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 secundarios), . ^[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 , entonces . Para crear 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 que "se eliminen dos nodos de hoja" y "se elimine un nodo interno" y "el nodo interno eliminado se convierta en un nodo de hoja", por lo que se eliminan un nodo de hoja y un nodo interno cada vez que se eliminan dos nodos hermanos. Como resultado, esto también es válido para un árbol binario completo. Para hacer un árbol binario con un nodo hoja sin su hermano, se elimina un nodo hoja único de un árbol binario completo, luego "se elimina un nodo hoja" y "se eliminan un nodo interno con dos hijos", 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 determinada , la cantidad de nodos no puede exceder la cantidad de nodos en un árbol perfecto. De este modo . ${\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 la altura . Con una altura determinada , el número de hojas a esa altura no puede exceder el número de hojas a la altura en un árbol perfecto. De este modo . ${\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 un borde 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 determinado. 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 determinado), y los árboles se distinguen sólo por su estructura; sin embargo, se distinguen los hijos izquierdo y derecho de cualquier nodo (si son árboles diferentes, intercambiarlos producirá un árbol distinto del original). El tamaño del árbol se considera 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 argumentos de cada operador. Por ejemplo, para n = 3 hay que poner entre paréntesis una cadena como , lo cual es posible de cinco maneras: ${\displaystyle X*X*X*X}$

$${\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 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 genere una nueva posibilidad).

Existe un árbol binario único 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 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 catalán 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 constan únicamente de paréntesis de tal manera que estén adecuadamente equilibrados. El número de tales cadenas satisface la misma descripción recursiva (cada palabra de Dyck de longitud 2 n está determinada por la subpalabra de Dyck encerrada por el '(' y su correspondiente ')' junto con la subpalabra de 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 tanto, también el número catalán . Entonces también hay cinco palabras de Dyck de longitud 6: ${\displaystyle C_{n}}$

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

Estas palabras de Dyck no se corresponden de la misma manera con los árboles binarios. En cambio, están relacionados mediante 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. Luego, la biyección se define 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: incluya la palabra Dyck entre un par de paréntesis adicionales, de modo que el resultado pueda interpretarse como una expresión de lista Lisp (con la lista vacía () como el único átomo que ocurre); entonces la expresión de par de puntos para esa lista adecuada 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 adecuada).

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 generalmente se construyen con una estructura de nodos de árbol que contiene algunos datos y referencias a su hijo izquierdo y a su hijo derecho. A veces también contiene una referencia a su padre único. Si un nodo tiene menos de dos hijos, algunos de los punteros secundarios pueden establecerse en un valor nulo especial o en un ganglio centinela especial .

Este método de almacenar á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 subproceso . ^[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 datos de tres, hijo izquierdo y hijo derecho, y el otro es una "hoja". "nodo, que no contiene datos y funciona de manera 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]

escriba  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 1, la implementación se simplifica con los hijos encontrados en y y los padres encontrados 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. Sin embargo, su crecimiento es costoso ^[29] y desperdicia espacio proporcional ^{[ cita necesaria ]} a 2 ^h - n para un árbol de profundidad h con n nodos. ${\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 de almacenamiento se utiliza a menudo para montones binarios . ^[30]

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, según lo establecido por los límites inferiores teóricos de la información . El número de árboles binarios diferentes en los nodos es , el enésimo número catalán (suponiendo que consideremos árboles con estructura idéntica como idénticos). En el caso de las grandes , se trata de ; por lo tanto, necesitamos al menos unos bits para codificarlo. Por 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 simple que cumple con este límite es visitar los nodos del árbol en preorden, generando "1" para un nodo interno y "0" para una hoja. ^[31] Si el árbol contiene datos, simplemente podemos 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 = nil  entonces agregue 0 a la estructura; demás agregar 1 a la estructura; agregar n.datos a los datos; EncodeSuccinct(n.izquierda, estructura, datos); EncodeSuccinct(n.derecho, 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 nuevamente al árbol original de esta manera: ${\displaystyle 2n+1}$ ${\displaystyle n}$

función DecodeSuccinct ( estructura de cadena de bits , datos de matriz ) { elimine la primera parte de la estructura y colóquela en b  si b = 1 , luego cree un nuevo nodo n elimine el primer elemento de datos y colóquelo en n.data n.left = DecodeSuccinct(estructura, datos) n.right = DecodeSuccinct(estructura, datos) devolver n en caso contrario  devolver nulo}

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

Codificación de árboles ordenados como árboles binarios

Existe una correspondencia natural uno a uno entre árboles ordenados y árboles binarios. Permite representar de forma única cualquier árbol ordenado 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 el primer hijo de T , mientras que el hijo derecho de B representa el 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 que se muestra, los bordes negros de la izquierda representan el primer hijo , mientras que los bordes azules de la derecha representan el 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 .

Hay una variedad de operaciones diferentes que se pueden realizar en árboles binarios. Algunas son operaciones mutadoras , 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 agregarse después de un nodo hoja . En los árboles binarios, un nodo que se inserta se especifica de quién será hijo.

Nodos de 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 el nodo A como su padre.

Nodos internos

El proceso de insertar un nodo en un árbol binario.

La inserción en los nudos internos es ligeramente más compleja que en los nudos de las hojas. Digamos que el nodo interno es el nodo A y que el nodo B es hijo de A. (Si la inserción es para insertar un hijo derecho, entonces B es el hijo derecho de A, y lo mismo ocurre 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 nuevo nodo.

Supresión

La eliminación es el proceso mediante el cual se elimina un nodo del árbol. Sólo determinados nodos de un árbol binario se pueden eliminar sin ambigüedades. ^[32]

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 nulo . Si A tiene un hijo, establezca el padre del hijo de A como el padre de A y establezca el hijo del padre de A como el hijo de A.

Nodo con dos hijos.

En un árbol binario, un nodo con dos hijos no se puede eliminar sin ambigüedades. ^[32] 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.

El recorrido

El recorrido de preorden, en orden y postorden visita 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 preorden, siempre visitamos el nodo actual; a continuación, atravesamos recursivamente el subárbol izquierdo del nodo actual y luego atravesamos recursivamente el subárbol derecho del nodo actual. El recorrido de preorden está ordenado topológicamente , porque un nodo principal se procesa antes de que se realice cualquiera de sus nodos secundarios.

En orden

En orden, siempre atravesamos recursivamente el subárbol izquierdo del nodo actual; a continuación, visitamos el nodo actual y, por último, atravesamos recursivamente el subárbol derecho del nodo actual.

Orden de publicación

En el orden posterior, siempre atravesamos recursivamente el subárbol izquierdo del nodo actual; A continuación, atravesamos recursivamente el subárbol derecho del nodo actual y luego visitamos el nodo actual. El recorrido posterior al orden puede resultar útil para obtener la expresión postfija de un árbol de expresión binaria . ^[33]

Primer orden en profundidad

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

Orden de amplitud primero

En contraste con el orden de profundidad primero, está el orden de amplitud, que siempre intenta visitar el nodo más cercano a la raíz que aún no ha visitado. Consulte búsqueda en amplitud para obtener más información. También llamado 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 transversales 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 desde 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 hacia la izquierda o hacia la derecha, respectivamente. El proceso continúa comprobando sucesivamente el siguiente bit a la derecha hasta que no queden 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 tiempo-espacio entre iterar un árbol binario completo de esta manera versus que cada nodo tenga punteros a sus hermanos.

Ver también

• 2-3 árboles
• 2–3–4 árbol
• árbol AA
• Ahnentafel
• árbol AVL
• árbol B
• Partición del espacio binario
• árbol de huffman
• árbol k-ary
• 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áticas discretas: pruebas, estructuras y aplicaciones, tercera edición. Prensa CRC. pag. 620.ISBN​ 978-1-4398-1280-8.
2. Steven S. Skiena (2009). El manual de diseño de algoritmos. Medios de ciencia y negocios de Springer. pag. 77.ISBN​ 978-1-84800-070-4.
3. Knuth (1997). El arte de la programación informática, volumen 1, 3/E . Educación Pearson. pag. 363.ISBN​ 0-201-89683-4.
4. Iván Flores (1971). Sistema de programación informática/360 . Prentice Hall. pag. 39.
5. Kenneth Rosen (2011). Matemática discreta y sus aplicaciones, 7ª edición . Ciencia de McGraw-Hill. pag. 749.ISBN​ 978-0-07-338309-5.
6. David R. Mazur (2010). Combinatoria: una visita guiada. Asociación Matemática de América. pag. 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. pag. 124.ISBN​ 978-0-7923-4709-5.
8. LR Foulds (1992). Aplicaciones de la teoría de grafos. Medios de ciencia y negocios de Springer. pag. 32.ISBN​ 978-0-387-97599-3.
9. David Makinson (2009). Conjuntos, Lógica y Matemáticas para la Computación . Medios de ciencia y negocios de Springer. pag. 199.ISBN​ 978-1-84628-845-6.
10. Jonathan L. Bruto (2007). Métodos combinatorios con aplicaciones informáticas. Prensa CRC. pag. 248.ISBN​ 978-1-58488-743-0.
11. Kenneth Rosen (2011). Matemática Discreta y sus Aplicaciones 7ª edición . Ciencia de McGraw-Hill. págs. 352–353. ISBN 978-0-07-338309-5.
12. Te Chiang Hu; Man-tak Shing (2002). Algoritmos combinatorios . Publicaciones de Courier Dover. pag. 162.ISBN​ 978-0-486-41962-6.
13. Lih-Hsing Hsu; Cheng-Kuan Lin (2008). Teoría de grafos y redes de interconexión. Prensa CRC. pag. 66.ISBN​ 978-1-4200-4482-9.
14. J. Flum; M. Grohe (2006). Teoría de la Complejidad Parametrizada . Saltador. pag. 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. pag. 76.ISBN​ 978-81-265-0986-7.{{cite book}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
16. "árbol binario completo". NIST .
17. Richard Stanley, Combinatoria enumerativa, volumen 2, p.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) desde el original el 9 de octubre de 2022.
22. Aaron M. Tenenbaum, et al. Estructuras de datos que utilizan C, Prentice Hall, 1990 ISBN 0-13-199746-7 
23. Paul E. Black (ed.), entrada para estructura de datos en 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 online Archivada 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 árbol binario con ilustraciones coloridas". Medio . Consultado el 24 de enero de 2020 .
25. Mehta, Dinesh; Sartaj Sahni (2004). Manual de estructuras y aplicaciones de datos . Chapman y Hall . ISBN 1-58488-435-5.
26. D. Samanta (2004). Estructuras de datos clásicas . PHI Aprendizaje Pvt. Limitado. 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 Kaufman. pag. 347.ISBN​ 978-0-08-092299-7.
28. Introducción a los algoritmos . Cormen, Thomas H., Cormen, Thomas H. (2ª ed.). Cambridge, Massachusetts: MIT Press. 2001. pág. 128.ISBN​ 0-262-03293-7. OCLC  46792720.{{cite book}}: Mantenimiento CS1: otros ( enlace )
29. "Matrices de notación Big O versus inserciones de listas vinculadas". Desbordamiento de pila . Consultado el 4 de julio de 2023 .
30. Laakso, Mikko. "Cola de prioridad y montón binario". Universidad de Aalto . Consultado el 11 de octubre de 2023 .
31. Demaine, Erik. "6.897: Estructuras de datos avanzadas, primavera de 2003, conferencia 12" (PDF) . MIT CSAIL. Archivado desde el original (PDF) el 24 de noviembre de 2005 . Consultado el 14 de abril de 2022 .
32. Estiércol X. Nguyen (2003). "Estructura de árbol binario". arroz.edu . Consultado el 28 de diciembre de 2010 .
33. Wittman, Todd (13 de febrero de 2015). "Conferencia 18: Recorridos 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 . 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 las subsecciones 2.3.1 a 2.3.2 (págs. 318 a 348). 

enlaces externos

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