Árbol binario



Toda la información completa que se ha podido reunir sobre Árbol binario ha sido escrupulosamente examinada y organizada con la finalidad de que te resulte altamente provechosa. Posiblemente no erramos si decimos que has llegado hasta esta web buscando conocer algo más acerca de Árbol binario. Con frecuencia es común extraviarse por la red en la espesa jungla de páginas web que hablan sobre Árbol binario y que, no obstante, no aportan aquello que esperamos conocer en relación con Árbol binario. Es por ello que deseamos que si los datos que te ofrecemos a continuación acerca de Árbol binario es de tu agrado, nos dejes un comentario. Asimismo, si la información acerca de Árbol binario que te proporcionamos no es lo que necesitas, también ponlo en nuestro conocimiento, así nos será posible mejorar día a día este sitio web.

En informática , un árbol binario es una estructura de datos que se puede representar en forma de una jerarquía en la que cada elemento se denomina nodo , y el nodo inicial se denomina raíz . En un árbol binario, cada elemento tiene como máximo dos elementos secundarios en el nivel inferior, generalmente llamados izquierda y derecha . Desde el punto de vista de estos elementos hijos, el elemento del que descienden en el nivel superior se llama padre .

En el nivel más alto, nivel 0, hay un nodo raíz. En el nivel directamente debajo, hay como máximo dos nodos secundarios. Al continuar descendiendo a los niveles inferiores, uno puede tener cuatro, luego ocho, dieciséis, etc. es decir, la secuencia de las potencias de dos . Un nodo sin hijos se llama hoja .

El nivel de un nodo, en otras palabras, la distancia entre ese nodo y la raíz, se llama profundidad . La altura del árbol es la profundidad máxima de un nodo. Un árbol reducido a un solo nodo tiene una altura de 1.

Los árboles binarios se pueden utilizar en particular como un árbol de búsqueda binario o como un montón binario .

Definición en teoría de grafos

La teoría de grafos utiliza la siguiente definición: un árbol binario es un grafo conectado acíclico , tal como el grado de cada nodo (o vértice) es como máximo 3.

La raíz de un árbol binario es el nodo de un gráfico de grado máximo 2. Con una raíz así elegida, cada nodo tendrá un padre definido único y dos hijos; sin embargo, esta información es insuficiente para distinguir un hijo derecho de un hijo izquierdo. Si descuidamos esta condición de conexión, y hay múltiples elementos conectados, llamaremos a esta estructura un bosque.

Tipos de árboles binarios

  • Un árbol binario (o binario-unario) es un árbol con una raíz en la que cada nodo tiene como máximo dos hijos.
  • Un árbol binario estricto o localmente completo es un árbol en el que todos los nodos tienen cero o dos hijos.
  • Un árbol binario degenerado es un árbol en el que todos los nodos internos tienen un solo hijo. Este tipo de árbol tiene una sola hoja y puede verse como una lista vinculada.
  • Un árbol binario perfecto es un árbol binario estricto en el que todas las hojas (nodos sin hijos) están a la misma distancia de la raíz (es decir, la misma profundidad). Este es un árbol con todos los niveles llenos: donde todos los nodos internos tienen dos hijos y donde todos los nodos externos tienen la misma altura.
  • Un árbol binario completo o casi completo , que no debe confundirse con localmente completo (arriba), es un árbol en el que se llenan todos los niveles con la posible excepción del último, en el que las hojas se alinean a la izquierda. Podemos verlo como un árbol perfecto cuyo último nivel se habría visto privado de algunas de sus hojas partiendo de la más derecha. Otra forma de verlo sería un árbol binario estricto en el que las hojas tienen una profundidad n o n-1 para un n dado. La eventualidad es importante: un árbol perfecto es necesariamente casi completo, mientras que un árbol casi completo puede ser perfecto.

Hay usos contradictorios de los términos completo y perfecto , que pueden usarse como se describió anteriormente, pero que a veces pueden intercambiarse. Esto puede crear confusión o malentendidos, por lo que podemos optar por utilizar el término casi completo para referirnos a un árbol en el último nivel que posiblemente no esté lleno. También pueden existir confusiones entre el francés y el inglés, en los que encontramos los términos perfectos y completos , nuevamente con diferentes usos según la persona.

Método para almacenar árboles binarios

Los árboles binarios se pueden construir a partir de primitivas de un lenguaje de programación de varias formas. En un lenguaje con estructuras y punteros (o referencias ), los árboles binarios pueden diseñarse teniendo una estructura de tres nodos que contiene algunos datos y punteros a su hijo derecho y al hijo izquierdo. El orden que esto impone a los nodos secundarios a veces es útil, en particular para rutas infijas. A veces también contiene un puntero a su único padre. Si un nodo tiene menos de dos hijos, a uno de los dos punteros se le puede asignar el valor especial cero; también puede apuntar a un ganglio centinela.

