Eu consegui uma tarefa do seguinte tipo. É necessário implementar um contêiner de armazenamento de dados que ofereça a seguinte funcionalidade:
- inserir um novo elemento
- remover um elemento pelo número da ordem
- obter um elemento pelo número da ordem
- os dados são armazenados de forma ordenada
Os dados são constantemente adicionados e removidos, a estrutura deve garantir alta velocidade de operação. Primeiro, tentei implementar algo assim usando os contêineres padrão de std. Esse caminho não teve sucesso, e veio a compreensão de que eu precisava implementar algo por conta própria. A única coisa que me veio à mente foi usar uma árvore binária de busca. Pois ela atende ao requisito de inserção rápida, remoção e armazenamento de dados de forma ordenada. Resta apenas descobrir como indexar todos os elementos e recalcular os índices quando a árvore mudar.
struct node_s {
data_t data;
uint64_t weight; // peso do nó
node_t *left;
node_t *right;
node_t *parent;
};O artigo terá mais imagens e teoria do que código. O código pode ser visto pelo link abaixo.
Peso
Para isso, a árvore passou por uma pequena modificação, foi adicionada uma informação adicional sobre o peso do nó. O peso do nó é o número de descendentes deste 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;
}O peso de uma folha, portanto, é 0.
Agora vamos passar para uma representação visual de um exemplo dessa árvore. Na cor preta será mostrado a chave do nó (o valor não será mostrado, pois não há necessidade disso), em vermelho — o peso do nó, em verde — o índice do nó.
Quando a árvore está vazia, seu peso é 0. Vamos adicionar o elemento raiz a ela:
O peso da árvore torna-se 1, o peso do elemento raiz 1. O peso do elemento raiz é o peso da árvore.
Vamos adicionar mais alguns elementos:
Cada vez que um novo elemento é adicionado, descemos pelos nós e aumentamos o contador de peso de cada nó percorrido. Ao criar um novo nó, define-se seu peso 1. Se um nó com essa chave já existir, então sobrescrevemos o valor e retornamos ao raiz, anulando as alterações nos pesos de todos os nós que passamos.
Se houver a remoção de um nó, descemos e decrementamos os pesos dos nós percorridos.
Índices
Agora vamos falar sobre como indexar os nós. Os nós não armazenam explicitamente seu índice; ele é calculado com base no peso dos nós. Se eles armazenassem seu índice, levaria O(n) mais tempo para atualizar os índices de todos os nós após cada alteração na árvore.
Vamos para uma representação visual. Nossa árvore está vazia; vamos adicionar o primeiro nó:
O primeiro nó tem um índice 0, e agora podem ocorrer dois casos. No primeiro, o índice do elemento raiz mudará; no segundo, não mudará.
Na raiz, a subárvore esquerda pesa 1.
Segundo caso:
O índice da raiz não mudou, pois o peso de sua subárvore esquerda permaneceu 0.
Como o índice do nó é calculado, é o peso de sua subárvore esquerda + o número passado pelo pai. Que número é esse? É o contador de índices, que inicialmente é 0, já que a raiz não tem pai. A partir daí, tudo depende de para onde descemos: para o filho esquerdo ou para o direito. Se for para o esquerdo, o contador não aumenta. Se for para o direito, adicionamos o índice do nó atual.
Por exemplo, como é calculado o índice do elemento com chave 8 (filho direito da raiz). Isso é "Índice da raiz" + "peso da subárvore esquerda do nó com chave 8" + "1" == 3 + 2 + 1 == 6
O índice do elemento com chave 6 será "Índice da raiz" + 1 == 3 + 1 == 4
Portanto, para obter ou remover um elemento pelo índice, leva O(log n), pois para obter o elemento desejado, primeiro precisamos encontrá-lo (descer da raiz até esse elemento).
Profundidade
Com base no peso, também é possível calcular a profundidade da árvore. Isso é necessário para o balanceamento.
Para isso, o peso do nó atual deve ser arredondado para o primeiro número em potência de 2 que é maior ou igual ao peso dado e tirar seu logaritmo binário. Assim, obteremos a profundidade da árvore, desde que ela esteja balanceada. A árvore é balanceada após a inserção de um novo elemento. Não vou discutir a teoria sobre como balancear árvores. A função de balanceamento está apresentada nos códigos-fonte.
Código para converter peso em profundidade.
/*
* Возвращает первое число в степени 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
- a inserção de um novo elemento ocorre em O(log n)
- a remoção de um elemento pelo número ordinal ocorre em O(log n)
- a obtenção de um elemento pelo número ordinal ocorre em O(log n)
A velocidade O(log n) pagamos pelo fato de que todos os dados são armazenados em ordem classificada.
Não sei onde essa estrutura pode ser útil. É apenas um exercício para entender melhor como funcionam as árvores. Obrigado pela atenção.
Links
O projeto contém dados de teste para verificar a velocidade de operação. A árvore é preenchida 1000000 de elementos. E ocorre a remoção, inserção e obtenção sequencial de elementos 1000000 vezes. Ou seja, 3000000 operações. O resultado foi bastante bom ~ 8 segundos.
Fonte: habr.com
