Árboles Binarios y Árboles de Búsqueda

Árbol binario:

Es un conjunto de elementos del mismo tipo (nodos) tal que:

• O bien es un conjunto vacío, en cuyo caso se denomina árbol vacío y se denota por triángulo.
• O bien es no vacío y entonces:

1. Existe un elemento distinguido, llamado raíz y
2. El resto de elementos se distribuyen en dos conjuntos disjuntos, que también forman árboles binarios y que se denominan hijo izquierdo e hijo derecho.

Árbol de búsqueda:

Es un tipo especial de árbol binario, en el que los elementos están ordenados de la siguiente manera:

• Los elementos del hijo izquierdo son todos menores o iguales que la raíz.
• Los elementos del hijo derecho son todos mayores que la raíz.

Árboles generales:

Un árbol n-ario, con n>=1, es un conjunto de elementos del mismo tipo tal que:

• Existe un elemento llamado raíz.
• El resto de elementos se distribuyen en m subconjuntos disjuntos, con 0<><=n, cada uno de los cuales es un árbol n-ario, llamados subárboles del árbol.

Cuando el orden importa, se dice que el árbol está ordenado. Un árbol general no puede estar vacío.

Árboles AVL:

Son un tipo especial de árboles binarios de búsqueda.

• Se caracterizan por estar balanceados. Las alturas de los hijos izquierdo y derecho de un nodo se diferencian en 1 como máximo.
• Permiten las operaciones típicas de los árboles de búsqueda binarios: esta?, insertar y borrar.
• Las operaciones se realizan de igual manera que en los árboles de búsqueda binarios.

Cuando se inserta un nodo se puede desequilibrar el árbol y hay que rebalancearlo.

Montículos: (De mínimos) es un árbol binario semicompleto de elementos ordenables que verifica:

• El árbol está vacío, o
• El elemento de la raíz es menor o igual que el resto de los elementos en el árbol, y los hijos son también montículos.
• (De máximos)->si la relación entre los elementos es de mayor o igual.

Los montículos permiten las operaciones de insertar_mínimo y eliminar_mínimo.

Un árbol binario es completo si todas sus hojas están en el mismo nivel, y es semicompleto si es completo o si las hijas que le faltan están consecutivas (Empezando por la derecha).

ESPECIFICACIÓN: ÁRBOLES BINARIOS

espec ÁRBOLES_BINARIOS[ELEMENTO] usa NATURALES2, BOOLEANOS

parametro formal generos elemento fparametro g

generos a_bin {árbol_binario}

operaciones: (código)

ESPECIFICACIÓN: ÁRBOLES DE BÚSQUEDA

espec ÁRBOLES_BÚSQUEDA[ELEMENTO] usa ÁRBOLES_BINARIOS[ELEMENTO]

parametro formal generos elemento

operaciones elemento elemento->bool

var x, y: elemento