Wondershare EdrawMind
Galería de mapas mentales estructura de datos
estructura de datos
Lo más básico e importante en el campo informático actual es la estructura de datos. Este mapa mental contiene el conocimiento básico de las estructuras de datos, como estructuras lineales, estructuras de árbol, estructuras de gráficos, sus métodos de implementación y algoritmos comunes, como clasificación y búsqueda. Si desea obtener una base sólida en estructuras de datos, este mapa mental será de gran ayuda para usted. Le ayuda a aprender y comprender diferentes tipos de estructuras de datos y cómo optimizar y mejorar algoritmos con estructuras de datos adecuadas.
Editado a las 2023-02-16 10:18:56,
- Breve historia del tiempo
Este es un mapa mental sobre una breve historia del tiempo. "Una breve historia del tiempo" es una obra de divulgación científica con una influencia de gran alcance. No sólo presenta los conceptos básicos de cosmología y relatividad, sino que también analiza los agujeros negros y la expansión. del universo. temas científicos de vanguardia como la inflación y la teoría de cuerdas.
- ¿Cuáles son los métodos de fijación de precios para los subcontratos de proyectos bajo el modelo de contratación general EPC
¿Cuáles son los métodos de fijación de precios para los subcontratos de proyectos bajo el modelo de contratación general EPC? EPC (Ingeniería, Adquisiciones, Construcción) significa que el contratista general es responsable de todo el proceso de diseño, adquisición, construcción e instalación del proyecto, y es responsable de los servicios de operación de prueba.
- Puntos de conocimiento que los ingenieros de Java deben dominar en cada etapa
Los puntos de conocimiento que los ingenieros de Java deben dominar en cada etapa se presentan en detalle y el conocimiento es completo, espero que pueda ser útil para todos.
estructura de datos
- Breve historia del tiempo
Este es un mapa mental sobre una breve historia del tiempo. "Una breve historia del tiempo" es una obra de divulgación científica con una influencia de gran alcance. No sólo presenta los conceptos básicos de cosmología y relatividad, sino que también analiza los agujeros negros y la expansión. del universo. temas científicos de vanguardia como la inflación y la teoría de cuerdas.
- ¿Cuáles son los métodos de fijación de precios para los subcontratos de proyectos bajo el modelo de contratación general EPC
¿Cuáles son los métodos de fijación de precios para los subcontratos de proyectos bajo el modelo de contratación general EPC? EPC (Ingeniería, Adquisiciones, Construcción) significa que el contratista general es responsable de todo el proceso de diseño, adquisición, construcción e instalación del proyecto, y es responsable de los servicios de operación de prueba.
- Puntos de conocimiento que los ingenieros de Java deben dominar en cada etapa
Los puntos de conocimiento que los ingenieros de Java deben dominar en cada etapa se presentan en detalle y el conocimiento es completo, espero que pueda ser útil para todos.
- Recomendados
- Resumen
estructura de datos
Árboles binarios y árboles y bosques
Árboles y árboles binarios
¿Cómo convertir un árbol en un árbol binario?
Tanto la representación de hermanos secundarios de un árbol como la representación de lista enlazada binaria de un árbol binario utilizan dos punteros.
Comprender la representación del hermano menor como una lista binaria enlazada
Método de simulación manual para convertir un árbol en un árbol binario:
① Conecte los hijos del mismo nodo con líneas
② Elimine las ramas del subárbol de cada nodo de izquierda a derecha excepto la primera.
ejemplo
¿Cómo convertir un árbol binario en árbol?
Método de simulación manual para convertir un árbol binario en un árbol:
① Coloque el árbol binario en capas de arriba a abajo y ajústelo en la dirección horizontal. (Método jerárquico: cada vez que te encuentras con el hijo izquierdo, es una capa)
② Encuentre el nodo principal de cada capa. El método es que el nodo conectado a la capa anterior es el nodo principal. Por ejemplo, en la capa bcd, el nodo en la capa superior conectado a ella es a, por lo que los nodos principales de los tres nodos en bcd son todos a.
③ Conecte cada nodo de capa a su nodo principal y elimine las conexiones entre los nodos secundarios del nodo principal.
ejemplo
Bosque y árboles binarios.
Bosque: Un bosque es una colección de m (m≥0) árboles disjuntos.
¿Cómo convertir un bosque en un árbol binario?
Método de simulación manual para convertir bosque en árbol:
①Convierte cada árbol del bosque en un árbol binario
② Tome el segundo árbol como el subárbol derecho del nodo raíz del primer árbol y tome el tercer árbol como el subárbol derecho del nodo raíz del segundo árbol... y así sucesivamente.
ejemplo
¿Cómo convertir un árbol binario en un bosque?
Método de simulación manual para convertir un árbol binario en un bosque:
Desconecte repetidamente el puntero del subárbol derecho del hijo derecho del nodo raíz del árbol binario hasta que no haya ningún árbol binario con un hijo derecho del nodo raíz.
ejemplo
Atravesando árboles y bosques
Reserva: visite primero el nodo raíz y luego visite cada subárbol del nodo raíz. El acceso a los subárboles también sigue el orden de los requisitos de prioridad.
Postorden: primero visite cada subárbol del nodo raíz y luego visite el nodo raíz. El acceso a los subárboles también sigue el orden de los requisitos de prioridad.
ejemplo
El recorrido en orden previo de un árbol es igual al recorrido en orden previo de su árbol binario correspondiente, y el recorrido en orden posterior es igual al recorrido en orden de su árbol binario correspondiente.
Capítulo 7: Clasificación
Conocimientos básicos de clasificación.
Definición: Ordenar consiste en reorganizar una secuencia originalmente desordenada en una secuencia ordenada.
estabilidad de clasificación
Si hay dos elementos Ri y Rj en la lista a ordenar, y sus palabras clave correspondientes keyi = keyj, y Ri está delante de Rj antes de ordenar, si después de ordenar usando un determinado algoritmo de clasificación, Ri todavía está delante de Rj, entonces esto se llama El algoritmo de clasificación es estable; de lo contrario, se dice que es inestable.
Clasificación de clases de inserción
clasificación por inserción directa
Ordenación por inserción directa: primero use un elemento como una secuencia ordenada y luego inserte elementos posteriores en la secuencia ordenada en las posiciones apropiadas hasta que todos los elementos se inserten en la secuencia ordenada.
La complejidad del tiempo es O (n)
La clasificación por inserción directa es estable.
clasificación de media inserción
La clasificación por inserción a mitad de camino separa las dos operaciones de comparación y movimiento, es decir, primero utiliza la búsqueda a mitad de camino para encontrar la posición de inserción, luego mueve el elemento a la vez y luego inserta el elemento.
La complejidad temporal de la ordenación por media inserción es O (n ^ 2)
Estabilidad: Es la misma que la estabilidad del tipo de inserción directa y es estable.
clasificación de colinas
La idea básica de la clasificación Hill: la clasificación Hill es esencialmente una clasificación por inserción, pero divide la secuencia que se va a clasificar en varias subsecuencias y luego realiza una clasificación por inserción directa en estas subsecuencias.
① Primero divida la secuencia en incrementos 5, es decir, las palabras clave con subíndices 0, 5, 10, 15... se dividen en un grupo, y las palabras clave con subíndices 1, 6, 11, 16... se dividen en uno grupo, y luego Estos grupos se someten a clasificación por inserción directa respectivamente, lo que completa una ronda de clasificación Hill.
②Reduzca el incremento (d1=n/2, di 1= [di/2], por ejemplo, 10 secuencias de datos, el primer incremento d1=10/2=5, el segundo incremento d2= [d1/2 ]= [5 /2]=2, y el último incremento es igual a 1), por lo que la segunda ronda realiza un proceso de clasificación similar con un incremento de 2.
③La siguiente tercera ronda, cuarta ronda... son procesos similares hasta la última ronda con un incremento de 1. Este es el tipo de inserción directa mencionado anteriormente.
Complejidad temporal:... La complejidad temporal de la clasificación Hill es aproximadamente O (n ^ 1,3). En el peor de los casos, la complejidad temporal de la clasificación Hill es O (n ^ 2).
Complejidad espacial: la complejidad espacial de la clasificación Hill es O (1)
Estabilidad: inestable debido a diferentes incrementos, las palabras clave iguales se pueden dividir en dos tipos de inserción directa para la clasificación, lo que puede provocar cambios de orden relativos.
Clasificación de intercambio
Ordenamiento de burbuja
Suponga que la longitud de la lista a ordenar es n. Compare los valores de los elementos adyacentes de atrás hacia adelante (o de adelante hacia atrás si están en orden inverso (es decir, A [i-1]>A [). i]), cámbielos hasta que se complete la comparación de secuencias. Lo llamamos pase de burbuja y el resultado es que el elemento más pequeño se intercambia a la primera posición de la columna a ordenar. En la siguiente burbuja, el elemento mínimo determinado en la burbuja anterior ya no participará en la comparación, y la secuencia a ordenar se reducirá en un elemento. El resultado de cada burbuja pondrá el elemento más pequeño de la secuencia al final. posición de la secuencia,..., esto es lo máximo. Todos los elementos se pueden ordenar haciendo n-1 burbujas.
Complejidad del espacio: el espacio de almacenamiento se abre para almacenar variables intermedias durante el intercambio, por lo que la complejidad del espacio es O (1)
complejidad del tiempo
Estabilidad: cuando dos palabras clave son iguales, la condición de juicio if no se cumple, por lo que no se producirá ningún movimiento de datos. Entonces es estable.
Ordenación rápida
La clasificación rápida es un método de clasificación basado en divide y vencerás. Cada clasificación rápida selecciona cualquier elemento de la secuencia como pivote (normalmente se selecciona el primer elemento), mueve todos los elementos de la secuencia que son más pequeños que el pivote al frente del pivote y mueve todos los elementos que son más grandes que el pivote. . Ponte detrás del pivote.
1
2
complejidad del tiempo: En el mejor de los casos, la complejidad temporal es O (nlogn). Cuanto más desordenada sea la secuencia a ordenar, mayor será la eficiencia del algoritmo. En el peor de los casos, la complejidad temporal es O (n ^ 2). Cuanto más ordenada sea la secuencia a ordenar, menor será la eficiencia del algoritmo.
Complejidad espacial: Dado que la clasificación rápida es recursiva, se necesita una pila de trabajo recursiva para guardar la información necesaria para cada nivel de llamadas recursivas. Su capacidad debe ser coherente con la profundidad máxima de las llamadas recursivas. El mejor de los casos es ⌈log2(n 1)⌉ (cada partición es uniforme) y la profundidad del árbol recursivo es O(logn) En el peor de los casos, debido a que se requieren n-1 llamadas recursivas, la profundidad de la pila es O (n);
Estabilidad: la clasificación rápida es inestable debido a la existencia de palabras clave de intercambio.
Seleccionar clasificación de clase
Orden de selección simple
Complejidad del espacio: el espacio de almacenamiento adicional requerido es solo la variable intermedia utilizada al intercambiar elementos, por lo que la complejidad del espacio es O (1)
complejidad del tiempo: La operación clave es intercambiar elementos. Todo el algoritmo consta de bucles dobles. El bucle exterior va de 0 a n-2 un total de n-2 1 = n-1 veces. Para el i-ésimo bucle externo, el bucle interno se ejecuta n-1-(i 1) 1=n-i-1 veces. Cuando i = 0, el bucle interno se ejecuta n-1 veces. Cuando i = n-2, el bucle interno se ejecuta una vez, por lo que es una suma de secuencia aritmética, que totaliza (1 n-1) (n-1) /. 2=n(n-1)/2, por lo que la complejidad del tiempo es O(n^2)
Estabilidad: inestable La razón es que la parte de intercambio romperá el orden relativo.
clasificación de montón
¿Qué es un montón?
El montón es un árbol binario completo y el valor de cualquier nodo que no sea hoja no es mayor (ni menor) que el valor de sus nodos secundarios izquierdo y derecho.
Si el valor de cada nodo no es menor que el valor de sus nodos secundarios izquierdo y derecho, se denomina montón superior.
Si el valor de cada nodo no es mayor que el valor de sus nodos secundarios izquierdo y derecho, se denomina montón superior pequeño.
¿Qué es la clasificación del montón?
Sabemos que para un montón, su nodo raíz es el valor máximo (montón superior grande) o el valor mínimo (montón superior pequeño) de los valores de todos los nodos en todo el montón. Entonces, la idea de la clasificación del montón es ajustar la secuencia desordenada en un montón cada vez, luego seleccionar el valor del elemento superior del montón, agregar este valor a la secuencia ordenada, reducir la secuencia desordenada en uno y luego repetir ajuste la secuencia desordenada hasta que todas las palabras clave se agreguen a la secuencia ordenada.
complejidad del tiempo: El tiempo total de clasificación del montón se puede dividir en ① parte de construcción del montón ② n-1 ajustes hacia abajo en el montón La complejidad temporal de la clasificación del montón es O(n) O(nlog2n)=O(nlog2n)
La clasificación del montón es inestable
fusionar ordenar
Suponiendo que la tabla a ordenar contiene n registros, se puede considerar como n subtablas ordenadas, cada una con una longitud de 1, y luego fusionarlas en pares para obtener ⌈n/2⌉ tablas ordenadas con una longitud de 2 o 1 ; y luego fusionarlos de dos en dos,... y repetir esto hasta que se fusionen en una lista ordenada de longitud n. Este método de clasificación se llama clasificación por combinación bidireccional.
Por ejemplo: 49 38 65 97 76 13 27
①Primero trate cada palabra clave de la secuencia completa como una subsecuencia ordenada separada
② Fusionar de dos en dos, 49 y 38 se fusionan en {38 49}, 65 y 97 se fusionan en {65 97}, 76 y 13 se fusionan en {13 76}, 27 no tiene objeto de fusión
③ Fusionar de dos en dos, {38 49} y {65 97} se fusionan en {38 49 65 97}, {13,76} y 27 se fusionan en {13 27 76}
④ Fusionar de dos en dos, {38 49 65 97} y {13 27 76} fusionarse en {13 27 38 49 65 76 97}
Complejidad del tiempo: O (nlog2n)
Complejidad del espacio: debido a que la secuencia que se va a ordenar debe transferirse a una matriz, es necesario abrir un espacio de almacenamiento adicional de tamaño n, es decir, la complejidad del espacio es O (n)
Estabilidad: estable
Ordenación por base
La clasificación por base (también llamada clasificación por cubos) es un método de clasificación muy especial. No se clasifica en función de la comparación, sino que utiliza la idea de clasificación de varias palabras clave (es decir, clasificación según el tamaño de cada palabra clave). con la ayuda de operaciones de "asignación" y "recopilación" para ordenar palabras clave lógicas individuales. La clasificación por base se divide en clasificación con el dígito más alto primero (MSD) y clasificación con el dígito más bajo primero (LSD).
Ejemplos: 53, 3, 542, 748, 14, 214, 154, 63, 616
Dígitos suplementarios: 053, 003, 542, 748, 014, 214, 154, 063, 616
El depósito es en realidad una cola, primero en entrar, primero en salir (ingrese desde la parte superior del depósito y salga desde abajo)
El número de palabras clave es n, el número de dígitos de la palabra clave es d, por ejemplo, 748 d=3, r es el número de bases de la palabra clave, que es el tipo de datos que componen la palabra clave, por ejemplo, hay 10 dígitos decimales del 0 al 9 en total, es decir, r=10.
Complejidad del espacio: es necesario abrir varias colas de bases de palabras clave, por lo que la complejidad del espacio es O (r)
Complejidad del tiempo: se requieren D tiempos de "asignación" y "colección" para la cantidad de palabras clave. Una "asignación" requiere que se coloquen n palabras clave en cada cola, y una "colección" requiere que se recopilen r depósitos. Entonces, la complejidad temporal de una "asignación" y una "colección" es O (n r). D veces requiere una complejidad temporal de O (d (n r)).
Estabilidad: debido a que es una cola con una naturaleza de primero en entrar, primero en salir, se asigna en orden cuando se asigna, lo cual es estable, por lo que permanece estable durante la recopilación. Es decir, la clasificación por base es un algoritmo de clasificación estable.
clasificación externa
Es necesario almacenar los registros que se van a ordenar en la memoria externa y luego transferir los datos parte por parte a la memoria para su clasificación. Durante el proceso de clasificación, se requieren múltiples intercambios entre la memoria y el almacenamiento externo, y los resultados después de ordenar los registros en el archivo de almacenamiento externo aún se colocan en el archivo original. Este método de clasificación se denomina clasificación externa.
La capacidad de la memoria no puede acomodar grandes cantidades de datos.
Cómo obtener el segmento de fusión inicial
Clasificación por selección de desplazamiento: resuelva el problema de colocar segmentos de clasificación en la memoria
Cómo reducir la cantidad de fusiones de múltiples segmentos de fusión
Árbol de fusión óptimo: número mínimo de fusiones (número de E/S)
Cómo obtener rápidamente la palabra clave más pequeña para cada combinación de m vías
Árbol de perdedores: reducir el número de comparaciones
Capítulo 6: Búsqueda
Conceptos básicos de búsqueda y búsqueda secuencial.
Definición de búsqueda: el proceso de encontrar elementos de datos que cumplan ciertas condiciones en un conjunto de datos se llama búsqueda.
Palabra clave: un elemento de datos en un elemento de datos que identifica de forma única el elemento.
Longitud promedio de búsqueda (ASL: longitud promedio de búsqueda): durante el proceso de búsqueda, la duración de una búsqueda se refiere a la cantidad de palabras clave que deben compararse, y la longitud promedio de búsqueda es la cantidad promedio de comparaciones de palabras clave en todos los procesos de búsqueda. .
La búsqueda secuencial (búsqueda lineal) se utiliza principalmente para buscar en tablas lineales. Comenzando desde un extremo de la tabla de búsqueda, la tabla de búsqueda se escanea secuencialmente y las palabras clave escaneadas se comparan con la clave de valor que se encontrará. Si son iguales, la búsqueda es exitosa. Si no se encuentran elementos de datos iguales al final del análisis, la búsqueda falla.
1
2
3
4
La complejidad del tiempo es O (n)
media búsqueda
Idea de algoritmo:
Primero, compare la clave de valor dada con la clave del elemento intermedio en la tabla. Si son iguales, la búsqueda es exitosa y se devuelve la ubicación de almacenamiento del elemento. Si no son iguales, solo se puede buscar el elemento. estar en la primera mitad que no sea el elemento intermedio O en la segunda mitad. Luego continúe con la misma búsqueda dentro del rango reducido y repita esto hasta que lo encuentre, o se determine que el elemento que se va a encontrar no existe en la tabla, entonces la búsqueda no tiene éxito y se devuelve un mensaje de error de búsqueda.
Análisis de media búsqueda
Árbol de decisión de media búsqueda
Para la búsqueda binaria, el número de comparaciones es el número de nodos pasados del nodo raíz al nodo.
La altura de un árbol binario completo con N (N>0) nodos es [log2(N 1)] o [log2N] 1.
La complejidad del tiempo es O(logn)
Buscar en trozos
La búsqueda de bloques también se denomina búsqueda de secuencia de índice.
Idea de búsqueda de bloques:
① Determine en qué bloque se encuentra el valor a encontrar (búsqueda a la mitad) ② Buscar el valor a buscar en el bloque determinado (búsqueda secuencial)
Análisis de búsqueda de bloques
Dado que la búsqueda de bloques en realidad realiza dos búsquedas, la longitud de búsqueda promedio de todo el algoritmo es la suma de las longitudes de búsqueda promedio de las dos búsquedas. Es decir, fragmentación de ASL = orden de ASL reducido a la mitad
árbol de clasificación binaria
Un árbol de búsqueda binario (árbol de búsqueda binario, también llamado árbol de búsqueda binario) es un árbol vacío o un árbol binario con las siguientes propiedades ①Si el subárbol izquierdo no está vacío, entonces los valores de todos los nodos en el subárbol izquierdo son menores que el valor de su nodo raíz. ②Si el subárbol derecho no está vacío, entonces los valores de todos los nodos en el subárbol derecho son mayores que el valor de su nodo raíz. ③ Sus subárboles izquierdo y derecho también son un árbol de clasificación binario.
"La izquierda es pequeña y la derecha es grande"
pensamiento algorítmico
Debido a las características de los árboles de clasificación binaria (subárbol izquierdo <nodo raíz <subárbol derecho), cada vez que busca una palabra clave, primero debe compararla con el nodo raíz: Si esta palabra clave es menor que el valor del nodo raíz, entonces se realiza la misma operación de comparación en el subárbol izquierdo del nodo raíz y continúa hasta que se encuentra la palabra clave, lo que indica una búsqueda exitosa, o un puntero nulo, que indica una búsqueda fallida. . Si esta palabra clave es mayor que el valor del nodo raíz, entonces se realiza la misma operación de comparación en el subárbol derecho del nodo raíz y continúa hasta que se encuentra la palabra clave, lo que indica una búsqueda exitosa, o un puntero nulo, que indica una búsqueda fallida. .
Buscar códigos de palabras clave
1
2
Insertar código de palabra clave
1) Árbol vacío: inserte directamente un nuevo nodo y devuelva el éxito 2) El árbol no está vacío: compruebe si hay nodos con palabras clave repetidas: ① Existe: Devuelve error de inserción ② No existe: verifique la relación de tamaño entre el valor del nodo raíz y el valor clave que se insertará, e inserte recursivamente los subárboles izquierdo y derecho.
Código de construcción
Eliminar nodo
①Los nodos hoja se eliminan
Método: simplemente elimine el nodo directamente
② Lo que se elimina es el nodo que tiene solo el subárbol izquierdo o el subárbol derecho.
Método: "El hijo hereda el legado del padre"
③Lo que se elimina son los nodos que tienen los subárboles izquierdo y derecho.
Siguiendo el tipo ②, un hijo "heredará la herencia del padre" y el otro hijo se "someterá" a este hijo. Método: busque el nodo predecesor directo o sucesor directo del nodo que se eliminará, reemplace el nodo que se eliminará con este nodo y luego elimine el nodo.
Análisis de árbol de clasificación binaria
La complejidad del tiempo de búsqueda es O(n)
Árbol binario equilibrado (árbol AVL)
Un árbol binario equilibrado (árbol AVL) es un árbol de clasificación binaria especial. Lo especial es que el valor absoluto de la diferencia de altura entre los subárboles izquierdo y derecho no excede 1, y los subárboles izquierdo y derecho también son un árbol binario equilibrado. .
factor de equilibrio
Defina la diferencia de altura entre el subárbol izquierdo y el subárbol derecho de un nodo como el factor de equilibrio del nodo. Entonces el valor del factor de equilibrio de un nodo de árbol binario equilibrado solo puede ser −1, 0 o 1.
Ajuste de equilibrio
El proceso de establecimiento de un árbol binario equilibrado es similar al de un árbol binario ordenado. Ambos parten de un árbol vacío e insertan nodos uno tras otro. La diferencia es que en el proceso de establecer un árbol binario equilibrado, dado que insertar un nodo puede destruir el equilibrio del nodo, se requiere un ajuste del equilibrio.
Ajuste LL (causado al insertar un nodo en el subárbol izquierdo del hijo izquierdo)
El factor de equilibrio del nodo raíz del subárbol mínimo desequilibrado es 2>0 El factor de equilibrio de su nodo hijo izquierdo es 1>0 Ambos son mayores que 0, por lo que puedes ajustarlo girando a la derecha
"Rotación regular a la derecha"
Ajuste de RR (causado al insertar un nodo en el subárbol derecho del hijo derecho)
El factor de equilibrio del nodo raíz del subárbol mínimo desequilibrado es -2 <0 Su factor de equilibrio del nodo secundario derecho es -1<0 Ambos son menores que 0, por lo que puedes ajustarlo girando a la izquierda.
"Negativo significa rotación hacia la izquierda"
Ajuste LR (causado al insertar un nodo en el subárbol derecho del hijo izquierdo)
Ajuste de RL (causado al insertar un nodo en el subárbol izquierdo del hijo derecho)
Primero convierta localmente a LL o RR y finalmente ajuste
analizar
La profundidad máxima de un árbol binario equilibrado con n nodos es O (log2n). Por lo tanto, la longitud de búsqueda promedio de un árbol binario equilibrado es O (log2n).
Árbol B y árbol B
2-3 árboles
El árbol 2-3 es un árbol de búsqueda multidireccional: 2 y 3 significan que el árbol 2-3 contiene dos tipos de nodos
1) 2 nodos contienen un elemento y dos hijos (o ningún hijo). ①Los elementos contenidos en el subárbol izquierdo son menores que el valor del elemento del nodo y los elementos contenidos en el subárbol derecho son mayores que el valor del elemento del nodo. ②El nodo 2 tiene dos hijos o no tiene hijos. No se permite un hijo.
2) El nodo 3 contiene dos elementos, uno grande y otro pequeño, y tres hijos (o ningún hijo). (Los dos elementos están ordenados por tamaño) ①El subárbol izquierdo contiene elementos más pequeños que el valor del elemento más pequeño del nodo, el subárbol derecho contiene elementos mayores que el valor del elemento más grande del nodo y el subárbol del medio contiene elementos entre estos dos valores de elemento. ②El nodo 3 tiene tres hijos o ningún hijo. No se permiten uno o dos hijos.
3) Todos los nodos de hojas del árbol 2-3 están al mismo nivel
2-3-4 árbol
El árbol 2-3-4 también es un árbol de búsqueda multidireccional: 2, 3 y 4 significan que el árbol 2-3-4 contiene tres tipos de nodos.
1) 2 nodos contienen un elemento y dos hijos (o ningún hijo). ①Los elementos contenidos en el subárbol izquierdo son menores que el valor del elemento del nodo y los elementos contenidos en el subárbol derecho son mayores que el valor del elemento del nodo. ②El nodo 2 tiene dos hijos o no tiene hijos. No se permite un hijo.
2) El nodo 3 contiene dos elementos, uno grande y otro pequeño, y tres hijos (o ningún hijo). ①El subárbol izquierdo contiene elementos más pequeños que el valor del elemento más pequeño del nodo, el subárbol derecho contiene elementos mayores que el valor del elemento más grande del nodo y el subárbol del medio contiene elementos entre estos dos valores de elemento. ②El nodo 3 tiene tres hijos o ningún hijo. No se permiten uno o dos hijos.
3) El nodo 4 contiene tres elementos, pequeño, mediano y grande, y cuatro hijos (o ningún hijo). ① El subárbol izquierdo contiene elementos menores que el valor del elemento más pequeño del nodo, el segundo subárbol contiene elementos mayores que el valor del elemento más pequeño y menores que el valor del elemento medio, el tercer subárbol contiene elementos mayores que el valor del elemento medio y menores que el valor máximo del elemento, derecha El subárbol contiene elementos mayores que el valor de elemento más grande del nodo. ②El nodo 4 tiene cuatro hijos o no tiene hijos. No se permiten uno, dos o tres hijos.
4) Todos los nodos de hojas del árbol 2-3-4 están al mismo nivel
árbol B
El árbol B también es un árbol de búsqueda equilibrado de rutas múltiples. El árbol 2-3 y el árbol 2-3-4 son casos especiales del árbol B. Llamamos al mayor número de hijos de un nodo en el árbol. el orden del árbol B. Generalmente escrito como m. Un árbol B de orden m es un árbol vacío o un árbol m-ario que satisface las siguientes características:
1) Cada nodo del árbol tiene como máximo m subárboles. (Es decir, contiene como máximo m-1 palabras clave) ("Dos punteros de subárbol intercalan una palabra clave")
2) Si el nodo raíz no es un nodo terminal, hay al menos dos subárboles. (al menos una palabra clave)
3) Todos los nodos que no son hoja, excepto el nodo raíz, tienen al menos ⌈m/2⌉ subárboles. (Es decir, contiene al menos ⌈m/2⌉-1 palabras clave)
4) La estructura de todos los nodos no hoja es la siguiente:
5) Todos los nodos de hoja aparecen en el mismo nivel sin información. (Al igual que el nodo donde falló la búsqueda en el árbol de juicio de búsqueda binaria)
1. Operación de búsqueda del árbol B
Proceso de búsqueda: ① Primero compare la clave de palabra clave que se encontrará con las palabras clave en el nodo. Si es igual a una de las palabras clave, la búsqueda es exitosa. ② Si no es igual a todas las palabras clave, verifique en qué rango se encuentra la clave y luego busque en el subárbol señalado por el puntero correspondiente. Por ejemplo: si Key es menor que la primera palabra clave K1, busque en el subárbol señalado por el puntero P0. Si es mayor que la última palabra clave Kn, busque en el subárbol señalado por el puntero Pn.
2. Operación de inserción del árbol B
Método de división: tome la palabra clave del medio (⌈n/2⌉) en esta matriz de palabras clave como el nuevo nodo y luego use las otras palabras clave para formar dos nodos como los hijos izquierdo y derecho del nuevo nodo.
3.Operación de eliminación del árbol B
La operación de eliminación en el árbol B es similar a la operación de inserción, pero es un poco más complicada. Debe hacer que el número de palabras clave en el nodo eliminado sea ≥⌈m/2⌉-1, por lo que implicará la "fusión". problema de nodos. Debido a las diferentes posiciones de las palabras clave eliminadas, se puede dividir en dos situaciones: la palabra clave está en el nodo terminal y la palabra clave no está en el nodo terminal.
1) Si la palabra clave eliminada está en el nodo terminal (el nodo no hoja más bajo): ①El número de palabras clave en el nodo es mayor que ⌈m/2⌉-1. En este caso, eliminar esta palabra clave no destruirá los requisitos de definición del árbol B. Así que elimínelo directamente. ②Si el número de palabras clave en un nodo es igual a ⌈m/2⌉-1, y hay nodos con un número de palabras clave mayor que ⌈m/2⌉-1 en sus nodos hermanos izquierdo y derecho, entonces tome prestadas palabras clave del etapa de hermanos. ③Si el número de palabras clave en un nodo es igual a ⌈m/2⌉-1 y no hay ningún nodo con un número de palabras clave mayor que ⌈m/2⌉-1 en sus nodos hermanos izquierdo y derecho, se requiere la fusión de nodos .
2) Si la palabra clave eliminada no está en el nodo terminal (el nodo no hoja de nivel más bajo): primero debe convertirse para que esté en el nodo terminal y luego se consideran los métodos correspondientes de acuerdo con la situación en el nodo terminal. .
Palabras clave adyacentes: para una palabra clave que no está en un nodo terminal, su palabra clave adyacente es la palabra clave con el valor más grande en su subárbol izquierdo o la palabra clave con el valor más pequeño en su subárbol derecho.
El primer caso: hay un subárbol izquierdo o un subárbol derecho con un número de palabras clave mayor que ⌈m/2⌉-1. Busque las palabras clave adyacentes de la palabra clave en el subárbol correspondiente y luego reemplace las palabras clave adyacentes que se eliminarán. .
El segundo caso: el número de palabras clave en los subárboles izquierdo y derecho es igual a ⌈m / 2⌉-1, luego los dos nodos del subárbol izquierdo y derecho se fusionan y luego se eliminan las palabras clave que se eliminarán.
árbol B
B-tree es una estructura de datos comúnmente utilizada en bases de datos y sistemas de archivos de sistemas operativos para búsqueda.
La principal diferencia entre el árbol B de orden m y el árbol B de orden m es: 1) En el árbol B, un nodo con n palabras clave solo contiene n subárboles, es decir, cada palabra clave corresponde a un subárbol, mientras que en el árbol B, un nodo con n palabras clave contiene (n 1) Un árbol. 2) En el árbol B, el rango del número n de palabras clave en cada nodo (nodo interno no raíz) es ⌈m/2⌉≤n≤m (nodo raíz 1≤n≤m en el árbol B). árbol, el rango del número n de palabras clave para cada nodo (nodo interno no raíz) es ⌈m/2⌉ -1≤n≤m-1 (nodo raíz: 1≤n≤m-1). 3) En el árbol B, los nodos hoja contienen información y todos los nodos que no son hoja solo sirven como índice. Cada elemento de índice en un nodo que no es hoja solo contiene la palabra clave máxima del subárbol correspondiente y un puntero al subárbol. no contiene la dirección de almacenamiento del registro correspondiente a la palabra clave. 4) En el árbol B, los nodos hoja contienen todas las palabras clave, es decir, las palabras clave que aparecen en los nodos que no son hoja también aparecerán en los nodos hoja en el árbol B, los nodos hoja contienen palabras clave y las palabras clave contenidas en otros nodos no; repetido.
tabla de picadillo
Tabla hash: una estructura de datos que calcula la dirección de la palabra clave en la tabla en función de una palabra clave determinada. En otras palabras, la tabla hash establece una relación de mapeo directo entre palabras clave y direcciones de almacenamiento.
Función hash: una función que asigna palabras clave en la tabla de búsqueda a la dirección correspondiente a la palabra clave, registrada como Hash (clave) = Dirección.
La función hash puede asignar dos o más palabras clave diferentes a la misma dirección, lo que se denomina "colisión". Estas diferentes palabras clave que chocan se denominan sinónimos.
Consejos para construir funciones hash:
1) El dominio de la función hash debe incluir todas las palabras clave que deben almacenarse, y el rango del dominio de valores depende del tamaño o rango de direcciones de la tabla hash.
2) Las direcciones calculadas por la función hash deben distribuirse uniformemente en todo el espacio de direcciones con la misma probabilidad, reduciendo así la aparición de conflictos.
3) La función hash debe ser lo más simple posible y poder calcular la dirección hash correspondiente a cualquier palabra clave en poco tiempo.
1. Métodos de construcción de funciones Hash de uso común:
1. Método de direccionamiento abierto: tome directamente un valor de función lineal de la palabra clave como dirección hash, y la función hash es H (clave) = a × clave b. En la fórmula, a y b son constantes. Este método es el más sencillo de calcular y no causará conflictos.
2. Método de división con resto: suponga que la longitud de la tabla hash es m, tome un número primo p que no sea mayor que m pero más cercano o igual a m, y use la siguiente fórmula para convertir la palabra clave en una dirección hash . La función hash es H(clave)=clave % p La clave del método restante es elegir p para que cada palabra clave pueda asignarse a cualquier dirección en el espacio hash con la misma probabilidad después de ser convertida por esta función, reduciendo así la posibilidad de conflictos tanto como sea posible.
3. Método de análisis digital: suponga que la palabra clave es un número de base r (como un número decimal) y la frecuencia de aparición de r números en cada posición no es necesariamente la misma y puede estar distribuida de manera más uniforme en algunas posiciones. La probabilidad de que aparezca cada número Si algunos bits están distribuidos de manera desigual y solo ciertos números aparecen con frecuencia, entonces se deben seleccionar algunos bits con una distribución de números más uniforme como dirección hash. Este método es adecuado para conjuntos de palabras clave conocidos.
4. Método del cuadrado medio: como sugiere el nombre, los dígitos medios del valor cuadrado de la palabra clave se toman como dirección hash. La cantidad específica de bits a tomar depende de la situación real. La dirección hash obtenida por este método está relacionada con cada bit de la palabra clave, lo que hace que la distribución de la dirección hash sea más uniforme.
5. Método de plegado: divida la palabra clave en varias partes con el mismo número de dígitos (el número de dígitos en la última parte puede ser más corto) y luego tome la suma superpuesta de estas partes como la dirección hash. método de plegado. Cuando hay muchos dígitos en la palabra clave y los números de cada dígito de la palabra clave están distribuidos aproximadamente uniformemente, se puede utilizar el método de plegado para obtener la dirección hash.
2. Métodos de manejo de conflictos para funciones Hash de uso común:
1. Método de direccionamiento abierto: utilice la dirección Hash en conflicto como una variable independiente y obtenga una nueva dirección Hash libre a través de una determinada función de resolución de conflictos.
1) Método de detección lineal: cuando ocurre un conflicto, verifique la siguiente unidad en la tabla secuencialmente (cuando se detecta la dirección al final de la tabla m-1, la siguiente dirección de detección es la dirección al comienzo de la tabla 0) hasta que se encuentre una unidad inactiva (cuando la tabla no esté llena). Se debe encontrar una unidad libre cuando esté llena) o se pueda buscar en toda la tabla.
2) Método de detección de cuadrados: suponga que la dirección en conflicto es d y la nueva secuencia de direcciones obtenida mediante el método de detección de cuadrados es d 12, d-12, d 22, d-22 ... El método de detección de cuadrados es una mejor manera de lidiar con conflictos y puede evitar el problema de "acumulación". Su desventaja es que no puede detectar todas las celdas en la tabla hash, pero puede detectar al menos la mitad de las celdas.
3) Método de repetición: también llamado método de doble hash. Es necesario utilizar dos funciones hash. Cuando la dirección obtenida a través de la primera función hash H (clave) entra en conflicto, se utiliza la segunda función hash Hash2 (clave) para calcular el incremento de dirección de la clave.
4) Método de secuencia pseudoaleatoria: cuando ocurre un conflicto de direcciones, el incremento de dirección es una secuencia de números pseudoaleatoria, que se denomina método de secuencia pseudoaleatoria.
2. Método de cremallera: se pueden asignar diferentes palabras clave a la misma dirección a través de una función hash. Para evitar conflictos entre sinónimos, todos los sinónimos se pueden almacenar en una lista enlazada lineal. Esta lista enlazada lineal se identifica de forma única por su hash. DIRECCIÓN. . El método de cremallera es adecuado para situaciones en las que las inserciones y retiradas son frecuentes.
3. El proceso de búsqueda de la tabla hash: similar a construir una tabla hash, dada una clave clave. Primero calcule su dirección hash según la función hash. Luego verifique si hay una palabra clave en la ubicación de la dirección hash. 1) Si no, significa que la palabra clave no existe y se devuelve un error de búsqueda. 2) Si lo hay, verifique si el registro es igual a la palabra clave. ①Si es igual a la palabra clave, devuelve el éxito de la búsqueda. ② Si no es igual, calcule la siguiente dirección hash de acuerdo con el método de manejo de conflictos dado y luego use esta dirección para realizar el proceso anterior.
4. El rendimiento de búsqueda de la tabla hash: relacionado con el factor de llenado.
Cuanto mayor es α, más "llenos" están los registros llenos y mayor es la posibilidad de conflicto. Por el contrario, menor es la posibilidad de conflicto.
Capítulo 5: Imagen
Conceptos básicos de gráficos.
definición: Un árbol es un conjunto finito de N (N≥0) nodos. Cuando N = 0, se llama árbol vacío, que es un caso especial. En cualquier árbol no vacío debería satisfacer: 1) Existe y solo existe un nodo específico llamado raíz. 2) Cuando N>1, los nodos restantes se pueden dividir en m (m>0) conjuntos finitos disjuntos T1, T2,..., Tm, cada uno de los cuales es en sí mismo un árbol y se denomina subárbol del. nodo.
El gráfico G consta de un conjunto de vértices V y un conjunto de aristas E, denotado como G = (V, E)
V(G) representa un conjunto finito no vacío de vértices en el gráfico G. Utilice |V| para representar el número de vértices en el gráfico G, también llamado orden del gráfico G.
E(G) representa el conjunto de relaciones (aristas) entre vértices en el gráfico G. Sea |E| el número de aristas en el gráfico G.
Clasificación
gráfico dirigido
Un conjunto finito de aristas dirigidas (arcos)
Un arco es un par ordenado de vértices.
v es la cola del arco, w es la cabeza del arco
v es adyacente a w o w es adyacente a v
Gráfico no dirigido
Conjunto finito de aristas no dirigidas.
Las aristas son pares de vértices desordenados.
(v,w)
(v,w)=(w,v)
w y v son puntos adyacentes entre sí
diagrama simple
1. No hay arista desde el vértice hacia sí mismo.
2. El mismo borde no aparece repetidamente
múltiples gráficos
Si hay más de una arista entre dos nodos en el gráfico G, se permite que los vértices estén asociados entre sí a través de la misma arista.
grafico completo
gráfico completo no dirigido
Si hay una arista entre dos vértices cualesquiera
Gráfico completo dirigido
Si hay dos arcos en direcciones opuestas entre dos vértices cualesquiera
subtrama
Gráfico conectado: dos vértices cualesquiera del gráfico están conectados
Componentes conectados: subgrafos conectados máximos en gráficos no dirigidos
conectado
Hay un camino desde el vértice A al vértice B.
excelente
1. Hay suficientes vértices
2. Un subgrafo conectado máximo contiene todas las aristas adjuntas a estos vértices.
Cómo encontrar componentes conectados: Comience seleccionando un vértice, use este vértice como subgrafo y luego agregue los vértices y aristas conectados a este subgrafo uno por uno hasta que todos los vértices conectados se agreguen al subgrafo.
Conclusión 1: Si un gráfico tiene n vértices y menos de n-1 aristas, entonces el gráfico debe ser un gráfico desconectado.
Fuertemente conectado: hay caminos desde el vértice V al vértice W y desde el vértice W al vértice V.
Gráfico fuertemente conectado: cualquier par de vértices del gráfico está fuertemente conectado
Árbol de expansión de un gráfico conectado: un subgrafo conectado mínimo que contiene los n vértices del gráfico pero solo n-1 aristas.
Conclusión 2: Eliminar una arista de un árbol de expansión dará como resultado un gráfico no conectado, y agregar una arista formará un ciclo.
Grado: el número de aristas con este vértice como punto final
El grado de un vértice V en un gráfico no dirigido se refiere al número de aristas unidas al vértice, registrado como TD(v)
El grado del vértice V en un gráfico dirigido se divide en grados de salida y de entrada.
El grado (ID) es el número de aristas dirigidas que terminan en el vértice v.
El grado exterior (OD) es el número de aristas dirigidas a partir del vértice V
Camino simple y circuito simple: Un camino cuyos vértices no aparecen repetidamente se llama camino simple. Para un bucle, un bucle en el que los vértices no aparecen repetidamente excepto el primer y el último vértice se denomina bucle simple.
Quanhe Net: a cada borde del gráfico se le asigna un valor determinado en el examen de ingreso de posgrado. Este valor se denomina peso de este borde. El gráfico ponderado se denomina gráfico ponderado, también llamado red.
Ruta y longitud de la ruta: la ruta entre los vértices p a q se refiere a la secuencia de vértices que está almacenada, p, a, b, c, d,...q. El número encima del camino es la longitud del camino.
Bucle (anillo): Un camino cuyo primer y último vértice son iguales se llama bucle o bucle.
Distancia: La longitud del camino más corto desde el vértice u al v. Si no hay camino, es infinito.
Estructura de almacenamiento de gráficos
Matriz de adyacencia (almacenada secuencialmente)
Lista de adyacencia (almacenamiento vinculado)
Lista de enlaces cruzados (gráfico dirigido)
Lista múltiple de adyacencia (gráfico no dirigido)
Recorrido de gráficos
primer recorrido en profundidad
Búsqueda en profundidad primero (DFS: Depth-First-Search): la búsqueda en profundidad primero es similar al algoritmo transversal de pedido previo de un árbol
Complejidad del espacio: dado que DFS es un algoritmo recursivo, la recursividad requiere una pila de trabajo para ayudar en el trabajo. Como máximo, todos los vértices del gráfico deben insertarse en la pila, por lo que la complejidad del tiempo es O (| V |).
Complejidad temporal: 1) Lista de adyacencia: la operación principal del proceso transversal es atravesar sus puntos adyacentes para un vértice. Dado que los puntos adyacentes se encuentran accediendo a la tabla de bordes, la complejidad temporal es O (| E |), y la complejidad temporal es O (| E |). El tiempo para acceder a los vértices es O. (|V|), por lo que la complejidad del tiempo total es O(|V| |E|). 2) Matriz de adyacencia: la complejidad temporal de encontrar los puntos adyacentes de cada vértice es O (| V |), y se busca cada vértice, por lo que la complejidad temporal total es O (| V | 2)
recorrido de amplitud primero
Búsqueda primero en amplitud (BFS: búsqueda primero en amplitud): la búsqueda primero en amplitud es similar al algoritmo transversal de orden de nivel de un árbol
Complejidad espacial: BFS necesita usar una cola y n vértices deben ponerse en cola una vez, por lo que, en el peor de los casos, si hay n vértices en la cola, entonces se requiere una complejidad espacial de O (| V |).
complejidad del tiempo: 1) Lista de adyacencia: cada vértice se ingresa en la cola una vez y la complejidad temporal es O (| V |). Para cada vértice, buscar sus puntos adyacentes requiere visitar todos los bordes de este vértice, por lo que la complejidad temporal es O. ( |mi|). Entonces la complejidad del tiempo total es O(|V| |E|) 2) Matriz de adyacencia: cada vértice se ingresa en la cola una vez y la complejidad temporal es O (| V |). Para cada vértice, buscar sus puntos adyacentes requiere atravesar una fila de la matriz, por lo que la complejidad temporal es O (). |V |), por lo que la complejidad del tiempo total es O(|V|2)
Aplicación de diagramas
árbol de expansión mínimo
prlm
① Encuentre el primer vértice inicial v0 en el gráfico como el primer vértice del árbol de expansión y luego seleccione el borde con el peso más pequeño de todos los bordes desde este vértice hasta otros vértices. Luego agregue el otro vértice v de este borde y este borde al árbol de expansión.
② Para todos los demás vértices restantes, verifique si los pesos de estos vértices y el vértice v son menores que los pesos correspondientes de estos vértices en la matriz de bajo costo. Si son más pequeños, actualice la matriz de bajo costo con pesos más pequeños.
③Continúe seleccionando el borde con el peso más pequeño y que no esté en el árbol de expansión de la matriz de bajo costo actualizada, y luego agréguelo al árbol de expansión.
④ Repita ②③ hasta que todos los vértices se agreguen al árbol de expansión.
En un bucle doble, el número de veces del bucle exterior es n-1 y el número de veces de los dos bucles internos en paralelo es n. Por tanto, la complejidad temporal del algoritmo de Prim es O(n2) Además, la complejidad del tiempo solo está relacionada con n, por lo que es adecuada para gráficos densos.
Kruskal
Organice los bordes en el gráfico de acuerdo con sus pesos de pequeño a grande, luego escanee desde el borde más pequeño y establezca un conjunto de bordes para registrar. Si el borde no forma un bucle, el borde se fusionará en el árbol de expansión actual. . Hasta que se hayan detectado todos los bordes.
La operación del algoritmo de Kruskal se divide en la parte de clasificación por peso de los bordes y un bucle for único. Están en una relación paralela. Dado que la clasificación lleva más tiempo que el bucle único, el tiempo principal del algoritmo de Kruskal se dedica a la clasificación. La clasificación está relacionada con la cantidad de aristas en el gráfico, por lo que es adecuada para gráficos dispersos.
camino más corto
Dijkstra
El camino más corto desde un punto fuente a otros vértices.
Este algoritmo establece un conjunto S para registrar los vértices de la ruta más corta que se ha obtenido. Puede implementarse mediante una matriz s[], inicializada a 0. Cuando s[vi]=1, significa que se coloca el vértice vi. en S. Inicialmente, la fuente apunta v0 y la coloca en S. Además, durante la construcción se instalan dos conjuntos auxiliares: dist []: registra la longitud de la ruta más corta actual desde el punto de origen v0 a otros vértices. El valor inicial de dist [i] es arcs [v0] [i]. ruta []: ruta [i] representa el nodo predecesor de la ruta más corta desde el punto de origen hasta el vértice i. Al final del algoritmo, la ruta más corta desde el punto de origen v0 hasta el vértice vi se puede rastrear en función de su valor. Supongamos que comienza desde el vértice 0, es decir, el vértice 0 es el punto de origen. El conjunto S inicialmente solo contiene el vértice 0. Los arcos de la matriz de adyacencia representan el gráfico dirigido ponderado y los arcos [i] [j] representan el peso del borde dirigido. <i,j> Valor, si no hay un borde dirigido <i, j>, entonces los arcos [i] [j] son ∞. Los pasos del algoritmo de Dijkstra son los siguientes: 1) Inicialización: el conjunto S es inicialmente {0}, el valor inicial de dist[] es dist[i]=arcs[0][i], i=1, 2,..., n-1. 2) Encuentre el valor mínimo dist [j] en dist [] y agregue el vértice j al conjunto S, es decir, modifique s [vj] = 1. 3) Modifique la longitud del camino más corto desde v0 hasta cualquier vértice vk en el conjunto V-S: si dist[j] arcos[j][k]< dist[k], entonces dist[k]=dist[j] arcos [j][k]. Además, actualice la ruta [k] = j (es decir, después de agregar el vértice j al conjunto, si hay una nueva ruta que acorta la ruta al vértice k, la longitud de la ruta al vértice k se modificará a uno más corto) 4) Repita las operaciones 2) a 3) un total de n-1 veces hasta que todos los vértices estén incluidos en S.
Freud
El camino más corto desde todos los vértices a todos los vértices.
Idea algorítmica: La recursividad produce una secuencia de matriz cuadrada de orden n A(−1), A(0),…,A(k),…,A(n−1) Entre ellos, A (k) [i] [j] representa la longitud del camino desde el vértice vi al vértice vj, y k representa el paso de operación para omitir el k-ésimo vértice. Inicialmente, para dos vértices vi y vj cualesquiera, si hay un borde entre ellos, el peso en este borde se usa como la longitud del camino más corto entre ellos, si no hay un borde dirigido entre ellos, ∞ se usa como la longitud del camino más corto; entre ellos. En el futuro, intentaremos agregar gradualmente el vértice k (k = 0, 1, ..., n-1) como un vértice intermedio en la ruta original. Si después de agregar vértices intermedios, el camino resultante es más corto que el camino original, reemplace el camino original con este nuevo camino.
Gráfico no ponderado
El camino con el menor número de aristas entre dos puntos.
gráfico ponderado
El camino entre dos puntos que tiene la suma más pequeña de pesos de borde.
clasificación topológica
AOV
Si consideramos cada enlace como un vértice en el gráfico, en un gráfico dirigido de este tipo, utilizando vértices para representar actividades y arcos para representar las relaciones de prioridad entre actividades, entonces dicho gráfico dirigido se denomina red AOV (Actividad en vértice).
La clasificación topológica es el proceso de construir una secuencia topológica para un gráfico dirigido. La construcción tendrá dos resultados: Si se generan todos los vértices de este gráfico, significa que es una red AOV sin bucles; Si no se generan todos los vértices, significa que hay un bucle en este gráfico y no es una red AOV.
Algoritmo de clasificación topológica: Seleccione un vértice con un grado de entrada de 0 de la red AOV para generar, luego elimine este vértice y elimine el arco con este vértice como cola del arco. Repita este paso hasta que se generen todos los vértices del gráfico de salida o no se encuentre ningún vértice con grado de entrada 0.
Camino critico
AOE (Actividad en el borde): en un gráfico dirigido ponderado que representa un proyecto, los vértices se usan para representar eventos, los bordes dirigidos se usan para representar actividades y los pesos en los bordes se usan para representar la duración de las actividades. gráfico La red que representa la actividad se llama red AOE.
Capítulo 1: Estructura de datos concepto basico
definición
En cualquier problema, los elementos de datos no existen de forma aislada, sino que existe una cierta relación entre ellos. Esta relación entre los elementos de datos se llama estructura. Una estructura de datos es una colección de elementos de datos que tienen una o más relaciones específicas entre sí. La estructura de datos incluye tres aspectos: estructura lógica, estructura de almacenamiento y operación de datos. La estructura lógica y la estructura de almacenamiento de los datos son dos aspectos inseparables. El diseño de un algoritmo depende de la estructura lógica seleccionada y la implementación del algoritmo depende de la estructura de almacenamiento utilizada.
estructura lógica
La estructura lógica se refiere a la relación lógica entre elementos de datos, es decir, describir los datos en términos de relaciones lógicas. No tiene nada que ver con el almacenamiento de datos y es independiente del ordenador.
La estructura lógica de los datos se divide en estructura lineal y estructura no lineal.
No existe otra relación entre los elementos de datos en la estructura del conjunto que no sea la relación de "pertenencia al mismo conjunto". Similar a un conjunto matemático
Estructura lineal Sólo existe una relación uno a uno entre los elementos de datos de la estructura. Como hacer cola
Estructura de árbol Existe una relación de uno a muchos entre los elementos de datos de la estructura. Como la genealogía familiar.
Estructura gráfica o estructura de red Existe una relación de muchos a muchos entre los elementos de datos de la estructura. Como mapa
estructura física
La estructura de almacenamiento se refiere a la representación de la estructura de datos en la computadora (también llamada imagen), también llamada estructura física. Incluye la representación de elementos de datos y la representación de relaciones. La estructura de almacenamiento de datos es la realización de una estructura lógica en el lenguaje informático, que depende del lenguaje informático. Las estructuras de almacenamiento de datos incluyen principalmente: almacenamiento secuencial, almacenamiento en cadena, almacenamiento de índice y almacenamiento hash.
Almacenamiento secuencial: Las ubicaciones físicas de almacenamiento son adyacentes. (p.d. La ubicación física es la ubicación de la información en la computadora).
Almacenamiento vinculado: las ubicaciones físicas de almacenamiento pueden no ser adyacentes. Los elementos adyacentes se encuentran registrando las ubicaciones físicas de los elementos adyacentes.
Almacenamiento de índice: similar a un directorio, puede consultar el capítulo del sistema de archivos del sistema operativo para comprenderlo más adelante.
Almacenamiento hash: calcula directamente la dirección física del elemento mediante palabras clave (se explica en detalle más adelante).
Cinco características de los algoritmos.
1. Finitud: termina después de un número finito de pasos
2. Certeza: no hay ambigüedad, es decir, no hay ambigüedad
3. Viabilidad: por ejemplo, limitados por la potencia informática de las computadoras, algunos algoritmos, aunque teóricamente factibles, no se pueden completar en la práctica.
4. Entrada: Varios tipos de datos que la computadora puede procesar, como números, audio, imágenes, etc.
5. Salida: uno o más resultados de salida del programa.
complejidad del algoritmo
complejidad del tiempo:
• Se utiliza para medir qué tan rápido aumenta el tiempo de ejecución del algoritmo a medida que aumenta el tamaño del problema;
• Es función del tamaño del problema: T(n) es función de la escala de tiempo. La complejidad del tiempo analiza principalmente el orden de magnitud de T(n).
• T(n)=O(f(n)) f(n) es la frecuencia de las operaciones básicas en el algoritmo. Generalmente, consideramos la complejidad del tiempo en el peor de los casos.
Complejidad espacial:
• Se utiliza para medir la velocidad del espacio requerido por el algoritmo a medida que aumenta el tamaño del problema;
• Es función del tamaño del problema: S(n)=O(g(n)); la tasa de crecimiento del espacio requerido por el algoritmo es la misma que la tasa de crecimiento de g(n).
Centrarse en el cálculo de la complejidad
Relaciones de complejidad temporal de uso común:
Cómo calcular la complejidad
Cálculo de la complejidad del tiempo (cuerpo de bucle único)
Centrarse directamente en el número de ejecuciones del cuerpo del bucle, establecido en k
Cálculo de la complejidad del tiempo (múltiples cuerpos de bucle)
Dos reglas de operación: regla de multiplicación y regla de suma.
Capítulo 2: Mesa lineal
La estructura lógica de una tabla lineal.
Definición: Una tabla lineal es una secuencia finita de n (n≥0) elementos de datos del mismo tipo de datos. Donde n es la longitud de la mesa. Cuando n = 0, la tabla lineal es una tabla vacía
Características: el primer elemento de la lista lineal se denomina elemento de encabezado; el último elemento se denomina elemento de cola. Excepto el primer elemento, cada elemento tiene exactamente un predecesor directo. Cada elemento excepto el último elemento tiene exactamente un sucesor directo.
Estructura de almacenamiento secuencial de mesa lineal.
El almacenamiento secuencial de tablas lineales también se denomina tablas secuenciales. Utiliza un conjunto de unidades de almacenamiento con direcciones consecutivas (como matrices en lenguaje C) para almacenar elementos de datos en una tabla lineal en secuencia, haciendo así que la lógica Dos elementos editorialmente adyacentes también lo son físicamente.
Tres atributos para crear una tabla de secuencia: 1. La posición inicial del espacio de almacenamiento (datos del nombre de la matriz) 2. Capacidad máxima de almacenamiento de la tabla de secuencia (MaxSize) 3. La longitud actual de la tabla de secuencia (longitud)
De hecho, las matrices también pueden asignar espacio dinámicamente. El espacio para almacenar matrices se asigna mediante declaraciones de asignación de almacenamiento dinámicas durante la ejecución del programa.
Resumir:
1. La característica principal de la tabla de secuencia es el acceso aleatorio (basado en matrices en lenguaje C), es decir, el elemento especificado se puede encontrar en tiempo O (1) a través de la primera dirección y el número de serie del elemento.
2. La densidad de almacenamiento de la tabla de secuencia es alta y cada nodo solo almacena elementos de datos. No es necesario gastar espacio en los elementos de la tabla para establecer relaciones lógicas entre ellos (debido a las características de ubicación física adyacente)
3. Los elementos lógicamente adyacentes en la tabla de secuencia también lo son físicamente, por lo que las operaciones de inserción y eliminación requieren mover una gran cantidad de elementos.
Operaciones de tabla de secuencia
1.Insertar
Idea de algoritmo:
1. Determinar si el valor de i es correcto.
2. Determine si la longitud de la tabla excede la longitud de la matriz
3. De atrás hacia adelante hasta la i-ésima posición, mueva cada uno de estos elementos hacia atrás una posición.
4. Inserte el elemento en la posición i y modifique la longitud de la tabla.
código
analizar:
Mejor caso: al insertar al final de la tabla (es decir, i = n 1), la declaración de movimiento del elemento no se ejecutará y la complejidad del tiempo es O (1).
En el peor de los casos: al insertar en el encabezado de la tabla (es decir, i=1), se ejecutará la instrucción de movimiento del elemento. n veces, la complejidad del tiempo es O (n).
Caso promedio: Supongamos que pi (pi=1/(n 1)) se inserta en la i-ésima posición La probabilidad de un nodo, luego inserte un nodo en una lista lineal de longitud n El número promedio de veces que es necesario mover un nodo es
2.Eliminar
Idea de algoritmo:
1. Determinar si el valor de i es correcto.
2. Obtén el elemento eliminado.
3. Mueva todos los elementos después del elemento eliminado hacia adelante una posición en secuencia.
4. Modificar la longitud de la tabla
código
analizar
En el mejor de los casos: elimine el elemento al final de la tabla (es decir, i = n) sin mover el elemento, y la complejidad temporal es O (1).
En el peor de los casos: eliminar el elemento del encabezado (es decir, i = 1) requiere mover todos los elementos excepto el primer elemento, y la complejidad del tiempo es O (n).
Situación promedio: suponiendo que pi (pi = 1/n) es la probabilidad de eliminar el nodo en la posición i-ésima, entonces el número promedio de veces que es necesario mover el nodo al eliminar un nodo en una lista lineal de longitud n es
Estructura de almacenamiento vinculada de mesa lineal.
El almacenamiento vinculado de tablas lineales se refiere al almacenamiento de elementos de datos en tablas lineales a través de un conjunto de unidades de almacenamiento arbitrarias.
¿Cuál es la diferencia entre nodo principal y puntero principal?
Independientemente de si hay un nodo principal o no, el puntero principal siempre apunta al primer nodo de la lista vinculada, y el nodo principal es el primer nodo en la lista vinculada de nodos encabezados. Por lo general, no se almacena información en el nodo.
¿Por qué configurar el nodo de encabezado?
1. Es fácil de procesar y operar. Por ejemplo, las operaciones de insertar un nodo antes del primer nodo del elemento y eliminar el primer nodo están unificadas con las operaciones de otros nodos.
2. Independientemente de si la lista vinculada está vacía o no, su puntero principal es un puntero no nulo que apunta al nodo principal, por lo que el procesamiento de listas vacías y no vacías está unificado.
Operaciones de lista enlazada única
1. Cree una lista enlazada individualmente utilizando el método de inserción de encabezado:
Cree un nuevo nodo, asigne espacio de memoria e inserte el nuevo nodo en el encabezado de la lista vinculada actual.
código
2. Cree una lista enlazada individualmente utilizando el método de inserción de cola:
Cree un nuevo nodo, asigne espacio de memoria e inserte el nuevo nodo al final de la lista vinculada actual.
código
3. Buscar nodos por número de serie
Comenzando desde el primer nodo en la lista enlazada individualmente, busque el siguiente campo uno por uno hasta encontrar el i-ésimo nodo; de lo contrario, se devuelve NULL en el campo de puntero del último nodo.
código
4. Encuentra nodos por valor
Comenzando desde el primer nodo de la lista enlazada individualmente, compare los valores de los campos de datos de cada nodo en la lista de adelante hacia atrás. Si el valor del campo de datos de un nodo es igual al valor dado e, entonces. devuelve el puntero del nodo; si toda la lista enlazada única no existe tal nodo en la lista enlazada, se devuelve NULL.
código
5. insertar
La operación de inserción consiste en insertar un nuevo nodo con valor x en la i-ésima posición de la lista enlazada individualmente. Primero verifique la legalidad de la posición de inserción, luego busque el nodo predecesor de la posición que se va a insertar, es decir, el nodo i-1, y luego inserte el nuevo nodo después de él.
Idea de algoritmo: 1. Obtenga el puntero al nodo predecesor de la posición de inserción. ① p=GetElem(L,i-1); 2. Deje que el campo de puntero del nuevo nodo *s apunte al nodo sucesor de *p ② s->siguiente=p->siguiente; 3. Deje que el campo de puntero del nodo *p apunte al nodo *s recién insertado ③ p->siguiente=s;
6. borrar
La operación de eliminación consiste en eliminar el i-ésimo nodo de la lista enlazada individualmente. Primero verifique la legalidad de la posición eliminada, luego busque el nodo i-1 en la tabla, que es el nodo predecesor del nodo eliminado, y luego elimínelo.
Idea de algoritmo: 1. Obtenga el puntero al nodo predecesor de la posición eliminada p=GetElem(L,i-1); 2. Lleve el puntero a la posición eliminada q=p->next; 3. El sucesor del nodo señalado por p apunta al sucesor del nodo eliminado p->next=q->next 4. Libere y elimine el nodo free(q);
lista doblemente enlazada
definición
1. Insertar: (el método no es único) ① s->siguiente=p->siguiente; ② p->siguiente->anterior=s; ③ s->antes=p; ④ p->siguiente=s;
2. Eliminar: ① p->siguiente=q->siguiente; ② q->siguiente->anterior=p; ③ gratis (q);
Lista enlazada circular y lista enlazada estática
Lista circular individualmente enlazada: la diferencia entre una lista circular individualmente enlazada y una lista individualmente enlazada es que el puntero del último nodo de la lista no es NULL, sino que apunta al nodo principal, de modo que toda la lista enlazada forma un anillo. .
Lista doblemente enlazada cíclica: Análoga a la lista enlazada individualmente cíclica, la lista doblemente enlazada cíclica se diferencia de la lista doblemente enlazada en que los nodos de cabeza y cola forman un anillo.
Cuando la lista circular doblemente enlazada es una lista vacía, el campo anterior y el siguiente campo de su nodo principal son ambos iguales a Head.
Lista vinculada estática: la lista vinculada estática es una estructura de almacenamiento vinculada que utiliza una matriz para describir una lista lineal.
El primer elemento de la matriz no almacena datos, su campo de puntero almacena el índice de la matriz donde se encuentra el primer elemento. El valor del campo de puntero del último elemento de la lista vinculada es -1.
ejemplo
Capítulo 3: Pilas y colas
pila
Pila: una lista lineal que solo permite operaciones de inserción o eliminación en un extremo.
Parte superior de la pila (Top): El final de la lista lineal que permite la inserción y eliminación.
Abajo: Fijo, el otro extremo que no permite inserción ni eliminación.
Características: 1. La pila es una lista lineal restringida, por lo que naturalmente tiene una relación lineal. Atar. 2. Los elementos de la pila que entran después deben salir primero, es decir, el último en entrar, el primero en salir. LIFO (Último en entrar, primero en salir)
Los elementos de la pila avanzan hacia atrás. Los que van deben irse primero. Ven, último en entrar, primero en entrar Fuera LIFO (Último en entrar) Primero en salir)
pila de secuencia
La pila es un caso especial de tablas lineales, y el almacenamiento secuencial de la pila también es una simplificación del almacenamiento secuencial de tablas lineales. La estructura de almacenamiento secuencial de la pila también se denomina pila secuencial.
Operaciones de pila secuenciales
1. Juicio breve:
2. Empuje hacia la pila:
3. Sal de la pila:
4. Lea el elemento superior de la pila:
pila compartida
El tamaño del espacio de almacenamiento de la pila secuencial debe asignarse con anticipación. En muchos casos, la tasa de utilización de abrir por separado el espacio de almacenamiento para cada pila no es tan buena como compartir el espacio de almacenamiento de cada pila.
Diagrama esquemático
Estructura de pila compartida
Operaciones de pila compartida: (empujar hacia la pila)
pila de cadena
La pila es un caso especial de lista lineal. La estructura de almacenamiento de una lista lineal también tiene una estructura de almacenamiento vinculada, por lo que la pila también se puede implementar en forma de lista vinculada. La estructura de almacenamiento en cadena de la pila también se denomina pila en cadena.
Características 1. La pila de cadenas generalmente no se llena. 2. La condición de juicio para una pila vacía generalmente se establece en top==NULL;
estructura
Operaciones de pila de cadena
1. Empuje hacia la pila
2. Sal de la pila
cola
Una cola es una lista lineal que solo permite inserciones en un extremo y eliminaciones en el otro.
Frente: El extremo que permite la eliminación, también conocido como frente.
Trasero: El extremo que permite la inserción.
El elemento que ingresa primero a la cola debe salir primero de la cola, es decir, primero en entrar, primero en salir (FIFO).
cola secuencial
Para implementar una cola usando una matriz, puede colocar el encabezado de la cola en el índice de la matriz 0.
cola circular
"Doble" la matriz para formar un anillo. Cuando el puntero trasero alcanza la posición del subíndice 4, puede continuar apuntando hacia la posición del subíndice 0. De esta manera, la cola almacenada en secuencia conectada de un extremo a otro se denomina cola circular.
En cola: trasero=(trasero 1)%MaxSize
Quitar de cola: frente=(frente 1)%MaxSize
Entonces, ¿cómo saber si la cola está vacía o llena?
Método 1: establezca la bandera. Cuando flag = 0 y rear es igual a front, la cola está vacía. Cuando flag = 1 y rear es igual a front, la cola está llena.
Método 2: Usamos front=rear solo como condición de juicio para que el equipo esté vacío. Cuando la cola está llena, todavía queda una unidad libre en la matriz. Creemos que esta situación es cuando la cola está llena.
Operaciones de cola circular
1. Únase al equipo:
2. Salir del equipo:
cola encadenada
La estructura de almacenamiento vinculado de la cola es en realidad una lista vinculada individualmente de una lista lineal, pero debe restringirse. Los elementos solo se pueden insertar al final de la tabla y eliminarse del encabezado.
Para facilitar la operación, configuramos el puntero principal del equipo y el puntero de cola del equipo respectivamente. El puntero principal del equipo apunta al nodo principal y el puntero de cola del equipo apunta al nodo final.
Operaciones de cola encadenadas
1. Ingresar a la cola: sabemos que la cola solo puede insertar elementos del final de la cola y eliminar elementos del encabezado de la cola. Entonces, unirse a la cola significa insertar el nodo en el puntero final de la cola. La operación de inserción de la cola en cadena es la misma que la operación de inserción de la lista enlazada individualmente.
2. Sacar de la cola: Sacar de la cola el nodo sucesor del nodo principal y luego cambiar el sucesor del nodo principal al nodo detrás de él.
deque
Una cola de dos extremos se refiere a una cola que permite que ambos extremos realicen operaciones de puesta y retirada de la cola.
aplicación de pila
1. Coincidencia de corchetes: supongamos que hay dos tipos de corchetes, uno redondo () y otro cuadrado [].
Idea de algoritmo: si es un corchete izquierdo, empújelo hacia la pila; si es un corchete derecho, saque un corchete izquierdo de la pila para determinar si coincide cuando se detecte el final de la cadena y verifique si la pila; esta vacio. Mientras la pila esté vacía, toda la cadena estará entre corchetes.
código
2. Evaluación de expresiones:
Reglas: escanea cada número y símbolo de la expresión de izquierda a derecha. Cuando se encuentra un número, se empuja a la pila. Cuando se encuentra un símbolo, los dos números en la parte superior de la pila se sacan de la pila. luego, la operación se realiza en el símbolo. Finalmente, el resultado de la operación se coloca en la pila, hasta que se obtiene el resultado final.
¿Cómo convertir una expresión infija en una expresión postfija?
1. Agregue corchetes a todos los operadores y sus operandos según la precedencia de los operadores. (No es necesario agregar soportes originales)
2. Mueva el operador después del paréntesis correspondiente.
3. Elimine los paréntesis.
ejemplo
3. Recursión:
Para comprender la recursividad, primero debe comprender la recursividad hasta que pueda comprender la recursividad. Si se utiliza en la definición de una función, procedimiento o estructura de datos, entonces se dice que la función, procedimiento o estructura de datos se define de forma recursiva o, para abreviar, recursivamente. Lo más importante de la recursividad es la fórmula de la recursividad y el límite de la recursividad.
1. factores
Complejidad del tiempo: O (NlogN)
2. Secuencia de Fibonacci
Complejidad del tiempo O (2 ^ n)
Capítulo 4: Árbol
Conceptos básicos de los árboles.
Un árbol es una estructura definida recursivamente.
Nodo
Nodo raíz: el árbol tiene un solo nodo raíz.
Grado de nodo: el número de subárboles que posee el nodo
El grado es 0: nodo hoja o nodo terminal
El grado no es 0: nodo de rama o nodo no terminal
Los nodos de rama también se denominan nodos internos, excepto el nodo raíz.
Grado del árbol: el grado máximo de todos los nodos del árbol.
Relación de nodo
nodo ancestro
Cualquier nodo con la ruta única desde el nodo raíz hasta este nodo
Nodo de descendientes
nodo padre
El nodo más cercano al nodo en la única ruta desde el nodo raíz al nodo
nodo hijo
nodo hermano
Nodos con el mismo nodo padre
Nivel, altura, profundidad, altura del árbol.
Nivel: La raíz es el primer nivel, sus hijos son el segundo nivel, y así sucesivamente.
Profundidad del nodo: comenzando desde el nodo raíz y acumulando de arriba a abajo
La altura del nodo: los nodos de las hojas comienzan a acumularse de abajo hacia arriba.
Altura del árbol (profundidad): el número máximo de niveles de nodos en el árbol
naturaleza del arbol
1. El número de nodos en el árbol es igual al grado de todos los nodos más 1.
Prueba: no es difícil imaginar que, a excepción del nodo raíz, cada nodo tiene y tiene solo un nodo predecesor que apunta a él. Es decir, cada nodo tiene una correspondencia uno a uno con la rama que le apunta. Supongamos que hay b ramas en el árbol, luego, además del nodo raíz, todo el árbol contiene b nodos, por lo que el número de nodos en todo el árbol son los b nodos más el nodo raíz, establecido en n, luego n = b 1. El número de rama b es también el grado de todos los nodos. La prueba está completa.
2. Hay como máximo m^(i−1) nodos en el i-ésimo nivel de un árbol con grado m (i≥1).
Prueba: (inducción matemática) Primero considere el caso de i=1: el primer nivel solo tiene el nodo raíz, es decir, un nodo, y se introduce i=1 en la ecuación para satisfacerlo. Suponiendo que la capa i-1 satisface esta propiedad, la capa i-1 tiene como máximo m i-2 nodos. …………………. i-1 capa ……… Y debido a que el grado del árbol es m, para cada nodo en el nivel i-1, como máximo Hay m nodos secundarios. Por lo tanto, el número de nodos en la capa i es como máximo m en la capa i-1. veces, por lo que hay como máximo m^(i-1) nodos en la i-ésima capa.
3. Un árbol m-ario con altura h tiene como máximo (m^h-1)/(m-1) nodos.
4. La altura mínima de un árbol m-ario con n nodos es logm(n(m-1) 1)
estructura de almacenamiento de árboles
estructura de almacenamiento secuencial
Representación principal: use un conjunto de espacios de almacenamiento continuo para almacenar los nodos del árbol y, al mismo tiempo, en cada nodo, use una variable para almacenar la posición del nodo principal del nodo en la matriz.
estructura de almacenamiento en cadena
Representación secundaria: organice los nodos secundarios de cada nodo y guárdelos en una lista enlazada individualmente. Entonces hay n listas enlazadas para n nodos; Si es un nodo hoja, entonces la lista enlazada individualmente de hijos de este nodo está vacía; Luego, los punteros principales de n listas enlazadas individualmente se almacenan en una tabla de secuencia (matriz).
Representación del hermano menor: como su nombre lo indica, es para almacenar al hijo y a los hermanos del nodo hijo. Específicamente, es para establecer dos punteros para que apunten al nodo respectivamente. El primer nodo hijo del punto y el nodo hermano derecho de este nodo hijo.
Árbol binario
definición
Un árbol binario es un conjunto finito de n (n≥0) nodos: ① O es un árbol binario vacío, es decir, n = 0. ② O consta de un nodo raíz y dos subárboles izquierdos separados llamados raíces. y el subárbol derecho. El subárbol izquierdo y el subárbol derecho son cada uno un árbol binario.
1. Cada nodo tiene como máximo dos subárboles.
2. Los subárboles izquierdo y derecho están en orden.
Cinco formas básicas de árboles binarios:
1. árbol vacío
2. Solo hay un nodo raíz
3. El nodo raíz solo tiene el subárbol izquierdo.
4. El nodo raíz solo tiene el subárbol derecho.
5. El nodo raíz tiene subárboles izquierdo y derecho.
árbol binario especial
1. árbol inclinado
2. Árbol binario completo:
3. Árbol binario completo
Propiedades de los árboles binarios
1. La cantidad de nodos hoja en un árbol binario no vacío es igual a la cantidad de nodos con grado 2 más 1.
2. Hay como máximo 2^k-1 nodos en el nivel K de un árbol binario no vacío (K≥1)
3. Un árbol binario con altura H tiene como máximo 2^H-1 nodos (H≥1)
4. La altura de un árbol binario completo con N (N>0) nodos es [log2(N 1)] o [log2N] 1.
Estructura de almacenamiento de árbol binario
almacenamiento secuencial
La estructura de almacenamiento secuencial de un árbol binario utiliza un conjunto de unidades de almacenamiento con direcciones consecutivas para almacenar los elementos de nodo de un árbol binario completo de arriba a abajo y de izquierda a derecha.
almacenamiento en cadena
Cada nodo de un árbol binario tiene como máximo dos hijos, por lo que al diseñar la estructura de nodos de un árbol binario, considere dos punteros que apunten a los dos hijos del nodo.
Recorrido de árbol binario
Recorrido de reserva: 1) Acceder al nodo raíz; 2) Recorra el subárbol izquierdo en orden; 3) Recorra el subárbol derecho en orden.
recursividad
no recursivo
Recorrido en orden: 1) Recorrido en orden del subárbol izquierdo; 2) Acceder al nodo raíz; 3) En orden, recorra el subárbol derecho.
recursividad
no recursivo
Recorrido posterior al pedido: 1) Recorrido posterior al orden del subárbol izquierdo; 2) Recorrido posterior al pedido del subárbol derecho; 3) Visite el nodo raíz.
recursividad
no recursivo
Recorrido de nivel: Si el árbol está vacío, no hagas nada y regresa directamente. De lo contrario, el acceso comienza desde el primer nivel del árbol y recorre nivel por nivel de arriba a abajo. En el mismo nivel, los nodos se visitan uno por uno en orden de izquierda a derecha.
árbol binario de pistas
Una lista binaria enlazada de N nodos. Cada nodo tiene enlaces que apuntan a sus hijos izquierdo y derecho. Punteros de nodo, por lo que hay 2N punteros en total y el binario de N nodos El árbol tiene un total de N-1 ramas, lo que significa que hay 2N-(N-1)=N 1 punteros nulos. Por ejemplo, si hay 6 nodos en el árbol binario de la izquierda, entonces hay 7 nodos vacíos. puntero.
¿Se puede utilizar una gran cantidad de punteros gratuitos?
Los punteros que apuntan al predecesor y al sucesor se denominan pistas. La lista binaria enlazada más pistas se denomina lista enlazada de pistas, y el árbol binario correspondiente se denomina árbol binario de pistas.
El proceso de atravesar un árbol binario en un orden determinado para convertirlo en un árbol binario enhebrado se llama enhebrado.
Árboles de Huffman y codificación de Huffman
El algoritmo se describe a continuación: 1) Trate estos N nodos como N árboles binarios que contienen solo un nodo para formar un bosque F. 2) Construya un nuevo nodo y seleccione los dos árboles con los pesos de nodo raíz más pequeños de F como los subárboles izquierdo y derecho del nuevo nodo, y cambie los pesos del nuevo nodo. Establecido como la suma de los pesos de los nodos raíz en los subárboles izquierdo y derecho. 3) Elimine los dos árboles recién seleccionados de F y agregue los árboles recién obtenidos a F. 4) Repita los pasos 2) y 3) hasta que solo quede un árbol en F.