Introducción a los árboles

Treees una estructura discreta que representa relaciones jerárquicas entre elementos o nodos individuales. Un árbol en el que un padre no tiene más de dos hijos se llama árbol binario.

Árbol y sus propiedades

Definition- Un árbol es un gráfico no dirigido acíclico conectado. Existe una ruta única entre cada par de vértices en $ G $. Un árbol con N número de vértices contiene $ (N-1) $ número de aristas. El vértice que es de 0 grados se llama raíz del árbol. El vértice que es de 1 grado se llama nodo hoja del árbol y el grado de un nodo interno es al menos 2.

Example - El siguiente es un ejemplo de un árbol -

Centros y bi-centros de un árbol

El centro de un árbol es un vértice con una excentricidad mínima. La excentricidad de un vértice $ X $ en un árbol $ G $ es la distancia máxima entre el vértice $ X $ y cualquier otro vértice del árbol. La excentricidad máxima es el diámetro del árbol. Si un árbol tiene solo un centro, se llama Árbol Central y si un árbol tiene solo más de un centro, se llama Árbol Bi-central. Cada árbol es central o bi-central.

Algoritmo para encontrar centros y bi-centros de un árbol

Step 1 - Eliminar todos los vértices de grado 1 del árbol dado y también eliminar sus bordes incidentes.

Step 2- Repita el paso 1 hasta que quede un solo vértice o dos vértices unidos por un borde. Si se deja un solo vértice, entonces es el centro del árbol y si se dejan dos vértices unidos por un borde, entonces es el bi-centro del árbol.

Problem 1

Descubra el centro / bi-centro del siguiente árbol -

Solution

Al principio, eliminaremos todos los vértices de grado 1 y también eliminaremos sus bordes incidentes y obtendremos el siguiente árbol:

Nuevamente, eliminaremos todos los vértices de grado 1 y también eliminaremos sus bordes incidentes y obtendremos el siguiente árbol:

Finalmente obtuvimos un solo vértice 'c' y detenemos el algoritmo. Como hay un solo vértice, este árbol tiene un centro 'c' y el árbol es un árbol central.

Problem 2

Descubra el centro / bi-centro del siguiente árbol -

Solution

Al principio, eliminaremos todos los vértices de grado 1 y también eliminaremos sus bordes incidentes y obtendremos el siguiente árbol:

Nuevamente, eliminaremos todos los vértices de grado 1 y también eliminaremos sus bordes incidentes y obtendremos el siguiente árbol:

Finalmente, obtuvimos dos vértices 'c' y 'd', por lo tanto, detenemos el algoritmo. Como quedan dos vértices unidos por un borde, este árbol tiene 'cd' bi-central y el árbol es bi-central.

Árboles etiquetados

Definition- Un árbol etiquetado es un árbol a cuyos vértices se les asignan números únicos del 1 al n. Podemos contar dichos árboles para valores pequeños de n a mano para conjeturar una fórmula general. El número de árboles etiquetados de n número de vértices es $ n ^ {n-2} $. Dos árboles etiquetados son isomorfos si sus gráficos son isomorfos y los puntos correspondientes de los dos árboles tienen las mismas etiquetas.

Ejemplo

Árboles sin etiquetar

Definition- Un árbol sin etiqueta es un árbol cuyos vértices no tienen asignado ningún número. El número de árboles etiquetados de n número de vértices es $ \ frac {(2n)!} {(N + 1)! N! } $ ( ^enésimo número catalán)

Ejemplo

Árbol enraizado

Un árbol enraizado $ G $ es un gráfico acíclico conectado con un nodo especial que se denomina raíz del árbol y cada borde se origina directa o indirectamente desde la raíz. Un árbol enraizado ordenado es un árbol enraizado donde se ordenan los hijos de cada vértice interno. Si cada vértice interno de un árbol enraizado no tiene más de m hijos, se llama árbol m-ario. Si cada vértice interno de un árbol enraizado tiene exactamente m hijos, se le llama árbol completo m-ario. Si $ m = 2 $, el árbol enraizado se llama árbol binario.

Árbol de búsqueda binaria

El árbol de búsqueda binaria es un árbol binario que satisface la siguiente propiedad:

$ X $ en el subárbol izquierdo del vértice $ V, Valor (X) \ le Valor (V) $
$ Y $ en el subárbol derecho del vértice $ V, Valor (Y) \ ge Valor (V) $

Entonces, el valor de todos los vértices del subárbol izquierdo de un nodo interno $ V $ son menores o iguales a $ V $ y el valor de todos los vértices del subárbol derecho del nodo interno $ V $ son mayores o iguales a $ V $. El número de enlaces desde el nodo raíz al nodo más profundo es la altura del árbol de búsqueda binaria.

Ejemplo

Algoritmo para buscar una clave en BST

BST_Search(x, k) 
if ( x = NIL or k = Value[x] ) 
   return x; 
if ( k < Value[x]) 
   return BST_Search (left[x], k); 
else  
   return BST_Search (right[x], k)

Complejidad del árbol de búsqueda binaria

	Caso promedio	Peor de los casos
Complejidad espacial	En)	En)
Complejidad de búsqueda	O (log n)	En)
Complejidad de inserción	O (log n)	En)
Complejidad de eliminación	O (log n)	En)