Struktury danych/Drzewa/Drzewa przedziałowe

Z Wikibooks, biblioteki wolnych podręczników.

Drzewo przedziałowe jest strukturą danych umożliwiającą szybkie wykonywanie następujących operacji:

  • Sprawdzenie wartości elementu (w czasie O(log n))
  • Zmianę wartości elementu (w czasie O(log n))
  • Znalezienie maksimum i minimum w przedziale (w czasie O(log n))
  • Zwiększenie wszystkich elementów w przedziale o pewną wartość (w czasie O(log n))

Implementacja drzewa przedziałowego jest stosunkowo prosta.

Spis treści

[edytuj] Budowa struktury

Będę zakładał, że rozmiar drzewa jest całkowitą potęgą dwójki.

Drzewo przedziałowe składa się z trzech tablic:

  • Tablicy max[0..n-2] - tablicy zawierającej maksimum w danym przedziale:
    • max[0] - maksimum całego drzewa
    • max[1] - maksimum elementów 0...\frac{n}{2}-1
    • max[2] - maksimum elementów \frac{n}{2}...n
    • max[3] - maksimum elementów 0...\frac{n}{4}-1
    • max[4] - maksimum elementów \frac{n}{4}...\frac{n}{2}-1
    • max[5] - maksimum elementów \frac{n}{2}...\frac{3n}{4}-1
    • max[6] - maksimum elementów \frac{3n}{4}...n − 1
    • i tak dalej, aż do elementów zawierających maksima z par.
  • Tablicy min[0..n-2], zbudowanej analogicznie, zawierającej minima z zakresów.
  • Tablicy p[0..n-2], zbudowanej analogicznie, zawierającej wartości dodane do każdej liczby z zakresu.
  • Tablicy val[0..n-1], zawierającej wartości elementów.

Elementy tablic min[i] i max[i] (dla 0<=i<n-1) zawierają wartości powiększone o wartości p[] wszystkich synów i oraz o wartość p[i] (warto na to zwrócić uwagę, gdyż może to spowodować trudne do wykrycia błędy).

Budowę tablic max, min oraz p ilustruje tabela, narysowana tutaj dla n==32:

tab[0]: 0...31
tab[1]: 0..15 tab[2]: 16..31
tab[3]: 0..7 tab[4]: 8..15 tab[5]: 16..23 tab[6]: 24..31
tab[7]: 0..3 tab[8]: 4..7 tab[9]: 8..11 tab[10]: 12..15 tab[11]: 16..19 tab[12]: 20..23 tab[13]: 24..27 tab[14]: 28..31
tab[15]: 0..1 tab[16]: 2..3 tab[17]: 4..5 tab[18]: 6..7 tab[19]: 8..9 tab[20]: 10..11 tab[21]: 12..13 tab[22]: 14..15 tab[23]: 16..17 tab[24]: 18..19 tab[25]: 20..21 tab[26]: 22..23 tab[27]: 24..25 tab[28]: 26..27 tab[29]: 28..29 tab[30]: 30..31

[edytuj] Ustawianie wartości elementu

Algorytm jest następujący:

Zakładamy, że mamy do wstawienia element k na pozycję l.

  1. Ustawiamy i: identyfikator bieżącego zakresu na 0
  2. Ustawiamy sumę p_sum na 0
  3. Dodajemy p_sum=p_sum+p[i]. Jeżeli element jest w lewej połowie zakresu, ustawiamy i=i*2+1 i przechodzimy do kroku 3. Jeżeli w prawej: i=i*2+2 i przechodzimy do kroku 3
  4. //wiemy, że n odpowiada przedziałowi na samym dole
  5. k=k-p_sum
  6. Ustawiamy val[l]=k
  7. Ustawiamy i na bezpośredniego ojca elementu l
  8. Zwiększamy k o wartość p[i] i porównujemy ją z wartościami min[i] i max[i], w razie potrzeby je aktualizując.
  9. Jeżeli i jest równe zeru, kończymy. W przeciwnym wypadku i=(i-1)/2 i przechodzimy do kroku 8

[edytuj] Sprawdzenie wartości elementu

Jak wyżej, l jest pozycją elementu.

  1. Ustawiamy i: identyfikator bieżącego zakresu na 0
  2. Ustawiamy sumę p_sum na 0
  3. Dodajemy p_sum=p_sum+p[i]. Jeżeli element jest w lewej połowie zakresu, ustawiamy i=i*2+1 i przechodzimy do kroku 3. Jeżeli w prawej: i=i*2+2 i przechodzimy do kroku 3
  4. Zwracamy p_sum+tab[l];

[edytuj] Ogólna metoda dla sprawdzenia minimów/maksimów i zwiększania zakresu

Ważnym pojęciem, jakie należy wprowadzić, jeżeli chodzi o drzewa przedziałowe, jest metoda zstępująca. Dla danego przedziału, na którym musimy wykonać pewną operację (zwiększenie, zmniejszenie, sprawdzenie minimum/maksimum) wykonujemy następującą funkcję (zakładając, że zadany przedział to: a...b-1):

rec(a, b, i, from, to, p) {
    if (a<=from) && (b>to) {
         Wykonaj operację: np. sprawdź minimum/maksimum, 
         dodaj do niego sumę p i zwróć wynik.
    } else if ((a<from) && (b<=from)) || ((a>to) && (b>=to)) {
         rec(a, b, i*2+1, from, (from+to)/2, p+p[i]);
         rec(a, b, i*2+2, to, (from+to)/2, to, p+p[i]);
         uwaga: nie wiem czy w dwóch powyższych wierszach nie występuje pomyłka o 1
    }
}

f(a, b) { rec(a, b, 0, 0, n-1, 0); }

[edytuj] Zwiększenie/zmniejszenie zakresu o pewną wartość

Wykorzystujemy metodę wstępującą i następującą procedurę:

rec(a, b, i, from, to, zwiekszenie) {
    if (a<=from) && (b>to) {
         p[i]+=zwiekszenie;
    } else if ((a<from) && (b<=from)) || ((a>to) && (b>=to)) {
         rec(a, b, i*2, from, (from+to)/2, zwiekszenie);
         rec(a, b, i*2+1, (from+to)/2 + 1, to, zwiekszenie);
         uwaga: nie wiem czy w dwóch powyższych wierszach nie występuje pomyłka o 1
    }
}

Aby zwiększyć elementy z przedziału a...b-1 o wartość w, wywołujemy f(a, b, w).

f(a, b, zwiekszenie) { rec(a, b, 0, 0, n-1, zwiekszenie); }

[edytuj] Sprawdzenie minimum zakresu

[TODO]

[edytuj] Sprawdzenie maksimum zakresu

[TODO]
Źródło „http://pl.wikibooks.org/wiki/Struktury_danych/Drzewa/Drzewa_przedzia%C5%82owe”