Aspectos Básicos

• Pueden cambiar de tamaño durante tiempo de ejecución

• Contienen uno o más componentes pertenecientes a su mismo tipo

• Listas lineales, Clave, Puntero sucesor, información

Árboles

Árbol ordenado

Se ordenan de Izquierda a derecha

Nodos

Descendientes, él que está debajo
Antecesor, él que está encima

Profundidad o altura

Máximo de los niveles de todos los elementos

Hojas y nodos interiores

Hojas, el que no tiene descendientes, los demás son nodos interiores

Grado

Número de descendientes directos de un nodo

Grado del Árbol

El máximo de todos los grados del árbol

Longitud de Camino de x

Número de arcos que tienen que ser recorridos para llegar a un nodo.

Árbol binario

Árbol ordenado de grado 2

Árboles multicamino

Árboles de grado superior a  2

• Árboles B (Búsqueda)

  • Cada página contiene como máximo 2n elementos

  • Cada página, menos la raíz contiene al menos n elementos

  • Una página o no tiene descendientes o tiene m+1 descendientes.

  • Todas las hojas están en el mismo nivel.

Equilibrado

Altura del izquierdo difiere como mucho en una unidad del derecho

Perfectamente Equilibrado

Número de nodos del Izquierdo difiere como mucho en uno de los del derecho

Recorridos

• Pre-orden R,A,B

• Orden-Central A,R,B

• Post-orden A,B,R

Hashing

Funciones

• Módulo

• Multiplicación

• Cuadrado

Resolución de colisiones

1. Hashing abierto, fuera de la tabla principal

   1. Encadenamiento

      1. Externo

      2. Interno

   2. Área secundaria de desbordamiento

2. Hashing cerrado, dentro de la tabla principal

   1. Direccionamiento

   2. Hashing múltiple