Los árboles binarios también se pueden organizar en matrices, y si el árbol es un árbol binario completo, este método no desperdicia espacio y los datos estructurados resultantes se denominan montones . En esta disposición compacta, un nodo tiene un índice i , y (la matriz se basa en ceros) sus hijos están en los índices 2 i +1 y 2 i +2, mientras que su padre está (si existe) en el índice de piso ( i-1) / 2) . Este método permite beneficiarse de una huella más pequeña y una mejor referencia, en particular durante un escaneo de prefijo. Sin embargo, requiere una memoria contigua, es caro si se trata de extender el árbol y el espacio perdido (en el caso de un árbol binario incompleto) es proporcional a 2 h - n para un árbol de profundidad h con n nodos .

Un pequeño árbol binario completo contenido en una matriz.

En los lenguajes de unión etiquetados como ML , un nodo es a menudo una unión etiquetada de dos tipos de nodos, uno es un triplete que contiene datos y sus elementos secundarios derecho e izquierdo, y el otro es un nodo vacío, que no contiene datos ni funciones, parecido el valor nulo de los idiomas con punteros.

Método de iteración de árbol binario

A menudo, es deseable visitar cada uno de los nodos de un árbol y examinar el valor allí. Hay varios órdenes en los que se pueden visitar los nodos, y cada uno tiene propiedades útiles que son explotadas por algoritmos basados ​​en árboles de bits.

Ruta de prefijo, infijo y sufijo

(a veces llamado preorder , inorder y postorder )

Considere un árbol Ade tipo Arbre, raíz racine(A)y sus dos hijos gauche(A)y droite(A). Podemos escribir las siguientes funciones (observe la posición de la línea visiter (A)):

Ruta de prefijo

visiterPréfixe(Arbre A) :
    visiter (A)
    Si nonVide (gauche(A))
          visiterPréfixe(gauche(A))
    Si nonVide (droite(A))
          visiterPréfixe(droite(A))

Esto muestra los valores del árbol en orden de prefijo. En este orden, se visita cada nodo y luego cada uno de sus hijos.

Ruta de sufijo o sufijo

visiterPostfixe(Arbre A) :
    Si nonVide(gauche(A))
       visiterPostfixe(gauche(A))
    Si nonVide(droite(A))
       visiterPostfixe(droite(A))
    visiter(A)

En una ruta de sufijo o sufijo, mostramos cada nodo después de mostrar cada uno de sus hijos.

Curso infijo

visiterInfixe(Arbre A) :
    Si nonVide(gauche(A))
       visiterInfixe(gauche(A))
    visiter(A)
    Si nonVide(droite(A))
       visiterInfixe(droite(A))

Una caminata infija, como arriba, visita cada nodo entre los nodos de su subárbol izquierdo y los nodos de su subárbol derecho. Esta es una forma bastante común de iterar a través de un árbol de búsqueda binario, ya que devuelve los valores en orden ascendente.

Para entender por qué este es el caso, si n es un nodo en un árbol de búsqueda binario, entonces todos los elementos del subárbol izquierdo del nodo n serán menores que ny los del subárbol derecho serán mayores o iguales an . Ainsi, si nous visitons le sous-arbre de gauche dans l'ordre, de manière récursive, puis que nous visitons n , et que nous visitons le sous-arbre de droite, nous aurons visité l'ensemble du sous-arbre enraciné en n en el orden.

Un ejemplo simple de un árbol binario En este árbol binario
  • Representación del prefijo de ruta: 1, 2, 4, 5, 7, 8, 3, 6, 9
  • Renderizar la ruta prefijada: 4, 7, 8, 5, 2, 9, 6, 3, 1
  • Render de la ruta infija: 4, 2, 7, 5, 8, 1, 3, 9, 6
  • Representación de la ruta en ancho: 1, 2, 3, 4, 5, 6, 7, 8, 9

Podemos realizar estas rutas con un lenguaje funcional como Haskell con el siguiente código:

data Tree a = Leaf | Node(a, Tree a, Tree a)

preorder Leaf = []
preorder (Node (x, left,right)) = [x] ++ (preorder left) ++ (preorder right)

postorder Leaf = []
postorder (Node (x, left,right)) = (postorder left) ++ (postorder right) ++ [x]

inorder Leaf = []
inorder (Node (x, left,right)) = (inorder left) ++ [x] ++ (inorder right)

Todos estos algoritmos recursivos utilizan una pila de memoria proporcional a la profundidad de los árboles. Si agregamos en cada nodo una referencia a su padre, entonces podemos implementar todas estas rutas usando solo espacios de memoria constantes y un algoritmo iterativo. Sin embargo, la referencia al padre ocupa mucho espacio; solo es realmente útil si se requiere de otra manera o si la pila de memoria es particularmente limitada. Aquí está, por ejemplo, el algoritmo iterativo para la ruta de infijo:

VisiterInfixeIteratif(racine)
    precedent    := null
    actuel       := racine
    suivant      := null

    Tant que (actuel != null) Faire
        Si (precedent == pere(actuel)) Alors
            precedent := actuel
            suivant   := gauche(actuel)
        FinSi
        Si (suivant == null OU precedent == gauche(actuel)) Alors
            Visiter(actuel)
            precedent := actuel
            suivant   := droite(actuel)
        FinSi
        Si (suivant == null OU precedent == droite(actuel)) Alors
            precedent := actuel
            suivant   := pere(actuel)
        FinSi
        actuel := suivant
    FinTantQue

