Eu tenho o seguinte problema. É necessário implementar um contêiner de armazenamento de dados que forneça a seguinte funcionalidade:
- inserir novo item
- excluir item pelo número de série
- obtenha o item pelo número de série
- os dados são armazenados em forma classificada
Os dados são constantemente adicionados e excluídos, a estrutura deve fornecer velocidade rápida. No começo, tentei implementar uma coisa dessas usando contêineres padrão do std . Esse caminho não teve êxito e surgiu o entendimento de que você mesmo precisa implementar algo. A única coisa que veio à mente foi usar uma árvore de pesquisa binária. Uma vez que atende aos requisitos de inserção rápida, exclusão e armazenamento de dados em forma classificada. Resta apenas descobrir como indexar todos os elementos e recalcular os índices quando a árvore for alterada.
struct node_s { data_t data; uint64_t weight;
O artigo terá mais figuras e teoria do que código. O código pode ser visto no link abaixo.
Peso
Para isso, a árvore passou por uma leve modificação, informações adicionais sobre o peso do nó foram adicionadas. O peso de um nó é o número de descendentes desse nó + 1 (peso de um único elemento).
Função para obter o peso do nó:
uint64_t bntree::get_child_weight(node_t *node) { if (node) { return node->weight; } return 0; }
A folha, portanto, tem um peso de 0 .
Em seguida, passamos a uma representação visual de um exemplo dessa árvore. A chave do nó será mostrada em preto nela (o valor não será mostrado, porque isso não é necessário), em vermelho - o peso do nó, em verde - o índice do nó.
Quando a árvore está vazia, seu peso é 0. Adicione o elemento raiz a ela:
O peso da árvore se torna 1, o peso do elemento raiz 1. O peso do elemento raiz é o peso da árvore.
Adicione mais alguns elementos:
Cada vez que um novo item é adicionado, descemos os nós até o final e aumentamos o contador de pesos de cada nó passado. Ao criar um novo nó, ele é definido como peso 1 . Se um nó com essa chave já existir, reescreva o valor e volte para a raiz, cancelando as alterações nos pesos de todos os nós que passamos.
Se o nó estiver sendo removido, diminuiremos e diminuiremos os pesos dos nós passados.
Índices
Agora vamos seguir como indexar os nós. Os nós não armazenam explicitamente seu índice; é calculado com base no peso dos nós. Se eles armazenassem seu índice, seria necessário tempo O (n) para atualizar os índices de todos os nós após cada alteração na árvore.
Vamos passar para uma representação visual. Nossa árvore está vazia, adicione o 1º nó a ela:
O primeiro nó tem o índice 0 e agora são possíveis 2 casos. No primeiro, o índice do elemento raiz será alterado; no segundo, não será alterado.
Na raiz, a subárvore esquerda pesa 1.
Segundo caso:
O índice raiz não foi alterado, pois o peso de sua subárvore esquerda permanece 0.
Como o índice do nó é considerado, esse é o peso de sua subárvore esquerda + o número passado do pai. O que é esse número ?, Este é um contador de índice, inicialmente é 0 , porque a raiz não tem pai. Então tudo depende de onde descemos para a criança esquerda ou direita. Se for para a esquerda, nada será adicionado ao contador. Se à direita, adicione o índice do nó atual.
Por exemplo, como calcular o índice de um elemento com a chave 8 (o filho certo da raiz). Este é o peso "Índice Raiz" + "da subárvore esquerda do nó com a tecla 8" + "1" == 3 + 2 + 1 == 6
O índice do item com a chave 6 é "Índice Raiz" + 1 == 3 + 1 == 4
Assim, levaria tempo O (log n) para obter e remover um elemento pelo índice, porque, para obter o elemento, precisamos primeiro encontrá-lo (desça da raiz para esse elemento).
Profundidade
Com base no peso, você também pode calcular a profundidade da árvore. Necessário para equilibrar.
Para fazer isso, o peso do nó atual deve ser arredondado para o primeiro número no grau 2, que é maior ou igual ao peso especificado e retira o logaritmo binário dele. Assim, obtemos a profundidade da árvore, desde que ela seja equilibrada. A árvore é equilibrada após a inserção de um novo elemento. A teoria sobre como equilibrar as árvores não levará. O código fonte fornece uma função de balanceamento.
Código para aumentar o peso.
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)); }
Sumário
- a inserção de um novo elemento ocorre em O (log n)
- a exclusão do elemento pelo número de sequência ocorre em O (log n)
- obter um elemento por seu número de série ocorre em O (log n)
Com a velocidade de O (log n), pagamos pelo fato de que todos os dados são armazenados na forma classificada.
Onde essa estrutura pode ser útil, eu não sei. Apenas uma tarefa para entender mais uma vez como as árvores funcionam. Obrigado pela atenção.
Referências
O projeto contém dados de teste para verificar a velocidade do trabalho. A árvore é preenchida com 1.000.000 de elementos. E há uma exclusão seqüencial, inserção e recebimento de elementos 1.000.000 de vezes. São 3.000.000 de operações. O resultado foi muito bom ~ 8 segundos.