Estructuras Recursivas

ÁRBOLES

Árboles: Es un conjunto de nodos, en cada nodo hay información.

Características:

• Árbol vacio T = 0
• Raíz: se desprenden los subárboles.
• Longitud: cantidad de ramas o aristas desde la raíz hasta el nodo de referencia.
• Profundidad: niveles de árbol, desde la raíz hasta nodo más profundo.
• Grado: la cantidad de ramas en una sola raíz.
• Recorrido: ancho, preorden, inorden y postorden.
• Tamaño: el número de nodos que tiene el árbol.
• Árbol binario: es cuando el grado del árbol es 2.
• Árbol de busqueda: contiene un factor de equilibrio dado por la altura del hijo derecho menos (-) el hijo izquierdo. FE <= 1

Operaciones árboles

• Buscar
• Insertar
• Eliminar

"recorrido inorden es el que ordena un árbol"

"árbol de busqueda organizado AVAL"

"árbol degenerado: que queda todo hacia un solo lado"

IMPLEMENTACIÓN DE ÁRBOLES BINARIOS

• arreglo: estructura estática.
• como estructuras ligadas se debe definir el tamaño del arreglo y NUNCA cambiarlo.
• overflow: desborde de información.

Árboles multicaminos

• árboles B
• árboles B+

Características

• árboles binarios
• AVL
• ABB

1. Nodo padre: mínimo un elemento y max. de 2n
2. páginas intermedias, almacenar entre n (mínimo) y un max. de 2n.
3. Todas las hojas deben tener la misma altura.

ÁRBOL B+

características:

• Nodos internos solo contienen claves o apuntadores
• Todas las hojas se encuentran al mismo nivel
• Nodos hoja, se encuentran ligadas como una lista enlazada para permitir la busqueda más eficiente.
• El mínimo número de claves es 2.

operaciones:

• Buscar
• Insertar
• Eliminar