Drzewo przedziałowe

Z RNO-Wiki
(Różnice między wersjami)
Linia 1: Linia 1:
[[Grafika:Itree_rno.jpg|thumb|Tablica z moimi zapiskami. Wykład podczas Warsztatów Olimpijskich w II UWr]]
+
== Informacje wstępne ==
 +
[[Grafika:Itree_rno.jpg|thumb|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 ''IntervalTree', a poniżej znajduje się jej pełna implementacja
 +
<source lang="cpp">
 +
#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;
 +
}
 +
</source>
 +
 
 +
== Implementacja ==
 +
Poniżej znajduje się pełna implementacja klasy '''IntervalTree'''
 +
<source lang="cpp">
 +
#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]; }
 +
};
 +
</source>

Wersja z 22:13, 14 gru 2012

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 IntervalTree', 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 IntervalTree

#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