next up previous contents
Siguiente: Representación en C/C++ de Subir: Árboles binarios Anterior: Operaciones con árboles binarios   Índice General

Aplicaciones de árboles binarios

Un árbol binario es una estructura de datos útil cuando se trata de hacer modelos de procesos en donde se requiere tomar decisiones en uno de dos sentidos en cada parte del proceso. Por ejemplo, supongamos que tenemos un arreglo en donde queremos encontrar todos los duplicados. Esta situación es bastante útil en el manejo de las bases de datos, para evitar un problema que se llama redundancia.

Una manera de encontrar los elementos duplicados en un arreglo es recorrer todo el arreglo y comparar con cada uno de los elementos del arreglo. Esto implica que si el arreglo tiene $ n$ elementos, se deben hacer $ n$ comparaciones, claro, no es mucho problema si $ n$ es un número pequeño, pero el problema se va complicando más a medida que $ n$ aumenta.

Si usamos un árbol binario, el número de comparaciones se reduce bastante, veamos cómo.

El primer número del arreglo se coloca en la raíz del árbol (como en este ejemplo siempre vamos a trabajar con árboles binarios, simplemente diremos árbol, para referirnos a un árbol binario) con sus subárboles izquierdo y derecho vacíos. Luego, cada elemento del arreglo se compara son la información del nodo raíz y se crean los nuevos hijos con el siguiente criterio:

Una vez que ya está creado el árbol, se pueden buscar los elementos repetidos. Si x el elemento buscado, se debe recorrer el árbol del siguiente modo:

Sea k la información del nodo actual p. Si $ \texttt{x}>\texttt{k}$ entonces cambiar el nodo actual a right(p), en caso contrario, en caso de que $ \texttt{x}=\texttt{k}$ informar una ocurrencia duplicada y en caso de que $ \texttt{x}\geq\texttt{k}$ cambiar el nodo actual a left(p).

El siguiente algoritmo

leer numero buscado >> n
tree=makeTree(n)
while(hay numeros en el arreglo){
  leeSiguienteNumero >> k
  p=q=tree;
  while(k!=info(p)&&q!=NULL){
    p=q
    if(k<info(p))
       q=left(p)
      else
       q=right(p) 
  }
  if(k==info(p))
    despliega<<" el numero es duplicado";
   else
     if (k<info(p))
       setLeft(p,k)
      else
       setRight(p,k)  
}

Figura 28: Árbol binario para encontrar números duplicados
Image aCoincid

Para saber el contenido de todos los nodos en un árbol es necesario recorrer el árbol. Esto es debido a que solo tenemos conocimiento del contenido de la dirección de un nodo a la vez. Al recorrer el árbol es necesario tener la dirección de cada nodo, no necesariamente todos al mismo tiempo, de hecho normalmente se tiene la dirección de uno o dos nodos a la vez; de manera que cuando se tiene la dirección de un nodo, se dice que se visita ese nodo.

Aunque hay un orden preestablecido (la enumeración de los nodos) no siempre es bueno recorrer el árbol en ese orden, porque el manejo de los apuntadores se vuelve más complejo. En su lugar se han adoptado tres criterios principales para recorrer un árbol binario, sin que de omita cualquier otro criterio diferente.

Los tres criterios principales para recorrer un árbol binario y visitar todos sus nodos son, recorrer el árbol en:

preorden:
Se ejecutan las operaciones:
  1. Visitar la raíz
  2. recorrer el subárbol izquierdo en preorden
  3. recorrer el subárbol derecho en preorden
entreorden:
Se ejecutan las operaciones:
  1. recorrer el subárbol izquierdo en entreorden
  2. Visitar la raíz
  3. recorrer el subárbol derecho en entreorden
postorden:
Se ejecutan las operaciones:
  1. recorrer el subárbol izquierdo en postorden
  2. recorrer el subárbol derecho en postorden
  3. Visitar la raíz

Al considerar el árbol binario que se muestra en la figura 28 usando cada uno de los tres criterios para recorrer el árbol se tienen las siguientes secuencias de nodos:

En preorden: $ \langle 14,4,3,9,7,5,15,18,16,17,20\rangle$

En entreorden: $ \langle 3,4,5,7,9,14,15,16,17,18,20\rangle$

En postorden: $ \langle 3,5,7,9,4,17,16,20,18,15,14\rangle$

Esto nos lleva a pensar en otra aplicación, el ordenamiento de los elementos de un arreglo.

Para ordenar los elementos de un arreglo en sentido ascendente, se debe construir un árbol similar al árbol binario de búsqueda, pero sin omitir las coincidencias.

El arreglo usado para crear el árbol binario de búsqueda fue

<14,15,4,9,7,18,3,5,16,4,20,17,9,14,5>

El árbol de ordenamiento es el que se muestra en la figura 29

Figura 29: Árbol binario para ordenar una secuencia de números
Image ordArbol

Para ordenar los elementos de este arreglo basta recorrer el árbol en forma de entreorden.

¿Cuál sería el algoritmo para ordenarlo de manera descendente?


next up previous contents
Siguiente: Representación en C/C++ de Subir: Árboles binarios Anterior: Operaciones con árboles binarios   Índice General
Abdiel Caceres-Gonzalez Jun-02-2005