Árboles y árboles: sistemas complejos e IA

contenido

Árboles y arborescencias

Los árboles y las arborescencias son gráficos particulares que se usan a menudo para representar elayuda con la decisión, datos, o para calcular la complejidad.

Un árbol es un conjunto organizado de nodos en el que cada nodo tiene un padre y uno, excepto un nodo que llamamos raíz. Si un nodo pag es el padre del nudo F, entonces F es un hijo de pag; si F no tiene hijo, entonces ella es una hoja. Es posible almacenar cualquier tipo de información en nodos o enlaces.

Terminología

Un nodo se define por su etiqueta y sus subárboles. Por tanto, es posible representar un árbol mediante una tupla <e,a₁,…,Para_k> en el cual mi es la etiqueta del nodo y Para_I son sus subárboles.

Por ejemplo, las calculadoras organizan las expresiones Matemáticas dependiendo de la prioridad de los operadores y su profundidad: (y/2 – x)*(75+z) será representado por <*,<-,,>,>,<+,,>>. La operación se realiza entonces mediante un recorrido particular del árbol:

los descendientes de un nodo son los nodos de sus subárboles;
un antepasado de un nodo es su padre o un antepasado de su padre;
la ruta de un nodo a la raíz está formada por todos sus antepasados;
el hermano de un nodo es un hijo de su padre que no es él mismo.

Un árbol es a menudo representado por un grafico para facilitar la lectura:

Los nodos de un árbol se distribuyen por lo más hondo (o niveles). La profundidad 0 contiene solo la raíz, la profundidad 1 sus hijos, etc. los altura de un árbol es el número de profundidades, o el tamaño del camino más largo desde un nodo hasta la raíz.

Definición: teoría de grafos

Dado un gráfico no dirigido que comprende no vértices, las siguientes propiedades son equivalentes:

El gráfico está conectado y sin ciclo,
El gráfico no tiene ciclos y tiene n-1 aristas,
El gráfico está conectado y admite n-1 aristas,
El gráfico no tiene ciclos y, al agregar un borde, creamos uno y solo un ciclo elemental,
El gráfico está conectado y, al eliminar cualquier borde, ya no está conectado,
Hay una cadena y solo una entre todos los pares de vértices.

Un árbol es un gráfico dirigido sin circuito que admita una raíz, de modo que para cualquier otro vértice existe un camino único desde la raíz hasta este vértice. Un árbol tiene propiedades similares a las de un árbol.

Árbol binario

En un árbol binario, cada nodo tiene un hijo izquierdo y un hijo derecho, que pueden ser cero subárboles. Un árbol binario está completo si todas sus hojas tienen la misma profundidad y todos sus nodos que no son hojas tienen dos hijos.

Determinemos el número total de hojas y nodos de un árbol binario completo.

En la profundidad 0 hay una hoja, la raíz. Suponga que el árbol binario completo tiene 2^(h-1) deja la tarea h. Entonces, a la altura h + 1, cada una de estas hojas se convierte en un nodo con dos hilos, por lo que tenemos un número de hojas de 2 * 2^(h-1) = 2^h. CQFD.

Además, el número de nodos del gráfico binario completo es igual a la suma del número de hojas de los árboles binarios completos de menor altura. Deducimos que el número total de nodos es ∑_{(i = 0)}^(h-1) 2^I = 2^h -1. Por el contrario, si un gráfico binario completo tiene n nodos, entonces su altura está de acuerdo con la fórmula anterior log₂ (n) +1. Deducimos que cualquier árbol binario tiene al menos una altura de registro₂ (n) +1.

Un árbol binario balanceado o árbol AVL es un árbol binario tal que las alturas de los dos subárboles de cualquier nodo en el árbol difieren como máximo en 1. Un subárbol de un árbol AVL también es un árbol AVL.

El indicador de los vértices muestra la diferencia entre la altura del subárbol izquierdo y la altura del subárbol derecho.

Cuando el árbol está desequilibrado, es necesario intercambiar los vértices principales y la raíz mientras se mantiene el orden de los subárboles (consulte la continuación de los árboles de investigación).

Podemos ampliar la definición en árboles de mayor grado (árbol ternario, etc.). Solo el coeficiente 2 se modifica según el número de hilos definido por el tipo de eje.

Árbol de investigación

Un árbol de búsqueda es una estructura de datos que permite representar un conjunto de valores si tenemos una relación de orden sobre ellos. Las operaciones estándar en los árboles de búsqueda son: insertar, eliminar o encontrar un valor. Estas operaciones son económicas si el eje está equilibrado. Para facilitar la comprensión, trabajaremos en árboles de búsqueda binaria (ABR).

Sea un conjunto de valores mi provisto de una relación de pedido, y PARA un árbol binario. El árbol PARA es un ABR de mi si para cualquier nodo pag de PARA, El valor de pag es estrictamente mayor que los valores de su subárbol izquierdo y es estrictamente menor que los valores de su subárbol derecho; siempre que los valores sean únicos. Los valores se llaman teclas.

El valor más pequeño es el último descendiente izquierdo de la raíz y el mayor es el último descendiente derecho de la raíz. Otros criterios lógicos se pueden deducir de la definición:

A continuación, las tres acciones se llevan a cabo a través de rutas ABR.