Me encontré con el siguiente tipo de problema. Es necesario implementar un contenedor de almacenamiento de datos que proporcione la siguiente funcionalidad:
- insertar nuevo elemento
- eliminar elemento por número de serie
- obtener elemento por número ordinal
- los datos se almacenan en forma ordenada
Los datos se agregan y eliminan constantemente, la estructura debe garantizar una velocidad de operación rápida. Al principio intenté implementar algo así usando contenedores estándar de enfermedades de transmisión sexual. Este camino no estuvo coronado por el éxito y comprendí que necesitaba implementar algo yo mismo. Lo único que se me ocurrió fue utilizar un árbol de búsqueda binario. Porque cumple con el requisito de inserción, eliminación y almacenamiento rápidos de datos ordenados. Todo lo que queda es descubrir cómo indexar todos los elementos y recalcular los índices cuando cambia el árbol.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};El artículo contendrá más imágenes y teoría que código. El código se puede ver en el siguiente enlace.
peso
Para lograr esto, el árbol sufrió una ligera modificación, se agregó información adicional sobre peso nodo. El peso del nodo es número de descendientes de este nodo + 1 (peso de un solo elemento).
Función para obtener el peso del nodo:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}El peso de la hoja es correspondientemente igual a 0.
A continuación, pasemos a una representación visual de un ejemplo de dicho árbol. Negro la clave del nodo se mostrará en color (el valor no se mostrará, ya que esto no es necesario), rojo — peso del nudo, verde — índice de nodo.
Cuando nuestro árbol está vacío, su peso es 0. Agreguemos un elemento raíz:
El peso del árbol se convierte en 1, el peso del elemento raíz se convierte en 1. El peso del elemento raíz es el peso del árbol.
Agreguemos algunos elementos más:
Cada vez que se agrega un nuevo elemento, bajamos los nodos y aumentamos el contador de peso de cada nodo pasado. Cuando se crea un nuevo nodo, se le asigna un peso 1. Si ya existe un nodo con dicha clave, sobrescribiremos el valor y volveremos a la raíz, cancelando los cambios en los pesos de todos los nodos que hemos pasado.
Si se elimina un nodo, bajamos y disminuimos los pesos de los nodos pasados.
Índices
Ahora pasemos a cómo indexar nodos. Los nodos no almacenan explícitamente su índice, se calcula en función del peso de los nodos. Si almacenaran su índice, entonces sería necesario O (n) Es hora de actualizar los índices de todos los nodos después de cada cambio en el árbol.
Pasemos a una representación visual. Nuestro árbol está vacío, agreguemosle el primer nodo:
El primer nodo tiene un índice. 0, y ahora son posibles 2 casos. En el primero, el índice del elemento raíz cambiará, en el segundo no cambiará.
En la raíz, el subárbol izquierdo pesa 1.
Segundo caso:
El índice de la raíz no cambió porque el peso de su subárbol izquierdo permaneció en 0.
El índice de un nodo se calcula como el peso de su subárbol izquierdo + el número pasado del padre. ¿Cuál es este número?, este es el contador índice, inicialmente es igual a 0, porque la raíz no tiene padre. Entonces todo depende de dónde bajemos al niño de la izquierda o al de la derecha. Si está a la izquierda, no se agrega nada al contador. Si sumamos el índice del nodo actual al de la derecha.
Por ejemplo, cómo se calcula el índice de un elemento con la clave 8 (el hijo derecho de la raíz). Este es "Índice raíz" + "peso del subárbol izquierdo del nodo con clave 8" + "1" == 3 + 2 + 1 == 6
El índice del elemento con clave 6 será "Índice raíz" + 1 == 3 + 1 == 4
En consecuencia, lleva tiempo obtener y eliminar un elemento por índice. O (log n), porque para obtener el elemento deseado primero debemos encontrarlo (bajar desde la raíz hasta este elemento).
Profundidad
En función del peso, también puedes calcular la profundidad del árbol. Necesario para el equilibrio.
Para hacer esto, se debe redondear el peso del nodo actual al primer número elevado a 2 que sea mayor o igual al peso dado y tomarle el logaritmo binario. Esto nos dará la profundidad del árbol, suponiendo que esté equilibrado. El árbol se equilibra después de insertar un nuevo elemento. No daré una teoría sobre cómo equilibrar los árboles. Los códigos fuente proporcionan una función de equilibrio.
Código para convertir peso a profundidad.
/*
* Возвращает первое число в степени 2, которое больше или ровно x
*/
uint64_t bntree::cpl2(uint64_t x) {
x = x - 1;
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
x = x | (x >> 32);
return x + 1;
}
/*
* Двоичный логарифм от числа
*/
long bntree::ilog2(long d) {
int result;
std::frexp(d, &result);
return result - 1;
}
/*
* Вес к глубине
*/
uint64_t bntree::weight_to_depth(node_t *p) {
if (p == NULL) {
return 0;
}
if (p->weight == 1) {
return 1;
} else if (p->weight == 2) {
return 2;
}
return this->ilog2(this->cpl2(p->weight));
}resultados
- La inserción de un nuevo elemento ocurre en O (log n)
- la eliminación de un elemento por número de serie se produce en O (log n)
- la obtención de un elemento por número de serie se produce en O (log n)
velocidad O (log n) Pagamos por el hecho de que todos los datos se almacenan ordenados.
No sé dónde podría resultar útil una estructura así. Sólo un rompecabezas para comprender una vez más cómo funcionan los árboles. Gracias por su atención.
referencias
El proyecto contiene datos de prueba para comprobar la velocidad de funcionamiento. El árbol se está llenando. 1000000 elementos. Y hay una eliminación, inserción y recuperación secuencial de elementos. 1000000 una vez. Eso es 3000000 operaciones. El resultado resultó ser bastante bueno ~ 8 segundos.
Fuente: habr.com