Tipos de árboles
En ciencias de la computación, un árbol binario es una estructura de datos en la
cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden
tener más de dos hijos (de ahí el nombre "binario").
Árbol binario
completo: Es aquél en el que cada nodo tiene dos ramas o ninguna. Un árbol
binario completo con i nodos internos tiene (i + 1) hojas y (2i + 1) vértices
en total.
Árboles ternarios
Es una estructura
similar a un árbol, tiene una raíz y cada nodo tiene máximo tres hijos. Los
cuaternarios cada nodo padre tiene como máximo cuatro hijos y así
sucesivamente.
Árbol AVL (Balanceado)
Los árboles 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. El factor de equilibrio puede ser almacenado directamente en
cada nodo o ser computado a partir de las alturas de los subárboles.
Para conseguir esta propiedad de equilibrio, la inserción y el
borrado de los nodos se ha de realizar de una forma especial. Si al realizar
una operación de inserción o borrado se rompe la condición de equilibrio, hay
que realizar una serie de rotaciones
de los nodos.
Árbol des-balanceado: Esta es cuando
la diferencia de altura entre las ramas es mayor a 1.
Árboles 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 rojo o negro. En adelante, se dice que
un nodo es rojo o negro haciendo
referencia a dicho atributo.
Además de los requisitos impuestos a
los árboles binarios de búsqueda convencionales, se deben satisfacer las
siguientes reglas para tener un árbol rojo-negro válido:
1. Todo nodo es
o bien rojo o bien negro.
2. La raíz es negra.
3. Todas
las hojas (NIL) son negras.
4. Todo nodo rojo
debe tener dos nodos hijos negros.
5. Cada camino desde
un nodo dado a sus hojas descendientes contiene el mismo número de nodos negros.
Árbol de segmento
Es una estructura de datos en forma de árbol para guardar intervalos o segmentos. Permite consultar cuál de los segmentos guardados contiene un punto. Es decir, su contenido no puede ser modificado una vez que su estructura es construida. El árbol de segmentos puede generalizarse para espacios multidimensionales.
Árbol multicamino o multirrama
Posee un
grado g mayor a dos, donde cada nodo de información del árbol tiene
un máximo de g hijos.
Comentarios
Publicar un comentario