Diccionario de Estructuras de Datos: Árboles, Hashing y Matrices
Enviado por Programa Chuletas y clasificado en Informática y Telecomunicaciones
Escrito el en 
español con un tamaño de 2,53 KB
Estructuras de Datos: Árboles y Diccionarios
- Árbol 2-3: Estructura en la cual la información se encuentra en las hojas.
- Diccionario: Conjunto en el cual solo se pueden realizar las operaciones de inserción, eliminación y búsqueda de un elemento.
Árboles Rojo-Negro
- Violación de principios: Que la raíz sea roja.
- Color del nodo a insertar: Rojo.
- Color de la raíz: Negro.
- Naturaleza: Los árboles rojo-negro son un caso particular de los árboles BST (Binary Search Tree).
Hashing y Tablas Hash
Conceptos básicos
- Tabla Hash: Estructura de datos que permite realizar inserciones, eliminaciones y búsquedas en un tiempo promedio constante, bajo ciertas hipótesis. Proporciona alta velocidad sin necesidad de que los datos estén ordenados.
- Hashing: Método donde se ejecuta una operación sobre el campo clave para obtener la dirección del elemento.
- Colisión: Ocurre cuando más de una llave se mapea a la misma localidad en una tabla hash.
Métodos de mapeo y resolución
- Método de multiplicación: Técnica para mapear llaves en una tabla hash.
- Método de división: Se mapea una clave k a uno de los m espacios de la tabla, tomando el residuo de k entre m.
- Encadenamiento: Los elementos son puestos en una lista de apuntadores en la dirección marcada por la función.
- Direccionamiento abierto: Método de resolución de colisiones que acomoda los elementos que colisionan en una posición subsiguiente y contigua.
Matrices y Algoritmos
- Permutación: Matriz que tiene un 1 en cada renglón y en cada columna, siendo los demás elementos ceros.
- Triangular inferior: Matriz en la que todos los elementos que se encuentran por arriba de la diagonal principal son ceros.
- Algoritmo de Strassen: Método para multiplicar matrices con una complejidad de O(n^2.8).
Operaciones y Aplicaciones
- Operaciones básicas de los conjuntos: Pertenece, encuentra, mínimo, unión, inserta, particiona, elimina.
- Árboles 2-3: Estructuras de datos comúnmente usadas para implementar listas ordenadas.