Árbore binaria indexada

Atopei o seguinte tipo de problema. É necesario implementar un contedor de almacenamento de datos que proporcione as seguintes funcionalidades:

• inserir un novo elemento
• eliminar elemento por número de serie
• obter elemento por número ordinal
• os datos almacénanse en forma ordenada

Os datos son engadidos e eliminados constantemente, a estrutura debe garantir unha velocidade de operación rápida. Ao principio tentei implementar tal cousa usando contedores estándar de STD. Este camiño non foi coroado polo éxito e chegou a entender que necesitaba implementar algo eu. O único que se me ocorreu foi usar unha árbore de busca binaria. Porque cumpre co requisito de rápida inserción, eliminación e almacenamento de datos en forma ordenada. Todo o que queda é descubrir como indexar todos os elementos e recalcular os índices cando a árbore cambia.

struct node_s {    
    data_t data;

    uint64_t weight; // вес узла

    node_t *left;
    node_t *right;

    node_t *parent;
};

O artigo conterá máis imaxes e teoría que código. O código pódese ver na seguinte ligazón.

Peso

Para conseguilo, a árbore sufriu unha lixeira modificación, engadiuse información adicional sobre peso nodo. O peso do nodo é número de descendentes deste nodo + 1 (peso dun só elemento).

Función para obter o peso do nodo:

uint64_t bntree::get_child_weight(node_t *node) {
    if (node) {
        return node->weight;
    }

    return 0;
}

O peso da folla é, en consecuencia, igual a 0.

A continuación, pasemos a unha representación visual dun exemplo de tal árbore. negro a clave do nodo mostrarase en cor (o valor non se mostrará, xa que non é necesario), vermello - peso do nó, verde - índice de nodos.

Cando a nosa árbore está baleira, o seu peso é 0. Engadímoslle un elemento raíz:

O peso da árbore pasa a ser 1, o peso do elemento raíz pasa a ser 1. O peso do elemento raíz é o peso da árbore.

Engadimos algúns elementos máis:

Cada vez que se engade un novo elemento, baixamos polos nodos e aumentamos o contador de peso de cada nodo pasado. Cando se crea un novo nodo, asígnaselle un peso 1. Se xa existe un nodo con tal chave, entón sobrescribiremos o valor e volveremos á raíz, cancelando os cambios nos pesos de todos os nodos que pasamos.
Se se está a eliminar un nodo, baixamos e decrementamos os pesos dos nodos pasados.

Índices

Agora imos pasar a como indexar os nós. Os nós non almacenan explícitamente o seu índice, calcúlase en función do peso dos nós. Se almacenasen o seu índice, sería necesario O (n) hora de actualizar os índices de todos os nós despois de cada cambio na árbore.
Pasemos a unha representación visual. A nosa árbore está baleira, engadímoslle o primeiro nodo:

O primeiro nodo ten un índice 0, e agora son posibles 2 casos. No primeiro, o índice do elemento raíz cambiará, no segundo non cambiará.

Na raíz, a subárbore esquerda pesa 1.

Segundo caso:

O índice da raíz non cambiou porque o peso da súa subárbore esquerda permaneceu 0.

O índice dun nodo calcúlase como o peso da súa subárbore esquerda + o número pasado do pai. Cal é este número?, Este é o contador do índice, inicialmente é igual a 0, porque a raíz non ten pai. Despois todo depende de onde baixemos ao neno esquerdo ou ao dereito. Se está á esquerda, non se engade nada ao contador. Se engadimos o índice do nodo actual ao dereito.

Por exemplo, como se calcula o índice dun elemento coa clave 8 (o fillo dereito da raíz). Este é "Índice raíz" + "peso da subárbore esquerda do nodo coa chave 8" + "1" == 3 + 2 + 1 == 6
O índice do elemento coa clave 6 será "Índice raíz" + 1 == 3 + 1 == 4

En consecuencia, leva tempo obter e eliminar un elemento por índice O (rexistro n), porque para conseguir o elemento desexado primeiro debemos atopalo (baixe desde a raíz ata este elemento).

Profundidade

En función do peso, tamén se pode calcular a profundidade da árbore. Necesario para o equilibrio.
Para iso, o peso do nodo actual debe ser redondeado ao primeiro número á potencia de 2 que é maior ou igual ao peso dado e tomar o logaritmo binario del. Isto daranos a profundidade da árbore, asumindo que estea equilibrada. A árbore está equilibrada despois de inserir un novo elemento. Non vou dar unha teoría sobre como equilibrar as árbores. Os códigos fonte proporcionan unha función de equilibrio.

Código para converter peso en 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 de

• prodúcese a inserción dun novo elemento O (rexistro n)
• a eliminación dun elemento por número de serie ocorre en O (rexistro n)
• a obtención dun elemento por número de serie ocorre en O (rexistro n)

Velocidade O (rexistro n) Pagamos polo feito de que todos os datos se almacenen en forma ordenada.

Non sei onde tal estrutura pode ser útil. Só un crebacabezas para comprender unha vez máis como funcionan as árbores. Grazas pola súa atención.

referencias

• Código fonte da árbore

O proxecto contén datos de proba para comprobar a velocidade de funcionamento. A árbore estase enchendo 1000000 elementos. E hai unha eliminación, inserción e recuperación secuenciais de elementos 1000000 unha vez. É dicir 3000000 operacións. O resultado resultou ser bastante bo ~ 8 segundos.

Fonte: www.habr.com