Drzewo przedziałowe

Z RNO-Wiki
Wersja Rno (dyskusja | edycje) z dnia 12:17, 20 gru 2012
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)

Informacje wstępne

Tablica z moimi zapiskami. Wykład podczas Warsztatów Olimpijskich w II UWr (2008)

Drzewo przedziałowe to struktura danych pozwalająca przechowywać przedziały w taki sposób, że możliwe są następujące operacje:

  • insert(a,b) - dodaj przedział domknięty [a,b]
  • remove(a,b) - usuń przedział domknięty [a,b]
  • top() - podaj ile co najwyżej przedziałów może pokryć jeden punkt.

Realizacja tej struktury danych bardzo przypomina Drzewo licznikowe, gdzie w liściach pamiętaliśmy liczbę wystąpień pewnej liczby, a w węzłach --- liczbę wystąpień liczb z pewnego zakresu. W strukturze drzewa przedziałowego, w liściach i węzłach pamietana jest liczba wystąpień pewnych przedziałów bazowych. Załączony rysunek pokazuje jak rozmieszczone są te przedziały w wierzchołkach drzewa.

Oto przykładowe użycie klasy ITree, a poniżej znajduje się jej pełna implementacja

#include "IntervalTree.cpp"
#include<cassert>
using namespace std;
 
int main()
{
	ITree T(-100, 100); // drzewo przedzialowe na ocinku [-100, 100]
 
	T.insert( 10, 20); // dodaj przedzial [ 10,20]
	T.insert( 15, 30); // dodaj przedzial [ 15,30]
	T.insert(-15, 30); // dodaj przedzial [-15,30]
	// kazdy punkt jest pokryty przez co najwyzej trzy przedzialy
	assert( T.top()==3 );
 
	// kazdy punkt jest pokryty przez co najwyzej trzy przedzialy
	T.insert(-15, 14);
	assert( T.top()==3 );
 
	// kazdy punkt jest pokryty przez co najwyzej dwa przedzialy
	T.remove(10, 20); // usun przedzial [10,20]
	assert( T.top()==2 );
	return 0;
}

Implementacja

Poniżej znajduje się pełna implementacja klasy ITree

#include<vector>
#include<cstdio>
#include<algorithm>
 
class ITree
{
private:
	const unsigned int N, _minX;
	unsigned int x, y;  // 0 <= x,y < N
	int amount;
 
	std::vector<unsigned int> _cnt, _max;
 
	/** oblicza potege liczby 2, ktora przekracza n
		Warunek:  0 <= n <= 2*10^9
	 */
	static unsigned int UpperPowerOfTwo( const unsigned int n ) {
		unsigned int ans = 1; while ( ans<=n ) ans <<= 1; return ans;
	}
 
	/** przechodzenie drzewa przedzialowego od korzenia
		Argumenty:
			k - numer wierzcholka, od ktorego zaczynamy przechodzenie
			[a,b] - przedzial reprezentowany przez wierzcholek nr k
		Zlozonosc: O( log N )
	*/
	void dfs(int k, int a, int b) {
		// jesli przedzial [x,y] zawiera sie w [a,b], to konczymy rekurencje
		if ( a >= x && b <= y ) { _cnt[k] += amount; _max[k] += amount; return; }
		int m = (a+b)/2;
		if ( x <= m ) dfs(  2*k,   a, m );
		if ( y > m  ) dfs(2*k+1, m+1, b );
		_max[k] = std::max( _max[2*k], _max[2*k+1] ) + _cnt[k];
	}
 
public:
	/**
		konstruktor drzewa przedzialowego
			minX .. maxX : maksymalny zakres przedzialow do dodawania/usuniecia
		Uwaga: implementacja uzywa dwoch tablic o rozmiarze 2*(maxX-minX)
	*/
	ITree(unsigned int minX, unsigned int maxX)
	: _cnt(N<<1,0), _max(N<<1,0) , N( UpperPowerOfTwo(maxX-minX) ), _minX ( minX ) {
		fprintf(stderr, "Utworzono drzewo przedzialowe o rozmiarze = %u, tzn. 0 <= x <= %u\n", _cnt.size(), N-1);
	}
	/**
		dodawanie przedzialu domknietego [x,y]
		Argumenty:
		  cnt : liczba przedzialow do wstawienia, domyslna wartosc = 1
	*/
	void insert(int x, int y, int cnt=1) { this->x = x-_minX; this->y = y-_minX; this->amount = cnt; dfs(1, 0, N-1); }
 
	/**
		usuwanie przedzialu domknietego [x,y]
		Argumenty:
		  cnt : liczba przedzialow do usuniecia, domyslna wartosc = 1
	*/
	void remove(int x, int y, int cnt=1) { insert(x,y,-cnt); }
	/**
		maksymalna liczba przedzialow pokrywajacych pewien punkt w przedziale [minX, maxX]
	*/
	int  top() const { return _max[1]; }
};
Osobiste