Búsqueda en Árboles Binarios

Búsqueda en Árboles

• La búsqueda en árboles es un proceso clave en estructuras de datos para localización eficiente, usado principalmente en árboles de búsqueda binaria.
• El objetivo es el manejo de datos a nivel computacional, derivado en funciones específicas.
• La función "Buscar, encontrar" tiene la fórmula f(n) = O(log2n) y se relaciona con el concepto de Arreglo Lineal Ordenado.
• La función "Insertar y eliminar datos" tiene la fórmula f(n) = O(n) y se relaciona con el concepto de Lista Ligada.
• En un árbol binario denotado por T, N representa un nodo, M denota cualquier nodo dependiendo del valor del árbol binario.
• Si T es 45 y el nodo N es 35, el subárbol irá a la izquierda; si es 55, irá a la derecha.
• En un árbol binario con n nodos y profundidad d, f(n) denota el tiempo de ejecución, no excediendo la profundidad d, dependiendo el tiempo de ejecución f(n) de la profundidad d del árbol T.
• Encontrar una subgráfica T de una gráfica G, donde T es un árbol con todos los vértices de G, se conoce como árbol de expansión.
• Los métodos para encontrar árboles de expansión se aplican a otros problemas.

Búsqueda e Inserción

• Solo se especifica para árboles binarios.
• El proceso de búsqueda consta de dos etapas condicionales, buscando un ítem específico de información en un árbol binario.
• La primera etapa ubica el ITEM, considerando las ramificaciones (mayor o menor que N).
• La segunda etapa inicia el proceso de búsqueda tras la comparación e inserción, dividiéndose en dos condiciones: coincidencia con un nodo (M) o no encontrar datos relacionados.
• El ítem buscado debe estar entre dos nodos para ser encontrado, o al menos ser el más próximo.

Eliminación de Datos

• La eliminación implica una combinación de procesos.
• Primer paso: Se utiliza el algoritmo de búsqueda de árboles binarios para encontrar el nodo principal (f(n) = O(log2n)). Si no se encuentra, el proceso se detiene.
• Segundo paso, existen tres posibles resultados:
  • A. El nodo no tiene ramificaciones, eliminándose directamente.
  • B. Si tiene una ramificación, el nodo subsiguiente sustituye al nodo eliminado.
  • C. Si el nodo tiene dos ramificaciones, el nodo más próximo sustituye al nodo a eliminar.

Árboles Binarios Completos

• Un árbol binario completo tiene estas características:
  • Todos los niveles, excepto el último, están llenos, con cada nodo teniendo dos hijos (izquierdo y derecho).
  • En el último nivel, los nodos están lo más a la izquierda posible, sin espacios vacíos.
  • La estructura es balanceada, con la altura del árbol siendo la más baja posible.

Árboles Binarios Extendidos

• Un árbol binario T es extendido si cada nodo tiene 0 o 2 hijos.
• Para elaborar un árbol binario extendido, se sustituye cada subárbol por un nuevo nodo.
• Los nodos originales son los nodos internos del nuevo árbol extendido
• Si un árbol binario tiene n nodos, el árbol binario extendido tendrá:
  • n nodos internos
  • n + 1 nodos externos
• Para conseguirlo:

1. Sustituir cada subárbol vacío por un nuevo nodo.
2. El árbol original se convierte en los nodos internos, cada uno con al menos dos hijos.
3. Se aplica la fórmula n + 1 nodos externos.

Tipos de Búsquedas

Búsqueda en Profundidad

• Se expande cada nodo de forma recurrente desde el nodo padre al nodo hijo.
• Si no quedan nodos por visitar, se regresa al nodo predecesor y repite el proceso con los vecinos del nodo.
• La búsqueda concluye si se encuentra el nodo antes de recorrer todos los nodos.

Búsqueda en Anchura

• Se procesan todos los vértices en un nivel antes de pasar al siguiente nivel en la búsqueda.

Aplicaciones y Algoritmos

• Las búsquedas a profundidad y a lo ancho son la base de algoritmos de gráficas.
• Ambas pueden determinar si una gráfica es conexa (si se puede visitar cada vértice desde un vértice inicial).
• La búsqueda a profundidad puede usarse como algoritmo de búsqueda, llamándose "de regreso".

Árboles de Expansión Mínima

• El algoritmo de Prim construye un árbol agregando aristas iterativamente hasta obtener un árbol de expansión mínima, comenzando con un solo vértice.
• En cada iteración, añade una arista de peso mínimo al árbol actual que no completa un ciclo.
• El algoritmo de Kruskal es otro algoritmo para encontrar el árbol de expansión mínima.

Búsqueda Binaria

• Los elementos se organizan siguiendo un orden específico.
• El valor de un vértice izquierdo es menor que el de su raíz o padre.
• El valor de un nodo derecho es mayor que el de su vértice padre.
• Esta regla se repite recursivamente en las partes izquierda y derecha del árbol, comenzando desde la raíz.

Recorridos

• Son aplicables a árboles binarios para visitar cada vértice siguiendo un orden específico: preordenado, entreordenado (inorden) y postordenado.

Preorden

1. Se procesa la raíz.
2. Se recorre el subárbol izquierdo.
3. Se recorre el subárbol derecho.

Inorden (Entreorden)

1. Se recorre el subárbol izquierdo.
2. Se procesa la raíz.
3. Se recorre el subárbol derecho.

Postorden

1. Se recorre el subárbol izquierdo.
2. Se recorre el subárbol izquierdo.
3. Se recorre el subárbol derecho.

Conceptos Básicos y Terminología de Árboles

• Árbol: Estructura de datos jerárquica compuesta por nodos conectados mediante aristas, definida recursivamente como un conjunto de nodos.
  • Raíz: Nodo principal del árbol, sin padre, desde donde se derivan los demás nodos.
  • Nodo: Elemento que almacena un valor y referencias a otros nodos en el árbol.
  • Padre: Nodo con conexión directa a un nodo inferior en la jerarquía; un nodo solo tiene un padre (excepto la raíz).
  • Hijo: Nodo directamente conectado a un nodo superior (su padre); un nodo puede tener múltiples hijos o ninguno.
  • Hermano: Nodos que comparten el mismo padre.
  • Hoja: Nodo sin hijos, representando los extremos del árbol.
  • Caminos: Secuencia de nodos conectados desde un inicio hasta un destino siguiendo las aristas del árbol.
  • Longitud de un Camino: Número de aristas en el camino entre dos nodos.

Conceptos Básicos de Árboles Binarios

• Estructura de datos jerárquica donde cada nodo tiene como máximo dos hijos.
  • Subárbol: Cualquier nodo del árbol junto con todos sus descendientes.
  • Sucesores: Nodos que siguen a un nodo en un recorrido, generalmente en el subárbol derecho.
  • Nodos Terminales: Nodos sin hijos, al final de una rama.
• Árboles Semejantes: Árboles con la misma estructura, número de nodos y disposición.
• Árboles Copia: Árboles idénticos en estructura y datos almacenados.