4.1.2 CLASIFICACIÓN DE ÁRBOLES

- Arboles binarios:

Arboles cuyos nodos contienen dos enlaces (uno de los cuales puede ser null). El nodo raíz es el primer nodo de un árbol. Cada enlace en el nodo raíz hace referencia un hijo. El hijo izquierdo es el primer nodo en el subárbol izquierdo (también conocido como el nodo raíz del subárbol izquierdo). El hijo derecho es el primer nodo en el subárbol derecho (también conocido como el nodo raíz del subárbol derecho).Los hijos de un nodo especifico se llaman hermanos. Un nodo sin hijos se llama nodo hoja. Generalmente, los científicos computacionales dibujan arboles desde el nodo raíz hacia abajo; exactamente lo opuesto a la manera en que crecen los arboles naturales. Recorrido de un árbol binario:- Recorrido: Requiere que cada nodo del árbol sea procesado (visitado) una vez y solo en una secuencia predeterminada. Existen dos enfoques generales para la secuencia de recorrido, profundidad y anchura. Recorrido en profundidad:

El proceso exige un camino desde la raíz a través de un hijo, al descendiente más lejano del primer hijo antes de proseguir a un segundo hijo. En otras palabras, en el recorrido en profundidad, todos los descendientes de un hijo se procesaran antes del siguiente hijo.

Recorrido en anchura: El proceso se realiza horizontalmente desde el raíz a todos sus hijos, a continuación a los hijos de sus hijos y así sucesivamente hasta que todos los nodos han sido procesados. En otras palabras, en el recorrido en anchura cada nivel se procesa totalmente antes que comience el siguiente nivel.

- Arboles de búsqueda binaria:

(Sin valores de nodo duplicado) cuenta con la característica de que los valores en cualquier subárbol izquierdo son menores que el valor del nodo padre de ese subárbol, y el valores en cualquier subárbol derecho son mayores que el valor del nodo padre de ese subárbol.

El árbol de búsqueda binaria facilita la eliminación de valores duplicados. Al crear un árbol, la operación de inserción reconoce los intentos de insertar un valor duplicado, ya que este sigue las mismas decisiones de “ir a la izquierda”  “ir a la derecha” en cada comparación, al igual que el valor original. Por lo tanto, la operación de inserción eventualmente compara el valor duplicado con un nodo que contenga el mismo valor.

Arboles estrechamente empaquetados (o balanceados):

En este tipo de arboles, cada nivel contiene cerca del doble de elementos que el nivel anterior.-

Arboles AVL: Están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O (log n).

factor de equilibrio

puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los sub árboles. Ejemplo:

- Arboles rojo negro:

Un árbol rojo-negro es un árbol binario de búsqueda en el que cada nodo tiene un atributo de color cuyo valor es o bien rojo o bien negro. Además de los requisitos impuestos a los árboles binarios de búsqueda convencionales, se deben satisfacer los siguientes para tener un árbol rojo-negro válido:

▪Todo nodo es o bien rojo o bien negro.

▪La raíz es negra.

▪Todas las hojas son negras (las hojas son los hijos nulos).

▪Los hijos de todo nodo rojo son negros (también llamada "Propiedad del rojo").

▪ Cada camino simple desde un nodo a una hoja descendiente contiene el mismo número de nodos negros, ya sea contando siempre los nodos negros nulos, o bien no contándolos nunca (el resultado es equivalente). También es llamada" Propiedad del camino", y al número de nodos negros de cada camino, que es constante para todos los caminos, se le denomina "Altura negra del árbol", y por tanto el camino no puede tener dos rojos seguidos. El camino más largo desde la raíz hasta una hoja no es más largo que 2 veces el camino más corto desde la raíz del árbol a una hoja en dicho árbol. El resultado es que dicho árbol está aproximadamente equilibrado.

- Árbol AA:

Los árboles AA son una variación del árbol rojo-negro, que a su vez es una mejora del árbol binario de búsqueda. A diferencia de los árboles rojo-negro, los nodos rojos en un árbol AA sólo pueden añadirse como un hijo derecho. En otras palabras, ningún nodo rojo puede ser un hijo izquierdo.

- Arboles multicamino:

Un árbol multicamino posee un grado g mayor a dos, donde cada nodo de información del árbol tiene un máximo de g hijo.

4.1.3 OPERACIONES BÁSICAS SOBRE ARBOLES BINARIO.

▪Enumerar todos los elementos.

▪Buscar un elemento.

.Dado un nodo, listar los hijos (si los hay).

▪Borrar un elemento.

▪Eliminar un subárbol (algunas veces llamada podar

▪Añadir un subárbol (algunas veces llamada injertar

▪Encontrar la raíz de cualquier nodo. Por su parte, la representación puede realizarse de diferentes formas. Las más utilizadas son:  Advertisement 

▪Representar cada nodo como una variable en el heap, con punteros a sus hijos y a su padre.

▪Representar el árbol con un array donde cada elemento es un nodo y las relaciones padre-hijo vienen dadas por la posición del nodo en el array.