Índice

Árboles binarios de búsqueda

Árbol:de búsqueda

1. Definición

En un árbol binario de búsqueda, todos los elementos están dotados de una clave y se ubican en el árbol en función de esta clave. La clave hace que el orden del árbol sea visible y usable. La clave en general es un número que se añade al elemento. Es gracias a este número que el elemento se puede almacenar e identificar en una ubicación determinada en el árbol. A continuación, todos los elementos pueden encontrarse rápidamente gracias a su clave, sin que estén obligados a recorrer todo el árbol de forma sistemática. Los elementos almacenados en el árbol están de algún modo ordenados en función de su clave. Es fácil añadir nuevos elementos o borrar elementos sin modificar el orden del árbol.

Árbol:binario Árbol:clave

Las claves siguen las reglas siguientes:

Para cada nodo del árbol:

  • Las claves del subárbol izquierdo (SAI) son menores que la clave de la raíz.

  • Las claves del subárbol derecho (SAD) son menores que la clave de la raíz.

  • Todas las claves son diferentes, no hay claves repetidas.

Por ejemplo, la serie de claves 17, 3, 15, 9, 27, 44, 2, 50, 30 genera el árbol siguiente:

images/06ri68.PNG

El árbol anterior requiere que los elementos se introduzcan en el orden de la serie, ya que la forma del árbol depende del orden de inserción:

images/06ri69.png

Observación:

Sea cual ...