Árbol binario

Un árbol binario etiquetado de tamaño 9 y altura 3, con un nodo raíz cuyo valor es 1. El árbol anterior es desequilibrado y no se clasifica.

En la informática, una árbol binario es un k-ary ${displaystyle k=2}$ estructura de datos de árboles en la que cada nodo tiene a la mayoría de dos niños, a los que se denomina niño izquierdo y el niño derecho. Una definición recursiva usando nociones de teoría de conjuntos es que un árbol binario (no vacío) es un tuple (L, S, R), donde L y R son árboles binarios o el conjunto vacío y S es un conjunto de un soloton que contiene la raíz. Algunos autores permiten que el árbol binario sea el conjunto vacío también.

Desde la perspectiva de la teoría de grafos, los árboles binarios (y K-arios) como se definen aquí son arborescencias. Por lo tanto, un árbol binario también puede denominarse arborescencia bifurcada, un término que aparece en algunos libros de programación muy antiguos, 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 con raíz. Algunos autores usan árbol binario enraizado en lugar de árbol binario para enfatizar el hecho de que el árbol está enraizado, pero como se definió anteriormente, un árbol binario siempre está enraizado. Un árbol binario es un caso especial de un árbol K-ario ordenado, donde K es 2.

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, pero otros la definen como cada elemento que no es hoja que tiene exactamente dos elementos secundarios y tampoco ordena necesariamente (como izquierda/derecha) a los elementos secundarios.

En informática, los árboles binarios se utilizan de dos formas muy diferentes:

• En primer lugar, como medio de acceder a los nodos basado en algún valor o etiqueta asociada a cada nodo. Los árboles binarios etiquetados de esta manera se utilizan para implementar árboles de búsqueda binaria y montones binarios, y se utilizan para una búsqueda y clasificación eficientes. La designación de nodos no arraigados como niño izquierdo o derecho incluso cuando sólo hay un niño presente en algunas de estas aplicaciones, en particular, es significativa en los árboles de búsqueda binaria. Sin embargo, la disposición de los nodos particulares en el árbol no es parte de la información conceptual. Por ejemplo, en un árbol de búsqueda binaria normal la colocación de los ganglios depende casi enteramente del orden en el que fueron añadidos, y puede ser reorganizado (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 bajo y/o a la izquierda o derecha de otros nodos es parte de la información (es decir, cambiaría el significado). Ejemplos comunes se presentan con codificación Huffman y cladogramas. La división diaria de documentos en capítulos, secciones, párrafos, etc. es un ejemplo análogo con n-ary en lugar de árboles binarios.

Definiciones

Definición recursiva

Para definir realmente un árbol binario en general, debemos permitir la posibilidad de que solo uno de los elementos secundarios esté vacío. Para ello se necesita un artefacto, que en algunos libros de texto se denomina árbol binario extendido. Por lo tanto, un árbol binario extendido se define recursivamente como:

• el conjunto vacío es un árbol binario extendido
• si₁ y T₂ son árboles binarios extendidos, luego denota por T₁ • T₂ el árbol binario extendido obtenido por añadir una raíz r conectado a la izquierda a T₁ y el derecho a la₂ añadiendo bordes cuando estos sub-árboles no son 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.

Uso de 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 lo que para cada nodo se puede definir una noción de hijos como los nodos conectados a él un nivel por debajo. Ordenar estos niños (por ejemplo, dibujándolos en un plano) hace posible distinguir un niño izquierdo de un niño derecho. Pero esto todavía no distingue entre un nodo con hijo izquierdo pero no derecho de uno con hijo derecho pero no izquierdo.

Se puede hacer la distinción necesaria dividiendo primero los bordes, es decir, definiendo el árbol binario como triplete (V, E₁, E₂), donde (V, E₁ ∪ E₂) es un árbol enraizado (equivalentemente arborescencia) y E₁ ∩ E₂ es vacío, y también requiere que para todo j ∈ { 1, 2 } cada nodo tenga como máximo un hijo E_j. 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 para especificar que estos "son todos diferentes" árboles binarios.

Tipos de árboles binarios

La terminología del árbol no está bien estandarizada y, por lo tanto, varía en la literatura.

• A rooted árbol binario tiene un nodo raíz y cada nodo tiene a la mayoría de dos niños.

Un árbol binario completo

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

• A completo árbol binario (a veces referido como un apropiado o avión o estricto árbol binario) es un árbol en el que cada nodo tiene 0 o 2 niños. Otra forma de definir un árbol binario completo es una definición recursiva. Un árbol binario completo es cualquiera:
  • Un solo vértice.
  • Un árbol cuyo nodo raíz tiene dos subárboles, ambos de los cuales son árboles binarios completos.
• A perfecto árbol binario es un árbol binario en el que todos los nodos interiores tienen dos hijos y todas las hojas tienen el mismo profundidad o el mismo nivel. Un ejemplo de un árbol binario perfecto es el diagrama de ancestro (no incestuoso) de una persona a una profundidad determinada, ya que cada persona tiene exactamente dos padres biológicos (una madre y un padre). Siempre que el gráfico de ancestro muestre siempre a la madre y al padre del mismo lado por un nodo dado, su sexo puede ser visto como una analogía de los niños izquierdo y derecho, niños ser entendido aquí como un término algorítmico.
• A completo árbol binario es un árbol binario en el que cada nivel, excepto posiblemente el último, está completamente lleno, y todos los nodos en el último nivel están lo más lejos posible. Puede tener entre 1 y 2^h nodos en el último nivel h. Un árbol perfecto es por lo tanto siempre completo pero un árbol completo no es necesariamente perfecto. Una definición alternativa es un árbol perfecto cuyas hojas más derechas (quizás todas) han sido eliminadas. Algunos autores utilizan el término completo para referirse en su lugar a perfecto árbol binario tal como se define anteriormente, en cuyo caso llaman este tipo de árbol (con un posiblemente no llenado último nivel) casi completo árbol binario o casi completo árbol binario. Un árbol binario completo puede ser representado eficientemente usando un array.

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

• En el infinito completo árbol binario, cada nodo tiene dos niños (y por lo tanto el conjunto de niveles es contablemente infinito). El conjunto de todos los nodos es contablemente infinito, pero el conjunto de todos los caminos infinitos de la raíz es incontable, teniendo la cardinalidad del continuum. Esto se debe a que estos caminos corresponden por una bijeción que conserva el orden a los puntos del conjunto Cantor, o (utilizando el ejemplo de un árbol Stern-Brocot) al conjunto de números irracionales positivos.
• A equilibrado árbol binario es una estructura de árbol binario en la que los subárboles izquierdo y derecho de cada nodo difieren en altura por no más de 1. Uno también puede 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 "más lejos".)
• A degenerado (o patológica) árbol es donde cada nodo padre tiene sólo un nodo de niño asociado. Esto significa que el árbol se comportará como una estructura de datos de lista vinculada.

