Arboles binarios

Un árbol es un conjunto de elementos finitos (pueden ser homogéneos o heterogéneos) denominados nodos y un conjunto finitos de líneas que enlazan los nodos que se denominan ramas, tiene un nodo inicial el cual no depende de ningún otro denominado raíz, el resto son hijos del primer nodo y los nodos hijos que no posean descendencia se denominan hojas.

Una estructura de datos de árbol se puede definir de forma recursiva (localmente) como una colección de nodos (a partir de un nodo raíz), donde cada nodo es una estructura de datos con un valor, junto con una lista de referencias a los nodos (los hijos) , con la condición de que ninguna referencia esté duplicada ni que ningún nodo apunte a la raíz.

Vocabulario y definiciones

• Nodo: Un nodo es una parte fundamental de un árbol. Puede tener un nombre, que llamamos la “clave”. Un nodo también puede tener información adicional. Llamamos a esta información adicional la “carga útil”. Aunque la información de carga útil no es central para muchos algoritmos de árboles, a menudo es crítica en aplicaciones que usan árboles.
• Arista: Una arista es otra parte fundamental de un árbol. Una arista conecta dos nodos para mostrar que hay una relación entre ellos. Cada nodo (excepto la raíz) está conectado por exactamente una arista entrante desde otro nodo. Cada nodo puede tener varias aristas salientes.
• Raíz: La raíz del árbol es el único nodo en el árbol que no tiene aristas entrantes. Suele ser el nodo de acceso al arbol.
• Ruta: Una ruta es una lista ordenada de nodos que están conectados por aristas. Por ejemplo, Mamíferos → Carnívoros → Félidos → Felis → Domestica, es una ruta.
• Hijos: El conjunto de c nodos que tienen aristas entrantes desde el mismo nodo se dice que son hijos de ese nodo.
• Padre: Un nodo es el padre de todos los nodos con los que se conecta mediante aristas salientes. 
• Hermanos: Se dice que los nodos del árbol que son hijos del mismo padre son hermanos. 
• Subárbol: Un subárbol es un conjunto de nodos y aristas compuesto por un padre y todos los descendientes de ese padre.
• Nodo hoja: Un nodo hoja es un nodo que no tiene hijos. También se puede decir que es aquel nodo cuyos hijos son NULL.
• Nivel: El nivel de un nodo n es el número de aristas en la ruta desde el nodo raíz hasta n. 
• Altura: La altura de un árbol es igual al máximo nivel de cualquier nodo en el árbol. 

Árboles equilibrados

• Las búsquedas son más eficientes cuando el árbol está equilibrado
• Un árbol equilibrado es aquel en el que las ramas izquierda y derecha de cada nodo tienen aproximadamente la misma altura (el árbol lleno sería el árbol equilibrado perfecto con todos los nodos con subárboles izq y dch de la misma altura)
• Si los nodos que se van insertando en el árbol aparecen en orden aleatorio el árbol tenderá a ser equilibrado

Árboles “degenerados”

• El caso peor ocurre cuando el árbol está “degenerado”, es decir, sigue siendo un árbol pero su estructura es equivalente a una lista enlazada (todos los nodos sólo tienen un hijo)
• Si los nodos del árbol que se van insertando en el árbol aparecen con un orden determinado el árbol tenderá a ser degenerado.

Árbol des-balanceado

* Los datos en la realidad suelen tener un cierto grado de orden por lo que para que los árboles BB sean eficientes es necesario hacer reequilibrados ⇒ árboles AVL

Definamos un árbol binario (AB)

struct Nodo
  int dato;
  struct Nodo *nodoIzq;
  struct Nodo *nodoDer;
end

Árbol Binario de Búsqueda(ABB)

Es aquel que dado un nodo, todos los datos del subárbol izquierdo son menores, mientras que todos los del subárbol derecho son mayores. 

Operaciones en árboles ABB

Insertar un nodo en el árbol 

• Se compara la clave a insertar con la raíz del árbol
• Si el árbol es NULO insertamos una hoja con la clave en esa posición
• Si clave < valor de la raíz la búsqueda continúa por el subárbol izquierdo
• Si clave > valor de la raíz la búsqueda continúa por el subárbol derecho
• Si clave = valor (claves repetidas) no se hace nada. Este funcionamiento podría ser distinto: reemplazar el antiguo con el nuevo, lanzar un error, permitir duplicados, etc.

InsertarABB(Arbol, valor)
  if (Arbol == null)
    ConstruirArbol(null, null, valor, Arbol)
  else
    if (valor < Arbol->dato)
      InsertarABB(Arbol->nodoIzq, valor)
    else if (valor > Arbol->dato)
      InsertarABB(Arbol->nodoDer, valor)
    else 
      return true
    endif
  endif
end

Buscar un nodo específico

