Árboles Binarios

Árbol Binario

Un árbol binario es un conjunto finito de elementos, el cual está vacío o dividido en tres subconjuntos separados:

1. El primer subconjunto contiene un elemento único llamado raíz del árbol.
2. El segundo subconjunto es en sí mismo un árbol binario y se le conoce como sub-árbol izquierdo del árbol original.
3. El tercer subconjunto es también un árbol binario y se le conoce como sub-árbol derecho del árbol original.
4. El sub-árbol izquierdo o derecho puede o no estar vacío. Cada elemento de un árbol binario se conoce como nodo del árbol.

Si B es la raíz de un árbol binario y D es la raíz del sub-árbol izquierdo/derecho, se dice que B es el padre de D y que D es el hijo izquierdo/derecho de B.

1. A un nodo que no tiene hijos, tal como A o C de la Ilustración 2, se le conoce como hoja.
2. Un nodo n1 es un ancestro de un nodo n2 (y n2 es un descendiente de n1) si n1 es el padre de n2 o el padre de algún ancestro de n2.
3. Recorrer un árbol de la raíz hacia las hojas se denomina descender el árbol y al sentido opuesto ascender el árbol.
4. Un árbol estrictamente binario es aquel en el que cada nodo que no es hoja, tiene sub-árboles izquierdo y derecho que no están vacíos.
5. Un árbol estrictamente binario con n hojas siempre contiene 2n-1 nodos.
6. La raíz del árbol tiene el nivel 0.
7. El nivel de cualquier otro nodo en el árbol es uno más que el nivel de su padre.
8. La profundidad o altura de un árbol binario es el máximo nivel de cualquier hoja en el árbol.
9. Un árbol binario completo de profundidad p, es un árbol estrictamente binario que tiene todas sus hojas en el nivel p.

El nivel de un nodo en un árbol binario se define del modo siguiente:

1. La raíz del árbol tiene el nivel 0.
2. El nivel de cualquier otro nodo en el árbol es uno más que el nivel de su padre.
3. La profundidad o altura de un árbol binario es el máximo nivel de cualquier hoja en el árbol.
4. Un árbol binario completo de profundidad p, es un árbol estrictamente binario que tiene todas sus hojas en el nivel p.

Operaciones en árboles binarios.

Si p es un apuntador a un nodo nd de un árbol binario:

1. La función info(p) regresa el contenido de nd.
2. La función left(p) regresa un apuntador al hijo izquierdo de nd.
3. La función right(p) regresa un apuntador al hijo derecho de nd.
4. La función father(p) regresa un apuntador al padre de nd.
5. La función brother(p) regresa un apuntador al hermano de nd.
6. La función isLeft(p) regresa true si nd es un hijo izquierdo de algún otro nodo en el árbol, y false en caso contrario.
7. La función isRight(p) regresa true si nd es un hijo derecho de algún otro nodo en el árbol, y false en caso contrario. 

En la construcción de un árbol binario son útiles las operaciones: 

1. makeTree(x) crea un nuevo árbol que consta de un nodo único con un campo de información x, y regresa un apuntador a este nodo.
2. setLeft(p, x) crea un nuevo hijo izquierdo de node(p) con el campo de información x.
3. setRight(p, x) crea un nuevo hijo derecho de node(p) con el campo de información x.

Aplicaciones de árboles binarios.

Suponga que se desea encontrar todos los duplicados de una lista de números. Considérese lo siguiente:

1. El primer número de la lista se coloca en un nodo que se ha establecido como la raíz de un árbol binario con sub-árboles izquierdo y derecho vacíos.
2. Cada número sucesivo en la lista se compara con el número en la raíz, aquí se tienen 3 casos:
1. Si coincide, se tiene un duplicado.
2. Si es mayor, se examina el sub-árbol derecho.
3. Si es menor, se examina el sub-árbol izquierdo.

1. Si alguno de los sub-árboles esta vacío, el número no es un duplicado y se coloca en un nodo nuevo en dicha posición del árbol.

2. Si el sub-árbol no está vacío, se compara el número con la raíz del sub-árbol y se repite todo el proceso con el sub-árbol.

Un árbol binario de búsqueda no tiene valores duplicados en los nodos y además, tiene la característica de que:

1. Los valores en cualquier sub-árbol izquierdo son menores que el valor en su nodo padre.
2. Los valores en cualquier sub-árbol derecho son mayores que el valor en su nodo padre.
1. 14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17

Recorrido de un nodo

Para recorrer un árbol binario no vacío en orden previo (orden de primera profundidad) se ejecutan tres operaciones:

1. Visitar la raíz.
2. Recorrer el sub-árbol izquierdo en orden previo.
3. Recorrer el sub-árbol derecho en orden previo.

Para recorrer un árbol binario no vacío en orden (orden simétrico) se ejecutan tres operaciones:

1. Recorrer el sub-árbol izquierdo en orden.
2. Visitar la raíz.
3. Recorrer el sub-árbol derecho en orden.

Para recorrer un árbol binario no vacío en orden posterior se ejecutan tres operaciones:

1. Recorrer el sub-árbol izquierdo en orden posterior.
2. Recorrer el sub-árbol derecho en orden posterior.
3. Visitar la raíz.

Eliminación de un árbol binario de búsqueda. 

La eliminación es el problema inverso a la inserción, sin embargo, las cosas no son tan sencillas como para la inserción.

Si el nodo que se pretende eliminar es un nodo hoja o un nodo con un solo descendiente, la eliminación es directa.

La dificultad radica en la eliminación de un nodo con dos descendientes. En este caso, el elemento eliminado será substituido por el descendiente más a la derecha de su sub-árbol izquierdo (o bien por el descendiente más a la izquierda de su sub-árbol derecho).