Autor: Andrzej Gąsienica-Samek
Drzewo licznikowe to struktura danych, która umożliwia przechowywanie liczb całkowitych z niewielkiego przedziału (np. od 0 do 8 388 607). Ogromną zaletą drzew licznikowych jest ich prostota. Niech n oznacza wielkość przedziału. Na drzewie licznikowym możemy wykonywać następujące operacje:
| Operacja | Koszt | Opis |
|---|---|---|
| Inicjuj | O(n) | Tworzy nowe drzewo dla przedziału 0..n-1 |
| Wstaw(x) | O(log n) | |
| Usuń(x) | O(log n) | |
| IleRównych(x) | O(1) | Ile liczb równych x znajduje się w strukturze |
| IleMniejszych(x) | O(log n) | Ile liczb mniejszych od x znajduje się w strukturze |
| ElementNumer(k) | O(log n) | Znajdź (k+1)-szy co do wielkości element |
| Lewo(x), Prawo(x) | O(log n) | Znajdź najbliższy element mniejszy (większy) od x |
Jak widać koszt operacji nie zależy od liczby aktualnie przechowywanych elementów, a jedynie od rozmiaru przedziału. Pamięć zajmowana przez drzewo licznikowe nie zmienia się w czasie i jest proporcjonalna do n.
Budowę drzewa licznikowego zaczynamy od określenia przedziału. Przedział zawsze zaczyna się od 0, a liczba elementów jest pewną potęgą dwójki. Załóżmy, że chcemy przechowywać liczby z przedziału 0..15. W tym celu definiujemy jedną stałą i jedną tablicę:
4: const
5: BASE = 16; (* Musi być
potęgą dwójki *)
7: var
8:
Tab: array [1..2*BASE-1] of Longint;
Tak zdefiniowana struktura pozwoli na przechowywanie elementów z przedziału
0..BASE-1. O prostocie tej struktury może świadczyć fakt, że są to wszystkie
potrzebne deklaracje. Tablicy Tab będziemy używali jak drzewa, w
taki sam sposób jak w przypadku stogów (zajrzyj do notatek o stogach). Korzeniem
będzie element numer 1. Element numer k będzie miał dwóch synów 2*k i 2*k+1.
Zauważmy, że w naszym przypadku mamy do czynienia z pełnym drzewem binarnym.
Liście mają numer BASE..2*BASE+1. W liściu o numerze k będziemy przechowywali
informację o liczbie elementów równych k-BASE. W węźle wewnętrznym k będziemy
przechowywali informację o liczbie wszystkich elementów przechowywanych w jego
poddrzewie. Mając tak zdefiniowaną strukturę bardzo prosto możemy ją
zainicjować:
11: procedure Inicjuj;
12: var
13:
i: Longint;
14: begin
15: for i
:= 1 to 2*BASE-1 do
16: Tab[i]
:= 0;
17: end;
Działanie tej procedury jest bardzo proste. Po jej wykonaniu uzyskujemy strukturę zawierającą z liściach i węzłach wewnętrznych same zera, a więc nie zawierającą żadnych elementów. Wstawienie elementu do struktury jest równie proste:
20: procedure Wstaw(x, ile:
Longint);
21: begin
22: Inc(x, BASE);
23: while x
> 0 do
24:
begin
25: Inc(Tab[x],
ile);
26: x :=
x shr 1;
27:
end;
28: end;
Ta procedura wstawia ile elementów x. Zauważ, że
może być używana zarówno do wstawienia pojedynczego elementu (ile=1), jak
również do usunięcia elementu (ile=-1). Jej działanie polega na przejściu od
liścia do korzenia i zmianie wszystkich wartości na ścieżce. Najbardziej
skomplikowaną procedurą jest liczenie elementów mniejszych od danego:
31: function IleMniejszych(x:
Longint): Longint;
32: var
33: r: Longint;
34: begin
35: r := 0;
36: Inc(x, BASE);
37: (* UWAGA!!! nie liczymy korzenia!
*)
38: while x
> 1 do
39:
begin
40:
if x and 1 = 1 then
41:
Inc(r, Tab[x-1]);
42: x :=
x shr 1;
43:
end;
44:
IleMniejszych := r;
45: end;
Pomysł polega na przejściu od liścia do korzenia. Dla każdego prawego elementu ze ścieżki powiększamy licznik o wartość jego lewego brata. Kolejną operacją jest znalezienie (k+1)-szego co do wielkości elementu (elementu numer k w drzewie). Wykonuje to następująca procedura:
48: function ElementNumer(k:
Longint): Longint;
49: var
50: x: Longint;
51: begin
52: x := 1;
53: while x <
BASE do
54:
begin
55: x :=
x shl 1;
56: if k
>= Tab[x] then
57:
begin
58:
Dec(k, Tab[x]);
59:
Inc(x);
60:
end;
61:
end;
62:
ElementNumer := x - BASE;
63: end;
Dla odmiany tym razem idziemy od korzenia w dół do pewnego liścia. Idąc w dół sprawdzamy, czy szukany element znajduje się z lewym, czy w prawym poddrzewie. Jeśli w prawym to schodząc w dół pomniejszamy k o liczbę elementów w lewym poddrzewie. Teraz do zrealizowania pozostały trzy bardzo proste funkcje:
65: function IleRownych(x:
Longint): Longint;
66: begin
67: IleRownych := Tab[BASE +
x];
68: end;
69:
70: function Prawo(x: Longint):
Longint;
71: begin
72: Prawo := ElementNumer(IleMniejszych(x) +
IleRownych(x));
73: end;
74:
75: function Lewo(x:
Longint): Longint;
76: begin
77: Lewo := ElementNumer(IleMniejszych(x)
- 1);
78: end;
KONIEC