• Se compara la clave a buscar con la raíz del árbol.
• Si el árbol es NULO la búsqueda acaba sin éxito.
• Si clave = valor de la raíz la búsqueda acaba con éxito.
• Si clave < valor de la raíz la búsqueda continúa por el subárbol izquierdo.
• Si clave > valor de la raíz la búsqueda continúa por el subárbol derecho.

BuscaABB (Arbol, valor)
  if (Arbol == null)
    return null
  else
    if (valor == Arbol->dato)
      return Arbol
    else if (valor < Arbol->dato)
      BuscaABB(Arbol->nodoIzq, valor)
    else 
      BuscaABB(Arbol->nodoDer, valor)
    endif
  endif
end

Borrado

• Se busca en el árbol la posición del nodo a eliminar 
• Si es un nodo hoja ⇒ se actualiza el puntero del padre a null y se borra el nodo 
• Si es un nodo con un solo hijo ⇒ se actualiza el puntero del padre para que apunte al hijo y se borra el nodo
• Si es un nodo con dos hijos
• Se intercambia el nodo con el mayor de su subárbol izquierdo (nodo anterior en el orden) o con el menor de su subarbol derecho (nodo posterior en el orden) y se borra el nodo.
• El mayor de su subárbol izquierdo se caracteriza por ser un nodo sin hijos o con un hijo a la derecha (si tuviera un hijo a la izquierda ya no sería el mayor). Por lo tanto es un nodo sencillo de borrar
• El menor de su subárbol derecho se caracteriza por ser un nodo sin hijos o con un hijo a la izquierda (si tuviera un hijo a la derecha ya no sería el menor). Por lo tanto es un nodo sencillo de borrar
• Al substituir un nodo por su anterior o su posterior la propiedad de árbol binario de búsqueda se sigue cumpliendo

EliminarABB(Arbol, valor)
  if (Arbol == null)
    return false     // Si Arbol es VACIO, el valor no existe y se devuelve false
  elseif (valor < Arbol->dato) // Si el valor es menor mandamos borrar en subárbol izq
    EliminarABB(Arbol->nodoIzq, valor)
  elseif (valor>Arbol->dato) // Si el valor es mayor mandamos borrar en subárbol dch
    EliminarABB(Arbol->nodoDer, valor)
  else // Si el valor es igual borramos el nodo
    aux == Arbol
    if (Arbol->nodoDer == null) // Si no tiene hijo dch lo sustituimos por el izq
      Arbol = Arbol->nodoIzq // (incluye el caso de los dos hijos vacios)
    elseif (Arbol->nodoIzq == null) // Si no tiene hijo izq lo sustituimos por el dch
      Arbol = Arbol->nodoDer // Si tiene dos hijos llamamos a reemplazar
    else 
      reemplazar (aux, Arbol->nodoIzq); // pasando el nodo a eliminar y su subarbol izq
    return true // Se devuelve true porque el valor existe
  endif
end 


reemplazar(Arbol, nodoDel)
  if (nodoDel->nodoDer <> null)
    reemplazar(nodoDel->nodoDer) // Bajamos por la rama derecha
  else 
    Arbol->dato == nodoDel->dato // reemplazamos los campos de información
Arbol == nodoDel // Marcamos el nodo sobre el que se hará un dispose
nodoDel == nodoDel->nodoIzq // y reenlazamos la estructura “saltando” al nodo que 
  endif                                 // se va a eliminar

end

Búsqueda binaria

La Búsqueda binaria divide el conjunto o subconjuntos ordenados en tres. Uno unitario para comparar, si es el buscado finaliza la búsqueda, de lo contrario continúa la búsqueda en el conjunto de los menores al compararlo si el buscado es menor o en el conjunto de los mayores si el buscado es mayor. Esto elimina gran cantidad de elementos a comparar.

El método se mejora cuanto más parejos sean los conjuntos de menores y mayores.

La búsqueda binaria es computada en el peor de los casos en un tiempo logarítmico, realizando "O(log n)" comparaciones, donde n es el número de elementos del arreglo y log es el logaritmo. La búsqueda binaria requiere solamente O(1) en espacio, es decir, que el espacio requerido por el algoritmo es el mismo para cualquier cantidad de elementos.

Búsqueda binaria

Aunque estructuras de datos especializadas en la búsqueda rápidas como las tablas hash pueden ser más eficientes, la búsqueda binaria se aplica a un amplio rango de problemas de búsqueda.

La forma implícita es aquella en la cual la estructura que lo soporta está definida de esta forma. Este es el caso del Árbol Binario Ordenado (ABO) también denominado Árbol de Búsqueda Binaria (ABB) y es más eficiente cuanto más parejos son sus subárboles, tal el caso de árbol AVL.

La forma explícita es cuando la estructura que soporta al conjunto ordenado es lineal y es el algoritmo el que explicita la búsqueda binaria. Así se busca el elemento del medio, si es el buscado finaliza la búsqueda, de lo contrario si el buscado es menos se hace los mismo en el subconjunto del primer elemento al anterior al medio y si el buscado es mayor se hace lo mismo en el subconjunto del siguiente al medio hasta el último.