En un árbol binario completo, todos los nodos tienen 0 o 2 hijos. Ambos tipos de nodos pueden aparecer en todos los niveles del árbol. Un ejemplo se da en la siguiente figura.
En un árbol binario completo, todos los nodos tienen dos hijos, excepto los nodos en los dos niveles más bajos. En el nivel más bajo, los nodos tienen (por definición) cero hijos, y en el nivel superior, los nodos pueden tener 0, 1 o 2 hijos. Además, el último nivel debe llenarse de izquierda a derecha sin dejar huecos. Un ejemplo se da en la siguiente figura.
- Cómo construir un secuenciador de ADN
- Cómo demostrar que el algoritmo de búsqueda uniforme de costos siempre genera una ruta óptima
- Teoría de conjuntos: ¿un subconjunto es un tipo de intersección?
- Cómo hacer para vender con éxito el algoritmo de negociación de fx
- ¿Encontrar XOR de pares ordenados en una matriz que está incluso con O (n)?
Al comparar los dos tipos de árboles binarios, podemos hacer las siguientes observaciones:
- No todo árbol binario completo es un árbol binario completo. Esto se ilustra en el primer ejemplo. Las dos razones para esto es que en un árbol binario completo las hojas pueden aparecer en cualquier nivel, no solo en los dos más bajos, y el nivel más bajo no necesita llenarse de izquierda a derecha sin dejar huecos.
- No todo árbol binario completo es un árbol binario completo. Esto se ilustra en el segundo ejemplo. La razón es que hay un nodo con un solo hijo. Sin embargo, en un árbol binario completo siempre habrá como máximo un nodo que viole el requisito de árboles binarios completos. En ese sentido, los árboles binarios completos son árboles binarios completos o casi completos.
- Cuando se usan árboles binarios como árboles de búsqueda, se vuelve importante si están equilibrados o no, ya que la profundidad de un nodo determina cuántos pasos se necesitan para encontrar el valor asociado. Desde esa perspectiva, el árbol binario completo es preferible, ya que es más equilibrado. Sin embargo, para conjuntos de valores que cambian mucho puede ser engorroso ya que puede requerir una gran reestructuración cuando se eliminan o agregan valores. Por lo tanto, muchas estructuras de datos populares para buscar en conjuntos dinámicos de valores, como los árboles rojo-negros, son de hecho árboles binarios completos con restricciones adicionales para garantizar alguna forma de equilibrio.
