Indeksowane drzewo binarne

Natknąłem się na następujący typ problemu. Konieczne jest wdrożenie kontenera do przechowywania danych, który zapewnia następującą funkcjonalność:

• wstaw nowy element
• usuń element według numeru seryjnego
• pobierz element według liczby porządkowej
• dane są przechowywane w formie posortowanej

Dane są stale dodawane i usuwane, struktura musi zapewniać dużą szybkość działania. Na początku próbowałem zaimplementować coś takiego przy użyciu standardowych kontenerów z std. Droga ta nie została uwieńczona sukcesem i przyszło zrozumienie, że muszę coś wdrożyć samodzielnie. Jedyne co przyszło mi do głowy to użycie drzewa wyszukiwania binarnego. Ponieważ spełnia wymóg szybkiego wstawiania, usuwania i przechowywania danych w formie posortowanej. Pozostaje tylko wymyślić, jak zindeksować wszystkie elementy i przeliczyć indeksy, gdy drzewo się zmieni.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Artykuł będzie zawierał więcej zdjęć i teorii niż kodu. Kod można obejrzeć pod linkiem poniżej.

Waga

Aby to osiągnąć drzewo przeszło niewielką modyfikację, dodano dodatkowe informacje nt waga węzeł. Waga węzła wynosi liczba potomków tego węzła + 1 (waga pojedynczego elementu).

Funkcja uzyskiwania wagi węzła:

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

    return 0;
}

Waga arkusza jest odpowiednio równa 0.

Następnie przejdźmy do wizualnej reprezentacji przykładu takiego drzewa. Czarny klucz węzła zostanie wyświetlony w kolorze (wartość nie zostanie pokazana, ponieważ nie jest to konieczne), czerwonym. — waga węzła, zielony — indeks węzła.

Kiedy nasze drzewo jest puste, jego waga wynosi 0. Dodajmy do niego element główny:

Ciężar drzewa wynosi 1, ciężar elementu korzenia wynosi 1. Ciężar elementu korzenia jest ciężarem drzewa.

Dodajmy jeszcze kilka elementów:

Za każdym razem, gdy dodawany jest nowy element, schodzimy w dół węzłów i zwiększamy licznik wagi każdego mijanego węzła. Kiedy tworzony jest nowy węzeł, zostaje mu przypisana waga 1. Jeśli węzeł z takim kluczem już istnieje, to nadpiszemy wartość i wrócimy do korzenia, anulując zmiany wag wszystkich mijanych węzłów.
Jeśli węzeł jest usuwany, schodzimy w dół i zmniejszamy wagi przekazanych węzłów.

wskaźniki

Przejdźmy teraz do sposobu indeksowania węzłów. Węzły nie przechowują jawnie swojego indeksu, jest on obliczany na podstawie wagi węzłów. Gdyby przechowywali swój indeks, byłby on wymagany Na) czas na aktualizację indeksów wszystkich węzłów po każdej zmianie w drzewie.
Przejdźmy do reprezentacji wizualnej. Nasze drzewo jest puste, dodajmy do niego pierwszy węzeł:

Pierwszy węzeł ma indeks 0, i teraz możliwe są 2 przypadki. W pierwszym zmieni się indeks elementu głównego, w drugim nie ulegnie zmianie.

U korzenia lewe poddrzewo waży 1.

Drugi przypadek:

Indeks korzenia nie uległ zmianie, ponieważ waga jego lewego poddrzewa pozostała równa 0.

Indeks węzła oblicza się jako wagę jego lewego poddrzewa + liczbę przekazaną od rodzica. Co to za liczba?, To jest licznik indeksu, początkowo jest równy 0, ponieważ korzeń nie ma rodzica. Wtedy wszystko zależy od tego, gdzie zejdziemy, do lewego dziecka, czy do prawego. Jeśli po lewej stronie, nic nie jest dodawane do licznika. Jeśli dodamy indeks bieżącego węzła do prawego.

Na przykład, jak obliczany jest indeks elementu z kluczem 8 (prawym dzieckiem pierwiastka). To jest „Indeks pierwiastka” + „waga lewego poddrzewa węzła z kluczem 8” + „1” == 3 + 2 + 1 == 6
Indeks elementu z kluczem 6 będzie wynosić „Indeks pierwiastkowy” + 1 == 3 + 1 == 4

W związku z tym pobranie i usunięcie elementu według indeksu zajmuje trochę czasu O (log n), ponieważ aby otrzymać pożądany element musimy go najpierw znaleźć (przejść od korzenia do tego elementu).

Głębokość

Na podstawie masy można również obliczyć głębokość drzewa. Niezbędne do zrównoważenia.
Aby to zrobić, wagę bieżącego węzła należy zaokrąglić do pierwszej liczby do potęgi 2, która jest większa lub równa podanej wadze i pobrać z niej logarytm binarny. To da nam głębokość drzewa, zakładając, że jest zrównoważone. Drzewo zostaje zbilansowane po wstawieniu nowego elementu. Nie będę podawać teorii na temat równoważenia drzew. Kody źródłowe zapewniają funkcję równoważącą.

Kod do przeliczania ciężaru na głębokość.

/*
 * Возвращает первое число в степени 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));
}

Wyniki

• wstawienie nowego elementu następuje w O (log n)
• usunięcie elementu według numeru seryjnego następuje w O (log n)
• uzyskanie elementu według numeru seryjnego następuje w O (log n)

prędkość O (log n) Płacimy za to, że wszystkie dane są przechowywane w formie posortowanej.

Nie wiem gdzie taka konstrukcja może się przydać. To tylko łamigłówka, która pomoże ci jeszcze raz zrozumieć, jak działają drzewa. Dziękuję za uwagę.

referencje

• Kod źródłowy drzewa

Projekt zawiera dane testowe umożliwiające sprawdzenie szybkości działania. Drzewo się zapełnia 1000000 elementy. Następuje sekwencyjne usuwanie, wstawianie i pobieranie elementów 1000000 raz. To jest 3000000 operacje. Wynik okazał się całkiem dobry ~8 sekund.

Źródło: www.habr.com