árbol de clasificación binaria

árbol binario equilibrado

Árbol B (árbol B)

árbol B

Propiedad básica: calcula la dirección de la palabra clave en la tabla según la palabra clave proporcionada

Método de construcción

Métodos de manejo de conflictos

Clasificación de burbujas: ① Compara elementos adyacentes. Si el primero es más grande que el segundo, cámbielos a ambos ② Haga lo mismo para cada par de elementos adyacentes, comenzando con el primer par y terminando con el último par. En este punto, el último elemento debe ser el número más grande. ③ Repita los pasos anteriores para todos los elementos excepto el último. ④ Continúe repitiendo los pasos anteriores para cada vez menos elementos hasta que no haya pares de números para comparar.

Ordenación por selección simple: suponga que el número de registros en la secuencia ordenada es n. Tomo 1, 2,..., n-1, busco el registro con el código de clasificación más pequeño de todos los registros n-i 1 (Ri, Ri 1,..., Rn) y lo intercambio con el i-ésimo registro. Después de ejecutar n-1 veces, se completa la clasificación de la secuencia de registros.

Clasificación por inserción directa: primero, los primeros datos se clasifican primero y luego, en cada pasada, se inserta un dato a ordenar en la posición apropiada de un grupo de registros que se ha ordenado según el tamaño de su clave. Se insertan todos los datos a ordenar.

Clasificación Hill: primero tome un número entero d1 menor que n como primer incremento y agrupe todos los registros del archivo. Todos los registros cuya distancia sea múltiplo de d1 se colocan en el mismo grupo. Primero realice la clasificación por inserción directa dentro de cada grupo; luego, tome el segundo incremento d2<d1 y repita la agrupación y clasificación anterior hasta el incremento dt=1 (dt<...<d2<d1)

Clasificación del montón: construya la secuencia que se ordenará en un árbol binario y luego realice ajustes de transposición para garantizar que todos los nodos secundarios sean más pequeños que sus nodos principales. En este momento, el valor del nodo raíz debe ser el valor máximo. Y construya un árbol binario nuevamente, repita las operaciones anteriores.

Clasificación por combinación bidireccional: ① Forme varios grupos binarios y ajústelos al orden dentro del grupo ② Combine los grupos binarios ordenados en un grupo y ajústelos al orden dentro del grupo ③ Combine todos los datos en un grupo para completar la clasificación

Clasificación por base: configure diez espacios, denominados espacio 0, espacio 1,..., espacio 9. Primero, corresponda los registros en la secuencia a cada espacio principal uno por uno de acuerdo con el valor de un solo dígito y colóquelos en cada espacio. Complete la clasificación en cada espacio, luego saque cada registro del espacio 0 para formar una nueva secuencia y luego repita el trabajo en bits más altos hasta que se complete la clasificación de bits más altos.

Combinar clasificación: divida la secuencia inicial en m segmentos de registros más pequeños, clasifique estos segmentos de registros y compare continuamente los valores mínimos desde los extremos más pequeños de cada segmento de registros hasta que se complete la clasificación.

Árbol perdedor: cuando la clasificación por fusión detecta el valor mínimo, si no usa el árbol perdedor, debe comparar los valores k leídos k-1 veces. Después de usarlo, solo necesita realizar log2k veces. de seleccionar el mejor valor es O(log2k), la complejidad del tiempo de construcción del árbol es O(klog2k) y la altura del árbol perdedor es [log2k] 1

Clasificación por selección de reemplazo: según el tamaño del búfer, se lee un registro de la memoria externa. Cuando el registro llena el búfer, se selecciona el más pequeño y se vuelve a escribir en la memoria externa. Su posición vacante se reemplaza por la siguiente. lee el registro y el registro de salida se convierte en el registro inicial actual. Parte del segmento fusionado. Si el nuevo registro ingresado es más pequeño que el registro extraído en el segmento de combinación, se generará como alternativa a otros segmentos de combinación iniciales. Repita las operaciones anteriores.

Árbol de fusión óptimo: los segmentos de fusión de diferentes longitudes se obtienen mediante clasificación por selección de reemplazo. Cada segmento se coloca en un árbol de Huffman de acuerdo con su longitud (consulte el capítulo sobre árboles para conocer el método. Comenzando desde el nodo raíz, se alcanza cada segmento). El doble de la suma del número de aristas pasadas por el nodo es el número de E/S correspondientes al árbol de fusión óptimo (número mínimo de E/S).