Propiedades de los árboles binarios

• El número de nodos ${displaystyle n}$ en un árbol binario completo es al menos ${displaystyle 2h+1}$ y en la mayoría ${displaystyle 2^{h+1}-1}$, donde ${displaystyle h}$ es la altura del árbol. Un árbol compuesto por un nodo raíz tiene una altura de 0.
• Número de nodos de hoja ${displaystyle l}$ en un árbol binario perfecto, es ${displaystyle l=(n+1)/2}$ porque el número de nodos no sordos (a.k.a. interna) ${displaystyle n-l=sum _{k=0}{log _{2}(l)-1}2^{k}=2^{log _{2}(l)}-1=l-1}$.
• Esto significa que un árbol binario completo con ${displaystyle l}$ hojas ${displaystyle n=2l-1}$ nodos.
• En un equilibrado árbol binario completo, ${displaystyle h=lceil log _{2}(l)rceil +1=lceil log _{2}(n+1)/2)rceil +1=lceil log _{2}(n+1)rceil }$ (ver función de techo).
• En un perfecto árbol binario completo, ${displaystyle l=2^{h}$ por lo tanto ${displaystyle n=2^{h+1}-1}$.
• El número de enlaces nulos (es decir, niños ausentes de los nodos) en un árbol binario de n nodos esn+1).
• El número de nodos internos en un completo árbol binario de n nodos ${displaystyle lfloor n/2rfloor }$.
• Para cualquier árbol binario no vacío con n₀ nodos de hoja y n₂ nodos de grado 2, n₀ = n₂ + 1.

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 unidos a sus nodos (esto multiplicaría simplemente el número de árboles posibles por un factor fácilmente determinado), y los árboles se distinguen sólo por su estructura; sin embargo, el niño izquierdo y derecho de cualquier nodo se distingue (si son árboles diferentes, entonces intercambiándolos producirá un árbol distinto del original). El tamaño del árbol se toma para ser el número n de los nodos internos (los que tienen dos hijos); los otros nodos son los nodos de 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 paternizar una cadena de n + 1 símbolos (representando hojas) separados por n operadores binarios (representando nodos internos), para determinar las subexpresiones argumentales de cada operador. Por ejemplo n = 3 uno tiene que paréntesisar una cadena como ${displaystyle X*X*X*X*$, que es posible de cinco maneras:

${displaystyle ((X*X)*X)*X,qquad (X*(X*X*))*X,qquad (X*X)*(X*X*),qquad X*(X*X*)*X),qquad 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).

