Wondershare EdrawMind
Galería de mapas mentales Estructura de datos Capítulo 7 Búsqueda
Estructura de datos Capítulo 7 Búsqueda
Capítulo 7 de "Estructura de datos": conocimientos de búsqueda, incluidos los conceptos básicos de búsqueda, búsqueda secuencial y búsqueda binaria, búsqueda de árbol, tabla hash, árbol B y árbol B, etc.
Editado a las 2022-11-23 16:07:51,
- 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 Capítulo 7 Búsqueda
- 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
Encontrar
Conceptos básicos de búsqueda.
1) encontrar
El proceso de encontrar elementos de datos que cumplan ciertas condiciones en una recopilación de datos.
2) Tabla de búsqueda (estructura de búsqueda)
Recopilación de datos utilizada para la búsqueda.
tabla de búsqueda estática
Sólo se utiliza para consultas.
tabla de búsqueda dinámica
Admite inserción y eliminación dinámicas
3) Palabras clave
El valor de un elemento de datos en un elemento de datos que identifica de forma única el elemento.
4) Longitud media de búsqueda
n: longitud de la tabla de búsqueda
Pi: La probabilidad de encontrar el i-ésimo elemento (normalmente 1/n)
Ci: el número de comparaciones necesarias para encontrar el i-ésimo elemento
Búsqueda secuencial y búsqueda binaria.
búsqueda secuencial
Búsqueda secuencial de tablas lineales generales.
Encuentre la duración promedio exitosa: (n 1)/2
Duración media de los fallos de búsqueda: n 1
Búsqueda secuencial en lista ordenada
Encuentre la duración promedio exitosa: (n 1)/2
Duración media de la búsqueda fallida: n/2 n/(n 1)
Buscar por la mitad (dos puntos)
Idea básica
Solo se aplica a listas de secuencia ordenada, compare la clave con el elemento de posición intermedia y luego compare recursivamente la primera o segunda mitad del elemento de posición intermedia según el tamaño hasta que la búsqueda tenga éxito o falle.
implementar código
árbol de decisión
Se utiliza para describir el proceso de media búsqueda.
Altura máxima de la rama
Dado que el árbol de decisión es un árbol binario equilibrado, la diferencia de altura máxima entre las ramas de los árboles es 1, es decir, el número máximo de comparaciones - el número mínimo de comparaciones = 1
El árbol de decisión también es un árbol de clasificación binario (es decir, palabras clave del subárbol izquierdo <nodo raíz <subárbol derecho, o viceversa)
complejidad del tiempo:
Buscar en trozos
Idea básica
También conocido como búsqueda de secuencia de índice. Divida la tabla de búsqueda en varios bloques. Las palabras clave del bloque anterior son más pequeñas que las del siguiente bloque, pero los elementos del bloque pueden estar desordenados. Cada elemento indica la palabra clave máxima de cada bloque y la dirección. del primer elemento. La tabla de índice está organizada por palabras clave en orden.
Al buscar, primero determine el bloque donde se encuentra el registro a buscar en la tabla de índice (use una tabla de índice de búsqueda secuencial o media y luego busque secuencialmente dentro del bloque);
Longitud promedio de búsqueda = búsqueda de índice dentro de la búsqueda de bloque
Toda la búsqueda en orden
Divida la tabla de búsqueda de longitud n en b bloques, cada bloque tiene s registros.
La tabla de índice utiliza búsqueda media y búsqueda secuencial dentro del bloque.
búsqueda de árboles
Árbol de clasificación binaria (BST)
definición
Un árbol de clasificación binario (también llamado árbol de búsqueda binaria) es un árbol vacío o un árbol binario con las siguientes propiedades:
1) Si el subárbol izquierdo no está vacío, los valores de todos los nodos en el subárbol izquierdo son menores que el valor del nodo raíz.
2) 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 del nodo raíz.
3) Los subárboles izquierdo y derecho también son un árbol de clasificación binario respectivamente.
Realice un recorrido en orden en un árbol ordenado binario para obtener una secuencia ordenada creciente.
Encontrar
insertar
1) Si la palabra clave k es menor que el valor del nodo raíz, insértela en el subárbol izquierdo; de lo contrario, insértela en el subárbol derecho;
2) El nodo insertado debe ser un nodo hoja recién agregado y el hijo izquierdo o derecho del último nodo visitado en la ruta de búsqueda cuando la búsqueda falla.
3) Eliminar e insertar el mismo nodo en la clasificación binaria. Si el nodo es originalmente un nodo hoja, los árboles binarios anteriores y posteriores permanecerán sin cambios, y viceversa. Para un árbol binario equilibrado, no importa si el nodo original eliminado es un. nodo hoja o no, los nodos, AVL antes y después pueden cambiar (o no)
estructura
proceso de construcción
algoritmo
borrar
①Si el nodo eliminado es un nodo hoja, simplemente elimínelo directamente
②Si el nodo eliminado z tiene solo un subárbol izquierdo o un subárbol derecho, haga que su subárbol se convierta en el subárbol del nodo padre de z.
③Si z tiene dos subárboles, izquierdo y derecho, deje que su sucesor directo (calculado según la secuencia en orden) o su predecesor directo reemplace z, y luego elimine el nodo sucesor para convertir a la situación anterior
análisis de eficiencia
1) La diferencia de altura entre los subárboles izquierdo y derecho no excede 1, es decir, un árbol binario equilibrado
Longitud media de búsqueda:
2) Un solo árbol con un solo hijo derecho (izquierdo)
Longitud media de búsqueda:
Comparación con la búsqueda binaria
1) El rendimiento de la búsqueda de un árbol de clasificación binaria está relacionado con el orden de entrada de los datos. Solo en el mejor de los casos, el rendimiento de la búsqueda es el mismo que el de la búsqueda binaria.
2) En términos de mantener el orden de la tabla, un árbol binario no necesita mover nodos. Solo necesita modificar el puntero para completar las operaciones de inserción y eliminación. La complejidad del tiempo es O (log2n), mientras que la búsqueda binaria requiere. O (n); cuando hay Cuando la tabla de secuencia es una tabla de búsqueda estática, es apropiado usar la tabla de secuencia y la búsqueda binaria. Cuando es dinámica, es apropiado usar un árbol de clasificación binario como estructura lógica.
árbol binario equilibrado
definición
Defina la diferencia de altura entre los subárboles izquierdo y derecho de un nodo como el factor de equilibrio (alto izquierdo - alto derecho), entonces el factor de equilibrio de un nodo de árbol binario equilibrado solo puede ser 0, 1, -1, es decir, la altura diferencia entre los subárboles izquierdo y derecho de cualquier nodo no más de 1
insertar
1) Insertar nodos similares al árbol de clasificación binaria
2) Una vez que el nodo insertado destruye el equilibrio, busque el subárbol desequilibrado más pequeño y gírelo.
①Rotación equilibrada LL (rotación única derecha)
Inserte un nuevo nodo en el subárbol izquierdo del hijo izquierdo del nodo A; debe girarse hacia la derecha. Gire el hijo izquierdo B de A hacia arriba para convertirse en el nodo raíz del subárbol derecho de B. y el árbol hijo derecho original de B como el subárbol izquierdo de A
②Rotación equilibrada RR (rotación única izquierda)
Inserte un nuevo nodo en el subárbol derecho del hijo derecho del nodo A; debe girarse hacia la izquierda. Gire el hijo derecho B de A hacia arriba para convertirse en el nodo raíz del subárbol izquierdo de B. El subárbol izquierdo original de A sirve como subárbol derecho de A.
③Rotación equilibrada LR (doble rotación primero a la izquierda y luego a la derecha)
Para insertar un nuevo nodo en el subárbol derecho del hijo izquierdo de A, primero debe rotar el nodo raíz C del subárbol derecho del hijo izquierdo B de A hacia la izquierda y hacia arriba hasta la posición de B, y luego rotar C hacia la derecha. y hasta la posición de A.
④RL rotación equilibrada (doble rotación izquierda en sucesión)
borrar
1) Utilice el método del árbol de clasificación binaria para realizar la operación de eliminación en el nodo w.
2) Comenzando desde el nodo w, rastree hacia arriba para encontrar el primer nodo desequilibrado z (es decir, el subárbol desequilibrado más pequeño); y es el nodo hijo con la altura más alta del nodo z. x es la altura del nodo y El nodo hijo más alto;
3) Luego equilibre el subárbol con z como raíz, donde hay 4 posiciones posibles de x, y y z:
① y es el hijo izquierdo de z, x es el hijo izquierdo de y (LL, rotación única a la derecha);
②y es el hijo izquierdo de z, y x es el hijo derecho de y (LR, doble rotación primero hacia la izquierda y luego hacia la derecha);
③y es el hijo derecho de z, x es el hijo derecho de y (RR, rotación única izquierda);
④y es el hijo derecho de z, x es el hijo izquierdo de y (RL, doble rotación primero hacia la derecha y luego hacia la izquierda)
og
Encontrar
El proceso de búsqueda es el mismo que el de un árbol de clasificación binario y la longitud de búsqueda promedio es O (log2n)
Número de nodos
nh es el número mínimo de nodos de un árbol binario equilibrado con altura h
árbol negro rojo
definición
Un árbol rojo-negro es un árbol ordenado binario que satisface las siguientes propiedades rojo-negro:
①Cada nodo es rojo o negro.
②El nodo raíz es negro.
③Los nodos hoja (nodos externos ficticios, nodos NULL) son todos negros.
④ No hay dos nodos rojos adyacentes (es decir, el nodo padre y el nodo hijo del nodo rojo son ambos negros).
⑤ Para cada nodo, la ruta simple desde el nodo a cualquier nodo hoja contiene la misma cantidad de nodos negros.
El número total de nodos negros en cualquier ruta simple desde un nodo (excluyendo este nodo) hasta un nodo hoja se denomina altura negra del nodo (registrada como bh). La altura negra del nodo raíz es el árbol rojo-negro. la altura negra
naturaleza
1. La ruta más larga desde el nodo raíz hasta el nodo hoja no es más del doble de la ruta más corta.
2. Altura de un árbol rojo-negro con n nodos internos
insertar
Inserte utilizando el método de inserción del árbol de búsqueda binaria y coloree el nuevo nodo z en rojo
Si z es el nodo raíz, coloréelo de negro y finalice
Si z no es el nodo raíz
Si el nodo padre de z es negro, no se necesita ningún ajuste
Si el nodo padre de z es rojo
①El nodo tío y de z es negro y z es el hijo derecho
LR (si z.p es el hijo derecho, es RL), gira hacia la izquierda una vez y se convierte en ②
②El nodo tío y de z es negro y z es un hijo izquierdo
LL (o RR si z.p es el hijo correcto), gire hacia la derecha una vez e intercambie z.p y z.p.p y colores.
③Si el nodo tío y de x es rojo
Colorea z.p e y de negro, colorea z.p.p de rojo y luego usa z.p.p como el nuevo nodo z para repetir el ciclo hasta que ①, ② o z sea el nodo raíz.
borrar
1) El proceso de eliminación primero ejecuta el método de eliminación del árbol de búsqueda binario. Si el nodo que se va a eliminar tiene dos hijos, se intercambia con el nodo sucesor en el orden (es decir, el nodo más pequeño en el subárbol derecho). luego se convierte para eliminar este nodo sucesor; el nodo sucesor tiene como máximo un hijo, por lo que se convierte a la situación en la que el nodo que se va a eliminar no tiene hijos o solo tiene uno.
2) Si el nodo que se va a eliminar tiene solo un hijo derecho o un hijo izquierdo, se puede ver en sus propiedades que debe ser un nodo negro y su hijo debe ser un nodo rojo.
3) Si el nodo a eliminar no tiene hijos
①Si el nodo es rojo, elimínelo directamente
② Si el nodo que se va a eliminar no tiene hijos y es rojo, registre x como el nodo utilizado para reemplazar y (x es un nodo nulo negro para mantener la altura del negro sin cambios, x se coloca como un nodo negro doble). y es necesario volver al nodo normal.
1. El nodo hermano w de x es rojo
En este momento, w debe tener nodos secundarios izquierdo y derecho negros y nodos principales para intercambiar los colores de w y x.p, y luego rotar x.p hacia la izquierda, convirtiendo la situación 1 en 2, 3 y 4;
2. El nodo hermano w de x es negro, el hijo izquierdo de w es rojo y el hijo derecho es negro.
RL, es decir, el nodo rojo es el hijo izquierdo del hijo derecho de su nodo padre. Intercambie los colores de w y su hijo izquierdo, gire w hacia la derecha y convierta al caso 3
3. El nodo hermano w de x es negro y el hijo derecho de w es rojo.
RR. Intercambie los colores de w y x.p, coloree el hijo derecho de w de negro y gire x.p hacia la izquierda para cambiar x de nuevo a un solo negro y finalice.
4. El nodo hermano w de x es negro y los dos nodos secundarios de w son ambos negros.
Elimine una capa de negro tanto de x como de w (es decir, w se vuelve rojo). Como compensación, agregue una capa adicional de negro a x.p para mantener la altura del negro local.
Si x.p es originalmente rojo, cámbielo a negro y finalice
Si x.p es originalmente negro, úselo como un nuevo nodo x para ingresar al bucle
tabla de picadillo
concepto basico
Función hash: una función que asigna una palabra clave en una tabla de búsqueda a la dirección correspondiente a la palabra clave, registrada como Hash (clave) = Dirección (la dirección aquí puede ser un subíndice de matriz, un índice o una dirección de memoria, etc.).
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. Por un lado, una función hash bien diseñada debería minimizar tales conflictos; por otro lado, dado que dichos conflictos son siempre inevitables, se debe diseñar un método para manejarlos;
Tabla hash: una estructura de datos a la que se accede directamente en función de palabras clave. En otras palabras, la tabla hash establece una relación de mapeo directo entre palabras clave y direcciones de almacenamiento.
Cómo construir una función hash
Requerir
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.
Funciones hash de uso común
método de direccionamiento directo
Idea básica
Tome directamente el valor de una función lineal de la palabra clave como dirección hash
función hash
H(clave)=clave o H(clave)=a×clave b
Características
Es simple, no causa conflictos y es adecuado para la distribución continua de palabras clave; de lo contrario, desperdiciará espacio de almacenamiento.
método de división dejando resto
Idea básica
Sea m la longitud de la tabla hash, tome un número primo p que sea menor y más cercano o igual a m, y use la fórmula para convertir la palabra clave en una dirección hash
función hash
H(clave)=clave%p
Características
El método más común y sencillo.
analítica digital
Idea básica
Para r dígitos de un número de base r, seleccione una cantidad de bits con una distribución de dígitos relativamente uniforme como dirección hash.
Características
Adecuado para conjuntos de palabras clave conocidos. Si se cambian las palabras clave, es necesario reconstruir una nueva función hash.
Método cuadrado-medio
Idea básica
Tome los dígitos medios del valor al cuadrado de la palabra clave como dirección hash
Características
Los valores de cada bit utilizados solo para palabras clave no son lo suficientemente uniformes o son más pequeños que la cantidad de bits necesarios para la dirección hash.
Cómo manejar los conflictos
método de direccionamiento abierto
definición
La dirección libre donde se puede almacenar una nueva entrada está abierta tanto a sus entradas sinónimas como a sus entradas no sinónimas.
fórmula de recursividad
Hola representa la dirección hash obtenida por la i-ésima detección en el procesamiento de conflictos, m representa la longitud de la tabla hash y di es la secuencia de incremento.
secuencia incremental
Método de detección lineal
Idea básica
di=0, 1,...,m-1, es decir, cuando ocurre un conflicto, verifique la siguiente unidad en la tabla secuencialmente hasta encontrar una unidad libre o buscar en toda la tabla.
Características
Es fácil hacer que una gran cantidad de elementos se "agregen" en direcciones hash adyacentes, lo que reduce en gran medida la eficiencia de la búsqueda.
Con el sondeo lineal, pueden ocurrir conflictos incluso si no son sinónimos.
método de detección de cuadrados
Idea básica
di=0^2, 1^2, -1^2...,k^2,-k^2, donde k≤m/2, la longitud de la tabla hash m debe ser un número primo que pueda expresarse como 4K 3, también conocido como método de detección secundaria
Características
Evita problemas de "acumulación", pero no puede detectar todas las celdas en la tabla hash (pero puede detectar al menos la mitad de las celdas)
doble hash
Idea básica
di = Hash2 (clave), es decir, se utilizan dos funciones hash. Cuando la dirección obtenida por 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.
función hash
método de secuencia pseudoaleatoria
di = secuencia numérica pseudoaleatoria
Método de cremallera (encadenamiento)
Almacene todos los sinónimos en una lista enlazada lineal que se identifica de forma única por su dirección hash adecuada para situaciones donde las inserciones y eliminaciones son frecuentes;
Búsqueda de hash y análisis de rendimiento
Proceso de búsqueda
① Verifique si hay un registro en la dirección de Addr en la tabla de búsqueda. Si no hay ningún registro, devuelva el error de búsqueda; si hay un registro, compárelo con el valor de la clave. indicador de búsqueda exitosa; de lo contrario, continúe con el paso ②.
② Utilice el método de manejo de conflictos proporcionado para calcular la "siguiente dirección hash", establezca Addr en esta dirección y vaya al paso ①.
Longitud media de búsqueda ASL=2,5
Clasificación
Búsqueda exitosa
Encuentra la longitud de cada elemento conocido.
El número de comparaciones exitosas = el número de conflictos 1
La búsqueda falló
La longitud de búsqueda de cada posición de búsqueda determinada por la función hash.
Encuentre factores que afectan la eficiencia.
función hash
Cómo manejar los conflictos
Factor de llenado α = número de registros en la tabla n/longitud de la tabla hash m
Árbol B y árbol B
B-tree y sus operaciones básicas
definición
El árbol B, también conocido como árbol de búsqueda equilibrado de múltiples vías, el número máximo de hijos de todos sus nodos se denomina orden del árbol B, denotado como m. Un árbol B de orden m es un árbol vacío o. un árbol que satisface las siguientes propiedades árbol m-ario:
1) Cada nodo del árbol tiene como máximo m subárboles, es decir, contiene como máximo m- 1 palabras clave
2) Si el nodo raíz no es un nodo terminal, hay al menos dos subárboles
3) Todos los nodos que no son hoja, excepto el nodo raíz, tienen al menos "m/2] subárboles, es decir, contienen al menos "m/2]-1 palabras clave.
4) La estructura de todos los nodos no hoja es la siguiente:
Ki es la palabra clave del nodo, ordenada en orden ascendente
Pi es un puntero al nodo raíz del subárbol. Las claves de todos los nodos en el subárbol al que apunta Pi-1 son menores que Ki.
n es el número de palabras clave
5) Todos los nodos hoja aparecen en el mismo nivel y no contienen información (es decir, nodos externos, los punteros a estos nodos están vacíos)
Propiedades (asumiendo m=5)
1) La cantidad de hijos de un nodo es igual a la cantidad de palabras clave en el nodo más 1.
2) Si el nodo raíz no tiene palabras clave, no habrá subárboles y el árbol B está vacío en este momento. Si el nodo raíz tiene palabras clave, sus subárboles deben ser mayores o iguales a dos, porque el número de subárboles; es igual al número de palabras clave más 1.
3) Todos los nodos no terminales, excepto el nodo raíz, tienen al menos "m/2]-1=3 subárboles y como máximo 5 subárboles (es decir, como máximo 4 palabras clave).
4) Las palabras clave en el nodo están en orden creciente de izquierda a derecha. Hay punteros al subárbol a ambos lados de la palabra clave. Todas las palabras clave del subárbol señalado por el puntero izquierdo son más pequeñas que la palabra clave apuntada. por el puntero derecho es menor que la palabra clave. Todas las palabras clave son mayores que esta palabra clave.
5) Todos los nodos hoja están en el cuarto nivel, lo que representa la ubicación donde falló la búsqueda.
La altura del árbol B (número de accesos al disco)
1) Cada nodo del árbol B tiene como máximo m subárboles y m-1 palabras clave. Por lo tanto, el número de palabras clave en un árbol B de orden m con una altura de h debe satisfacer n≤(m-1)(1). m m^2 …… m^(h-1))=m^h-1
2) El nodo raíz tiene al menos 2 subárboles, el nodo no raíz tiene al menos "m/2]-1 palabras clave y el primer nivel h tiene al menos 2("m/2])^(h-1) puntos de nodos, y el número de nodos de hoja es n 1
Búsqueda de árbol B
①Buscar nodos en el árbol B
Realizado en el disco, busque el nodo correspondiente según la comparación de palabras clave
Si se encuentra un nodo hoja (el puntero correspondiente es un puntero nulo), significa que no hay ninguna palabra clave correspondiente en el árbol y la búsqueda falla.
②Buscar palabras clave en nodos
Realizado en memoria, utilizando métodos de búsqueda secuenciales o binarios dentro del nodo.
Inserción en el árbol B
1) Si la cantidad de palabras clave de nodo después de la inserción es menor que m, puede insertarlas directamente
2) De lo contrario, tome el nodo en la posición media ("m/2]) e insértelo en el nodo padre del nodo original, y el nodo original se dividirá en dos partes; si esto causa que el número de palabras clave del el nodo principal se desborda, continúe con la división hasta llegar al nodo raíz, lo que a su vez hace que la altura del árbol B aumente en 1
Eliminación del árbol B
1) Si la palabra clave eliminada k no está en el nodo terminal (el nodo no hoja de nivel más bajo), reemplace k con el predecesor (o sucesor) de k k', y luego elimine k' en el nodo correspondiente (k' debe caer en un nodo terminal)
2) Si la palabra clave eliminada k está en el nodo terminal
①Eliminar palabras clave directamente. La condición es que el número de palabras clave en el nodo sea ≥ "m/2]. Después de eliminar la palabra clave, aún cumple con la definición de árbol B.
②Los hermanos pueden pedir prestado lo suficiente. Si el número de palabras clave del nodo = "m/2] -1 y el número de palabras clave del nodo hermano ≥ "m/2], ajuste el nodo, el nodo hermano derecho (izquierdo) y su nodo padre (padre). -método de transposición son) para lograr un nuevo equilibrio
③No hay suficientes hermanos para pedir prestado. Si el número de palabras clave del nodo y sus nodos hermanos izquierdo y derecho son "m/2]-1, elimine las palabras clave y combínelas con las palabras clave del nodo hermano izquierdo (derecho) y el nodo padre.
Conceptos básicos de árboles B
B-tree es un árbol deformado de B-tree que cumple las siguientes condiciones:
1) Cada nodo de rama tiene como máximo m subárboles (nodos secundarios).
2) El nodo raíz no hoja tiene al menos dos subárboles, y cada otro nodo de rama tiene al menos "m/2] subárboles.
3) El número de subárboles de un nodo es igual al número de palabras clave.
4) Todos los nodos hoja contienen todas las palabras clave y punteros a los registros correspondientes. Las palabras clave están ordenadas por tamaño en los nodos hoja, y los nodos hoja adyacentes están vinculados entre sí por orden de tamaño.
5) Todos los nodos de rama (índices que pueden considerarse índices) solo contienen el valor máximo de la palabra clave en cada uno de sus nodos secundarios (es decir, el bloque de índice del siguiente nivel) y los punteros a sus nodos secundarios.
La diferencia entre árbol B y árbol B:
1) En el árbol B, un nodo con n palabras clave contiene solo 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 subárboles.
2) En el árbol B, el rango del número n de palabras clave para cada nodo (nodo interno no raíz) es "m/2]<n<m (nodo raíz: 2<n<m); en B En el á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. La dirección de almacenamiento del registro correspondiente a esta palabra clave no está incluida.
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 del árbol B, los nodos hoja (el nodo interno más externo) y las palabras clave contenidas en; otros nodos no se repiten.
Encontrar
① Hay dos punteros principales en el árbol B: uno apunta al nodo raíz y el otro apunta al nodo hoja con la palabra clave más pequeña, por lo tanto, se pueden realizar dos operaciones de búsqueda en el árbol B: una es una búsqueda secuencial; desde la palabra clave más pequeña, y la otra es La primera es una búsqueda multidireccional que comienza desde el nodo raíz
②Al buscar en el árbol B, no importa si tiene éxito o no, cada búsqueda es una ruta desde el nodo raíz hasta el nodo hoja.