Przejdź do zawartości

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.

Budowa struktury

[edytuj]

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

Drzewo przedziałowe składa się z czterech 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...
    • max[2] - maksimum elementów ...
    • max[3] - maksimum elementów 0...
    • max[4] - maksimum elementów ...
    • max[5] - maksimum elementów ...
    • max[6] - maksimum elementów ...
    • 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

Ustawianie wartości elementu

[edytuj]

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

Sprawdzenie wartości elementu

[edytuj]

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];

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

[edytuj]

[TODO]

Sprawdzenie minimum zakresu

[edytuj]
[TODO]

Sprawdzenie maksimum zakresu

[edytuj]
[TODO]