Conceptos básicos Arboles PDF

Preview

Summary

Arboles ...

Description

Conceptos básicos Un árbol es una estructura de datos similar a una lista enlazada, pero en lugar de que cada nodo apunte a un nodo siguiente de manera lineal, un nodo puede apuntar a una cantidad de nodos diferente. Un árbol es un ejemplo de una estructura de datos no lineal. La estructura de un árbol está representada de manera jerárquica, de manera gráfica.

En un ADT árbol, el orden de los elementos no es importante.

Nodo raíz (root): Es un nodo que no tiene padres. Puede existir como máximo una raíz para un árbol dado.

Hoja: Un nodo que no tiene hijos.

Ancestro: Un nodo p es un ancestro del nodo q si existe un camino desde la raíz hacia q, y p aparece en el camino.

Profundidad: La profundidad de un nodo es el tamaño del camino (cantidad de ramas) desde el nodo raíz hasta ese nodo.

Altura: La altura de un nodo está dada por el tamaño del camino (cantidad de ramas) desde ese nodo hasta el nodo más profundo (la hoja en el último nivel).

Nivel: El conjunto de todos los nodos para una profundidad del árbol dada es llamado nivel. El nodo raíz está en el nivel uno.

Árboles Binarios Un árbol es denominado binario si cada nodo del árbol tiene hasta un máximo de dos hijos. Tome en cuenta que un árbol vacío también es un árbol binario válido.

Algunas propiedades de los árboles binarios son las siguientes:

El número de nodos n de un árbol binario completo es 2a + 1 - 1. En donde a representa la altura del árbol. Como existen a niveles, es necesario contar todos los nodos en cada nivel.

El número de hojas en un árbol binario completo es 2a

Aplicaciones de los Árboles Binarios Árboles de expresión utilizados en compiladores Algortmos de compresión de datos (por ejemplo, Huffman) Árboles binarios de búsqueda (BST) Colas de prioridad Expresiones prefijas Recorridos en Árboles

PreOrden

-> Visitar la raíz

-> Visitar el nodo hijo izquierdo

-> Visitar el nodo hijo derecho

EnOrden

-> Visitar el nodo hijo izquierdo

-> Visitar la raíz

-> Visitar el nodo hijo derecho

PostOrden

-> Visitar el nodo hijo izquierdo

-> Visitar el nodo hijo derecho

-> Visitar la raíz

Level-Order Traversal (Breadth-First Search) -> Consiste en visitar todos los nodos de un nivel antes de seguir con el nivel siguiente.

Árboles Binarios de Búsqueda (BST) Árboles BST ¿Por qué utilizar árboles binarios de búsqueda?

Los árboles binarios y n-arios organizan la información sin ningún orden en particular. En el caso de los árboles binarios, para buscar un determinado elemento es necesario recorrer los subárboles izquierdo y derecho. Por lo tanto, la búsqueda en un árbol binario tiene complejidad O(n) - peor caso.

Un árbol BST tiene como propiedad principal la organización de elementos de tal manera que la búsqueda sea más eficiente, alcanzando una complejidad de O(log n) en el peor caso.

En un árbol BST, todos los elementos del subárbol izquierdo deben ser menores al elemento del nodo raíz, mientras que los elementos del subárbol derecho son mayores que el nodo raíz. Es necesario para un árbol BST que esta propiedad aplique para cada uno de los nodos del árbol. La siguiente imagen muestra un árbol BST.

Árboles BST balanceados Árboles binarios de búsqueda balanceados Normalmente esperamos que una búsqueda en un Árbol BST sea del orden O(log n). Sin embargo, conforme se realizan inserciones y se eliminan nodos del árbol, es posible que el árbol tome una estructura lineal en el peor de los casos, por lo que el orden de búsqueda se torna O(n). A este tipo de árboles se le denominan árboles degenerados. La siguiente ilustración muestra un ejemplo de árbol BST degenerado.

Por lo tanto, para mantener la eficiencia de búsqueda en el orden O(log n) en un árbol BST, es necesario recurrir a un mecanismo que permita reordenar el árbol para que no esté degenerado. Para obtener la complejidad O(log n) en el peor de los casos en un árbol BST, se ponen restricciones en las alturas de los subárboles izquierdo y derecho.

Cuando los árboles BST cumplen los requerimientos impuestos por las restricciones, se dice que el árbol está balanceado. En términos generales, se determina que un árbol BST está balanceado cuando la diferencia de la altura entre el subárbol izquierdo y derecho no supera un valor. Ese valor es

llamado el factor de balance o de equilibrio. Si el factor de balance es cero, el árbol se denomina árbol BST completamente balanceado. Las siguientes imágenes muestran ejemplos de árboles BST balanceados y sin balancear.

Árboles AVL Si el factor de balance es igual a uno, entonces el árbol es llamado Árbol AVL. Por lo tanto, un árbol AVL es un árbol binario de búsqueda con una condición de balance: la diferencia entre la altura del subárbol izquierdo y la del subárbol derecho es a lo sumo uno. Un árbol es considerado AVL si cumple lo siguiente:

Es un árbol binario de búsqueda Para cualquier nodo X, la altura del subárbol izquierdo de X y la altura del subárbol derecho de X difieren en máximo 1. Cuando la estructura del árbol cambia, requerimos modificar el árbol para mantener las propiedades descritas anteriormente. Esto se puede realizar a través de dos métodos: rotaciones simples y rotaciones dobles.

Por lo tanto, si la propiedad de un árbol AVL no se cumple en un nodo X, eso implica que los subárboles izquierdo y derecho de X difieren exactamente en dos (asumiendo una única operación de insertar o borrar). La rotación es la técnica utilizada para restaurar la propiedad de un árbol AVL....