Curso en profundidad

Con este paseo siempre intentamos visitar el nodo más alejado de la raíz que podamos, siempre que sea hijo de un nodo que ya hayamos visitado. A diferencia de la navegación en profundidad en gráficos, no es necesario saber qué nodos ya han sido visitados, porque un árbol no contiene ciclos. Las rutas de prefijo, infijo y sufijo son casos especiales de este tipo de ruta.

Para realizar este viaje, es necesario mantener una lista de elementos en espera de procesamiento. En el caso de la navegación en profundidad, esta lista debe tener una estructura de pila (del tipo LIFO, Last In, First Out, es decir: “last in, first out”). En esta implementación, también elegiremos agregar los hijos de un nodo de derecha a izquierda.

ParcoursProfondeur(Arbre A) {
   S = Pilevide
   ajouter(Racine(A), S)
   Tant que (S != Pilevide) {
       nœud = premier(S)
       retirer(S)
       Visiter(nœud) //On choisit de faire une opération
       Si (droite(nœud) != null) Alors
           ajouter(droite(nœud), S)
       Si (gauche(nœud) != null) Alors
           ajouter(gauche(nœud), S)
   }
}

Curso de ancho

A diferencia del anterior, este sendero siempre intenta visitar el nodo más cercano a la raíz que aún no ha sido visitado. Siguiendo esta ruta, primero visitaremos la raíz, luego los nodos en la profundidad 1, luego 2, etc. De ahí el nombre del curso en ancho.

La implementación es casi idéntica a la de la ruta en profundidad excepto que esta vez debemos usar una estructura de cola (tipo FIFO, First in, first out en otras palabras "first in, first out"), lo que implica que el orden de salida no es lo mismo (es decir, cambiamos de izquierda a derecha en nuestro procesamiento).

ParcoursLargeur(Arbre A) {
   f = FileVide
   enfiler(Racine(A), f)
   Tant que (f != FileVide) {
       nœud = defiler(f)
       Visiter(nœud)                        //On choisit de faire une opération
       Si (gauche(nœud) != null) Alors
           enfiler(gauche(nœud), f)
       Si (droite(nœud) != null) Alors
           enfiler(droite(nœud), f)
   }
}

Transformación de cualquier árbol en un árbol binario

Hay una inyección entre árboles ordenados en general y árboles binarios, que Lisp utiliza especialmente para representar árboles ordenados en general como árboles binarios. Cada nodo N en el árbol ordenado corresponde al nodo N 'en el árbol binario; el hijo izquierdo de N 'es el nodo para el primer hijo de N , y el hijo derecho de N ' es el nodo para el siguiente hermano del N - que es el siguiente nodo en el orden entre los hijos del padre de N .

Una forma de imaginarse esto es pensar que cada hijo de un nodo en una lista vinculada, cada uno vinculado por sus deberes de campo , y que el nodo solo tiene un puntero al principio de la lista, a su campo izquierdo.

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

Un ejemplo de conversión de un árbol arbitrario en un árbol binario

Este árbol binario puede considerarse como el árbol original inclinado en longitud, con los lados negros a la izquierda representando a los primeros hijos y los lados azules a la derecha representando a sus próximos hermanos . La parte del árbol de la izquierda podría codificarse en Lisp así:

(((MN) HI) CD ((O) (P)) F (L))

que podría implementarse en la memoria como el árbol binario derecho, sin las letras de los nodos que tienen un hijo izquierdo.

Ver también

Algoritmos que utilizan árboles binarios

Árboles binarios particulares

Otros tipos de arboles

Notas y referencias

De momento esta es toda la documentación que hemos logrado recopilar sobre Árbol binario, deseamos que haya satisfecho tus necesidades. Si es así, por favor, no obvies promovernos entre tus allegados y personas de la familia, y no olvides que quedamos a tu disposición siempre que lo necesites. Si pese a poner todo nuestro empeño, crees que lo que hemos recopilado acerca de Árbol binario dispone de alguna incorrección o hay información nueva que debe ser añadida o corregir, nos resultaría una valiosísima aportación que que nos lo indiques. Proporcionar la mejor y mayor información en relación con Árbol binario y acerca de cualquier otra cuestión es donde reside el espíritu de esta página web; nos mueve el mismo aliento que a la sazón incentivó a los creadores de la formulación de la Enciclopedia, y por eso lo que deseamos es que aquello que has hallado en esta Gran Enciclopedia en relación con Árbol binario te haya resultado útil para intensificar tus conocimientos.

Opiniones de nuestros usuarios

Maria Mar Guerrero Nieto

Me ha encantado encontrar este artículo sobre Árbol binario.

Beatriz Lopez Bermejo

Gracias. El artículo acerca de Árbol binario me sirvió.