tipos de arboles informatica

Tipos de árboles


Ejemplo de árbol (binario).
Árboles Binarios
Árbol de búsqueda binario auto-balanceable
Árboles AVL
Árboles Rojo-Negro
Árbol AA
Árboles Multicamino
Árboles B (Árbolesde búsqueda multicamino autobalanceados)
Árbol-B+
Árbol-B*
Árbol binario.-

En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijoizquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamadoun nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.Árbol binario de búsqueda auto-balanceable

En ciencias de la computación, un árbol binario de búsqueda auto-balanceable o equilibrado es un árbol binario de búsqueda que intenta mantener sualtura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente. Esto es importante, ya que muchas operaciones en un árbol de búsqueda binaria tardan untiempo proporcional a la altura del árbol, y los árboles binarios de búsqueda ordinarios pueden tomar alturas muy grandes en situaciones normales, como cuando las claves son insertadas en orden.Mantener baja la altura se consigue habitualmente realizando transformaciones en el árbol, como la rotación de árboles, en momentos clave.
Tiempos para varias operaciones en términos del número de nodosen el árbol n:
Operación
Tiempo en cota superior asintótica
Búsqueda
O(log n)
Inserción
O(log n)
Eliminación
O(log n)
Iteración en orden
O(n)
Para algunas implementaciones estos tiempos sonel peor caso, mientras que para otras están amortizados.
Estructuras de datos populares que implementan este tipo de árbol:
Árbol AVL
Árbol rojo-negro
Árbol AVL

Un árbol AVL es un tipo...