Tipos de Estructuras de Datos: Definición y Características de Árboles

Conceptos Fundamentales de Estructuras de Árboles

Árbol Binario

Un Á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 el símbolo de 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 Binaria (ABB)

Un Á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 (Árboles N-arios)

Un árbol n-ario, con $n \ge 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 \le m \le n$, cada uno de los cuales es un árbol n-ario, llamados subárboles del árbol.

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

Árboles AVL

Los Á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 (factor de balanceo).
• Permiten las operaciones típicas de los árboles de búsqueda binarios: ¿está?, insertar y borrar.
• Las operaciones se realizan de igual manera que en los árboles de búsqueda binarios.

Cuando se inserta un nodo, el árbol se puede desequilibrar, por lo que es necesario rebalancearlo mediante rotaciones.

Montículos (Heaps)

Un Montículo de Mínimos es un árbol binario semicompleto de elementos ordenables que verifica la propiedad de montículo:

• 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 subárboles hijos son también montículos.

Un Montículo de Máximos verifica la misma estructura, pero 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 (o máximo, según el tipo).

Definiciones de Completitud

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

Especificaciones Formales (ADT)

Especificación: Árboles Binarios (Instancia 1)

ESPECIFICACIÓN: ÁRBOLES BINARIOS[ELEMENTO]
usa NATURALES2, BOOLEANOS

parámetro formal
    géneros elemento
fparámetro

géneros a_bin {árbol_binario}

operaciones: (código)

Especificación: Árboles de Búsqueda (Instancia 1)

ESPECIFICACIÓN: ÁRBOLES DE BÚSQUEDA[ELEMENTO]
usa ÁRBOLES_BINARIOS[ELEMENTO]

parámetro formal
    géneros elemento
    operaciones: elemento elemento -> bool
    var x, y: elemento
fparámetro

Especificación: Árboles Binarios (Instancia 2)

ESPECIFICACIÓN: ÁRBOLES BINARIOS[ELEMENTO]
usa NATURALES2, BOOLEANOS

parámetro formal
    géneros elemento
fparámetro

géneros a_bin {árbol_binario}

operaciones: (código)

Especificación: Árboles de Búsqueda (Instancia 2)

ESPECIFICACIÓN: ÁRBOLES DE BÚSQUEDA[ELEMENTO]
usa ÁRBOLES_BINARIOS[ELEMENTO]

parámetro formal
    géneros elemento
    operaciones: elemento elemento -> bool
    var x, y: elemento
fparámetro