Hay un único árbol binario del tamaño 0 (consistente 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 ${displaystyle C_{n}$ de árboles binarios de tamaño n tiene la siguiente descripción recursiva ${displaystyle C_{0}=1}$, y ${displaystyle textstyle C_{n}=sum ¿Qué?$ para cualquier entero positivo n. De ello se desprende que ${displaystyle C_{n}$ es el número de índice catalán n.

Las cuerdas paréntesis arriba no deben confundirse con el conjunto de palabras de la longitud 2n en el idioma Dyck, que consiste sólo de paréntesis de tal manera que estén correctamente equilibrados. El número de tales cadenas satisface la misma descripción recursiva (cada palabra Dyck de longitud 2n es determinado por el subpalabra Dyck encerrado por el inicial '(' y su emparejado ')' junto con el subpalabra Dyck que permanece después de ese paréntesis de cierre, cuyas longitudes 2i y 2j satisfacer satisfacción i + j + 1 = n); este número es por tanto también el número catalán ${displaystyle C_{n}$. Así que también hay cinco palabras Dyck de la longitud 6:

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

Estas palabras Dyck no corresponden a los árboles binarios de la misma manera. En su lugar, están relacionados con la siguiente bijeción repetitivamente definida: la palabra Dyck igual a la cadena vacía corresponde al árbol binario del tamaño 0 con sólo una hoja. Cualquier otra palabra Dyck se puede escribir como (${displaystyle ¿Qué?$)${displaystyle w_{2}$, donde ${displaystyle ¿Qué?$,${displaystyle w_{2}$ son ellos mismos (posiblemente vacíos) Dyck palabras y donde los dos paréntesis escritos son iguales. La bijeción se define entonces dejando las palabras ${displaystyle ¿Qué?$ y ${displaystyle w_{2}$ corresponden a los árboles binarios que son los niños izquierdo y derecho de la raíz.

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

Métodos para almacenar árboles binarios

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

Nodos y referencias

En un lenguaje con registros y referencias, los árboles binarios normalmente se construyen teniendo una estructura de nodo de árbol que contiene algunos datos y referencias a su hijo izquierdo y 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 nodo 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 enhebrado.

En lenguajes con uniones etiquetadas como ML, un nodo de árbol suele ser 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 una "hoja" nodo, 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 de ML) define un árbol binario que almacena un carácter en cada nodo.

Tipo chr_tree = Vacío Silencio Node de char * chr_tree * chr_tree

Arreglos

Los árboles binarios también se pueden almacenar en orden panorámico como una estructura de datos implícita en arrays, y si el árbol es un árbol binario completo, este método no desperdicia espacio. En este arreglo compacto, si un nodo tiene un índice i, sus hijos se encuentran en índices ${displaystyle 2i+1}$ (para el niño izquierdo) y ${displaystyle 2i+2}$ (para la derecha), mientras que su padre (si lo hay) se encuentra en el índice ${displaystyle leftlfloor {frac Está bien.$ (suponiendo que la raíz tiene índice cero). Alternativamente, con una matriz de 1 índice, la aplicación se simplifica con los niños encontrados ${displaystyle 2i}$ y ${displaystyle 2i+1}$, y padre encontrado en ${displaystyle lfloor i/2rfloor }$. Este método se beneficia de un almacenamiento más compacto y de una mejor localización de referencia, especialmente durante una transversal preordenada. Sin embargo, es caro crecer y desperdicia espacio proporcional a 2^h - n para un árbol de profundidad h con n nodos.

Este método de almacenamiento se usa a menudo para montones binarios.

Codificaciones

Codificaciones sucintas

Una estructura de datos sucinta es la que ocupa cerca del espacio mínimo posible, según lo establecido por la información teórico límites inferiores. El número de diferentes árboles binarios en ${displaystyle n}$ nodos ${displaystyle mathrm {C} _{n}$, el ${displaystyle n}$el número catalán (asumiendo que vemos árboles con idénticos estructura como idéntico). Para grandes ${displaystyle n}$, esto es sobre ${displaystyle 4^{n}$; por lo tanto necesitamos al menos ${displaystyle log _{2}4^{n}=2n}$ bits para codificarlo. Por lo tanto, un árbol binario sucinto ocuparía ${displaystyle 2n+o(n)}$ bits.

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

función EncodeSuccinct(nodos No. Bitstring estructura, array datos) {
 si n = Nil entoncesa) Apéndice 0 a la estructura;
 mása) Apéndice 1 a la estructura;
a) Apéndice n.data a los datos;
EncodeSuccinct(n.left, structure, data);
EncodeSuccinct(n.right, structure, data);
}

La cuerda estructura sólo ${displaystyle 2n+1}$ pedazos al final, donde ${displaystyle n}$ 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 como este:

función DecodeSuccinct(Bitstring estructura, array datos) {
quitar el primer pedazo de estructura y ponerlo en b si b = 1 entoncescrear un nuevo nodo neliminar el primer elemento de datos y ponerlo en n.data
n.left = DecodeSuccinct(estructura, datos)
n.right = DecodeSuccinct(estructura, datos)
 retorno n
 más retorno Nil
}

Las representaciones sucintas más sofisticadas permiten no solo el almacenamiento compacto de árboles, sino también operaciones útiles en esos árboles directamente mientras todavía están en su forma sucinta.

Codificación de árboles generales como árboles binarios

Existe un mapeo uno a uno entre los árboles ordenados generales y los árboles binarios, que Lisp utiliza en particular para representar árboles ordenados generales como árboles binarios. Para convertir un árbol ordenado general en un árbol binario, solo necesitamos representar el árbol general en forma de hermano derecho del hijo izquierdo. El resultado de esta representación será automáticamente un árbol binario si se ve desde una perspectiva diferente. Cada nodo N en el árbol ordenado corresponde a un nodo N' en el árbol binario; el hijo izquierdo de N' es el nodo correspondiente al primer hijo de N, y el hijo derecho de N' es el nodo correspondiente al siguiente hermano de N' --- es decir, el siguiente nodo en orden entre los hijos del padre de N. Esta representación de árbol binario de un árbol de orden general a veces también se denomina árbol binario de hijo izquierdo y hermano derecho (también conocido como árbol LCRS, árbol doblemente encadenado, cadena de herederos filiales).

Una forma de pensar en esto es que los hijos de cada nodo están en una lista enlazada, encadenados junto con sus campos derechos, y el nodo solo tiene un puntero al principio o encabezado. de esta lista, a través de su campo izquierdo.

Por ejemplo, en el árbol de la izquierda, A tiene los 6 hijos {B,C,D,E,F,G}. Se puede convertir en el árbol binario de la derecha.

El árbol binario se puede considerar como el árbol original inclinado hacia un lado, con los bordes negros a la izquierda que representan al primer hijo y los bordes azules a la derecha que representan al próximo hermano. Las hojas del árbol de la izquierda se escribirían en Lisp como:

(N O) I J) C D (P) (Q))) F (M))

que se implementaría en la memoria como el árbol binario de la derecha, sin letras en los nodos que tienen un hijo izquierdo.

Operaciones comunes

Las rotaciones de árboles son operaciones internas muy comunes en árboles binarios auto-balancing.

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 pueden insertarse 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á el 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 el nodo A como su padre.

Nodos internos

El proceso de insertar un nodo en un árbol binario

La inserción en los nodos internos es un poco más compleja que en los 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 de manera similar con una inserción del 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.

Eliminació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 sin ambigüedades.

Nodo con cero o un hijo

El proceso de eliminación de un nodo interno en un árbol binario

Suponga que el nodo que se va a eliminar es el nodo A. Si A no tiene elementos secundarios, la eliminación se logra estableciendo el elemento secundario del elemento principal de A en nulo. Si A tiene un hijo, establezca 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 hijas

En un árbol binario, un nodo con dos hijos no se puede eliminar sin ambigüedades. Sin embargo, en ciertos árboles binarios (incluidos los árboles de búsqueda binarios) estos nodos pueden eliminarse, aunque con una reorganización de la estructura del árbol.

Transversal

Los recorridos en orden previo, en orden y posterior al orden visitan cada nodo en un árbol visitando recursivamente cada nodo en los subárboles izquierdo y derecho de la raíz.

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 un elemento secundario de un nodo que ya hemos visitado. A diferencia de una búsqueda profunda 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.

Primer orden en amplitud

En contraste con el orden primero en profundidad está el orden primero en amplitud, que siempre intenta visitar el nodo más cercano a la raíz que aún no ha visitado. Consulte la búsqueda en amplitud para obtener más información. También llamado recorrido de orden de niveles.

En un árbol binario completo, el índice de amplitud de un nodo (i − (2^d − 1)) puede utilizarse como instrucciones transversales desde la raíz. Lectura 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 en sí (d > 0). Cuando el índice de amplitud está enmascarado en el bit d − 1, los valores de bit 0 y 1 significa dar un paso 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 propio nodo. Hay una compensación de espacio-tiempo entre iterar un árbol binario completo de esta manera versus cada nodo que tiene puntero/s a su hermano/s.