Znalazłem zadanie następującego typu. Należy zaimplementować kontener do przechowywania danych, który zapewnia następującą funkcjonalność:
- dodać nowy element
- usunąć element według numeru porządkowego
- uzyskać element według numeru porządkowego
- dane są przechowywane w posortowanej formie
Dane są stale dodawane i usuwane, struktura musi zapewniać wysoką szybkość działania. Na początku próbowałem zrealizować to korzystając z standardowych kontenerów z std. Ta droga nie przyniosła sukcesu, więc zrozumiałem, że muszę coś zaimplementować samodzielnie. Jedyną myślą, która mi pojawiła, było użycie drzewa binarnego wyszukiwania, ponieważ spełnia ono wymagania szybkiego dodawania, usuwania i przechowywania danych w posortowanej formie. Pozostało tylko wymyślić, jak zaindeksować wszystkie elementy i przeliczać indeksy, gdy drzewo się zmienia.
struct node_s {
data_t data;
uint64_t weight; // waga węzła
node_t *left;
node_t *right;
node_t *parent;
};W artykule będzie więcej obrazków i teorii niż kodu. Kod będzie można zobaczyć pod linkiem na dole.
Waga
W tym celu drzewo przeszło niewielką modyfikację, dodano dodatkowe informacje o wadze węzła. Waga węzła to liczba potomków danego 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;
}Dla liścia waga wynosi odpowiednio 0.
Przejdźmy teraz do graficznej reprezentacji przykładu takiego drzewa. Czarnym kolorem w nim będzie pokazany klucz węzła (wartość nie będzie pokazywana, ponieważ nie ma takiej potrzeby), czerwonym — waga węzła, zielonym — indeks węzła.
Kiedy drzewo jest puste, jego waga wynosi 0. Dodajmy do niego element główny:
Waga drzewa staje się 1, waga elementu głównego wynosi 1. Waga elementu głównego jest wagą drzewa.
Dodajmy jeszcze kilka elementów:
Za każdym razem, gdy dodawany jest nowy element, schodzimy w dół przez węzły i zwiększamy licznik wagi każdego przechodzonego węzła. Przy tworzeniu nowego węzła nadaje mu się wagę 1. Jeśli węzeł z takim kluczem już istnieje, to nadpiszemy wartość i wrócimy w górę do korzenia, cofając zmiany wag u wszystkich węzłów, które przechodziliśmy.
Jeśli dochodzi do usunięcia węzła, schodzimy w dół i dekrementujemy wagi przechodzonych węzłów.
Indeksy
Teraz przejdźmy do tego, jak zindeksować węzły. Węzły nie przechowują jawnie swojego indeksu, jest on obliczany na podstawie wagi węzłów. Gdyby przechowywały swój indeks, potrzebny byłby O(n) czas, aby zaktualizować indeksy wszystkich węzłów po każdej zmianie w drzewie.
Przejdźmy do wizualnej reprezentacji. Nasze drzewo jest puste, dodajmy do niego pierwszy węzeł:
Pierwszy węzeł ma indeks 0, a teraz mogą wystąpić 2 przypadki. W pierwszym przypadku indeks elementu głównego się zmieni, w drugim nie zmieni.
Lewe poddrzewo korzenia waży 1.
Drugi przypadek:
Indeks korzenia nie zmienił się, ponieważ waga jego lewego poddrzewa pozostała 0.
Indeks węzła oblicza się jako waga jego lewego poddrzewa + liczba przekazana przez rodzica. Co to za liczba? To licznik indeksów, początkowo równy 0, ponieważ korzeń nie ma rodzica. Potem wszystko zależy od tego, czy schodzimy do lewego dziecka, czy do prawego. Jeśli do lewego, to licznik się nie zwiększa. Jeśli do prawego, to dodajemy indeks bieżącego węzła.
Na przykład, jak oblicza się indeks elementu z kluczem 8 (prawe dziecko korzenia). To "indeks korzenia" + "waga lewego poddrzewa węzła z kluczem 8" + "1" == 3 + 2 + 1 == 6
Indeksem elementu z kluczem 6 będzie "indeks korzenia" + 1 == 3 + 1 == 4
W związku z tym, aby uzyskać lub usunąć element według indeksu, potrzebny jest czas O(log n), ponieważ aby uzyskać potrzebny element, musimy najpierw go znaleźć (zejść od korzenia do tego elementu).
Głębia
Na podstawie wagi można również obliczyć głębokość drzewa. Niezbędna do równoważenia.
Aby to zrobić, wagę bieżącego węzła należy zaokrąglić do pierwszej liczby w potędze 2, która jest większa lub równa danej wadze, i wziąć z niej logarytm binarny. W ten sposób uzyskamy głębokość drzewa, pod warunkiem, że jest ono zrównoważone. Drzewo jest równoważone po wstawieniu nowego elementu. Nie będę przedstawiać teorii dotyczącej równoważenia drzew. W oryginalnych kodach znajduje się funkcja równoważenia.
Kod przekształceń wagi w 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));
}Podsumowanie
- Wstawienie nowego elementu odbywa się w O(log n)
- Usunięcie elementu według numeru porządkowego odbywa się w O(log n)
- Uzyskanie elementu według numeru porządkowego odbywa się w O(log n)
Szybkością O(log n) płacimy za to, że wszystkie dane są przechowywane w uporządkowanej formie.
Gdzie może być przydatna taka struktura — nie wiem. Po prostu zadanie, aby jeszcze raz zrozumieć, jak działają drzewa. Dziękuję za uwagę.
Linki
Projekt zawiera dane testowe do sprawdzenia szybkości działania. Drzewo jest wypełniane 1000000 elementami. I odbywa się kolejno usuwanie, wstawianie i pobieranie elementów 1000000 raz. To znaczy 3000000 operacji. Wynik okazał się całkiem niezły ~ 8 sekund.
Źródło: habr.com
