Hoja 1
Capítulo 8 : Árboles
  Introducción
    -Uno de los problemas principales para el tratamiento de los grafos es que no guardan una estructura establecida y que no respetan reglas, ya que la relación entre los nodos puede ser tan compleja como la misma naturaleza
-En lugar de usar grafos que están estructurados sin regla alguna se utilizan grafos con características particulares que permiten un mejor tratamiento de la información y que se conocen como árboles
  Propiedades de los árboles
    -Es un grafo conexo en donde existe un camino entre cualquier par de vértices
-no tiene ciclos ni lados paralelos y todo árbol con al menos dos vértices tiene al menos una hoja
-Las vértices de un árbol reciben el nombre de nodos y los lados de ramas
-Un grafo está compuesto por niveles y el mas alto de la jerarquía se le llama raíz
  Clasificación por número de nodos
    -Los árboles pueden ser binarios, trinarios, cuaternarios, etc
-Los árboles binarios son especialmente importantes en el área de la computación ya que por su naturaleza de tener solamente dos valores, o bien falso o verdadero, son muy útiles en aplicaciones de sistemas digitales
  Clasificación por altura
    -Los árboles pueden ser balanceados y desbalanceados
-Para balancear un árbol con una cantidad constante de hijos de los nodos padres, se llenan empezando por la raíz y descendiendo con un avance de izquierda a derecha
  Bosques
    -De un árbol se pueden obtener varios subárboles, mismos que conforman un bosque
-A su vez un árbol puede considerarse como un bosque conectado
-el árbol más pequeño está integrado por cuando menos dos nodos conectados por una arista
  Árboles con pesos
    -Para representar caracteres en el código ASCH, se usan cadenas de 8 bits
-se puede aumentar la velocidad de procesamiento bien aprovechar mejor la memoria de la computadora, mediante una compactación de la información, usando cadenas de diferente longitud
  Árboles generadores
    -De un grafo conexo es posible obtener un árbol que permite mantener conectados a todos los nodos del grafo, ese árbol obtenido recibe el nombre de árbol generador
  Búsqueda a lo ancho
    -En este procedimiento se comienza en la raíz y después se examinan todos los hijos de la raíz de izquierda a derecha
-Si la información que se busca no se encuentra en ese nivel, se procede a buscar en el siguiente nivel también de izquierda a derecha y así sucesivamente
  Búsqueda en profundidad
    -En este caso se comienza en el nodo raíz, después buscar en el hijo de la izquierda, si este nodo tiene hijos continuar con el de la izquierda y así sucesivamente hasta llegar a la parte más baja del árbol
-Si este nodo ya no tiene hijo izquierdo, continuar con el hijo de la derecha hasta llegar a la hoja
  Obtención de árboles generadores
    -Un árbol es un grafo muy importante ya que permite la estructuración y tratamiento de la información de manera más sencilla
-De todo grafo conexo se puede obtener un árbol que recibe el nombre de árbol generador
  Árbol generador mínimo
    -Permite mantener unidos a todos los vértices y que no tiene ciclos, además de que es la forma más barata o corta ya que la trayectoria o costo es mínimo
  Método de prim
    -Método para obtener un árbol generador mínimo a partir de un grafo conexo etiquetado
-se puede poner en práctica aplicando un algoritmo que se utiliza cuando se desea eliminar conexiones redundante y dejar sólo las aristas del grafo que tengan menor distancia o costo
  Método de Kruskal
    -Se destaca por integrar al árbol generador mínimo a aquellas aristas que tengan menos costo, cuidando siempre que no se formen ciclos
  Recorrido de un árbol
    -Preorden: En este recorrido primero se toma el padre, luego el hijo izquierdo y al final los demás hijos.
-Inorden: En este recorrido primero se toma el hijo izquierdo, después el padre y al final los demás hijos.
-Postorden: Se toma primero el hijo izquierdo, después los demás hijos y al final el padre.
  Recorridos en árboles etiquetados
    -En el área de la computación los árboles etiquetados se usan para evaluar expresiones matemáticas, y las constantes o variables se ubican en las hojas mientras que los operadores se colocan como nodos intermedios
  Búsquedas
    -Se puede considerar que uno de los usos principales de la computadora es guardar la información para después recuperarla en el orden deseado y en forma rápida
-Cuando la información es pequeña no hay ningún problema ya que el tiempo en que encuentra la información almacenada es relativamente pequeño, pero conforme ésta aumenta el tiempo de respuesta es importantísimo
  Árboles de búsqueda binarios
    -Es posible crear un árbol que desde el momento en que se captura la información quede de forma que sea relativamente fácil acceder a ella, además de que el árbol de búsqueda binario es relativamente sencillo de crear y manipular
  Aplicación de los árboles
    -La estructura de árbol, independientemente de si se trata de árboles binarios, AVL o B, se usa principalmente para guardar la información organizada de tal manera que sea posible tener un rápido acceso a ella
-La diferencia principal que permite decidir qué tipo de árbol usar depende de la forma en qué está estructurada la información, pero sobre todo del volumen de la misma