Tipos de árboles



Árbol binario


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