nodos interiores

Tema 16: Estructuras dinámicas de Información

Vista la escasa participación del publico en el sitio, estoy desarrollando algunos temas por mi cuenta aprovechando un curso de programación que imparto en Villanueva de la Serena, los temas que os pueden interesar son:

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

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