Drzewo licznikowe

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

Pozwoliłem sobie tym razem napisać klasę, a nie strukturę. Zanim podam szczegóły, proszę spojrzeć na sposób użycia klasy CountingTree

#include "CountingTree.cpp"
int main()
{
	CountingTree T(50);
 
	T.insert( 30 );
	T.insert( 35 );
	T.insert( 15 );
	T.insert( 25 );
	T.insert( 45 );
	printf("Rozmiar = %d\n", T.size());
	printf("Drugi element = %u\n", T.select(2));
	printf("Trzeci element = %u\n", T.select(3));
 
	printf("Liczba punktow wiekszych od 25 = %u\n",  T.how_many_greater(25) );
 
	T.insert(40, 5); // wstawiamy 5 punktów jednoczeœnie
	printf("Liczba punktow wiekszych od 25 = %u\n", T.how_many_greater(25) );
 
	printf("Liczba punktow mniejszych od 30 = %u\n", T.how_many_less(30) );
 
	T.remove( 15 ); // usuwamy punkt 15
	T.remove( 40, 2 ); // usuwamy dwa punkty 40
	printf("Rozmiar = %d\n", T.size());
	printf("Drugi element = %u\n", T.select(2));
 
	return 0;
}

Poniżej znajduje się kod źródłowy dla klasy CountingTree

#include<vector>
#include<cassert>
#include<cstdio>
 
class CountingTree
{
private:
	typedef unsigned int uint;
	unsigned const int N;
	std::vector<unsigned int> T;
 
	/** oblicza potege liczby 2, ktora przekracza n
		Warunek:  0 <= n <= 2*10^9
	 */
	unsigned int UpperPowerOfTwo( const unsigned int n ) const
	{
		assert( n <= 2000000000 );
		unsigned int ans = 1; while ( ans<=n ) ans <<= 1;
		return ans;
	}
 
public:
	CountingTree(unsigned int max) : N( UpperPowerOfTwo(max) ), T(N<<1,0)
	{
		fprintf(stderr, "Utworzono drzewo licznikowe o rozmiarze = %d, tzn. maxX = %d\n", T.size(), N-1);
	}
 
	/** liczba wszystkich wstawionych punktów */
	unsigned int size() const { return T[1]; }
 
	/** sprawdzanie czy w strukturze nie ma ¿adnych punktów */
	bool empty() const { return size()==0; }
 
	/** dodawanie punktów o wspó³rzêdnej x
		Argumenty:
			cnt : liczba punktów do wstawienia, domyœlna wartoœæ = 1
		Wynik:
			liczba punktów mniejszych od x
	*/
	unsigned int insert( unsigned int x , int cnt = 1 )
	{
        assert( 0<=x && x<N );
		unsigned int k = N+x, ans = 0;
		while(k) { T[k] += cnt; if ((k&1)==1) ans += T[k-1]; k >>= 1; }
	}
 
	/** usuwanie punktów o wspó³rzêdnej x
		Argumenty:
			cnt : liczba punktów do usuniêcia, domyœlna wartoœæ = 1
		Wynik:
			liczba punktów mniejszych od x
	*/
	unsigned int remove( unsigned int x , int cnt = 1 ) { return insert(x,-cnt); }
 
	/** k-ty element */
	unsigned int select( unsigned int k ) const
	{
		assert( 1 <= k && k <= T[1] );
		uint r = 1; while( r<N ) { r <<= 1; if ( T[r] < k ) k -= T[r++]; }
		return r-N;
	}
 
	/** liczba punktów równych x */
	unsigned int how_many_equal( unsigned int x ) const { assert(x<N); return T[N+x]; }
 
	/** liczba punktów wiêkszych od x */
	unsigned int how_many_greater( unsigned int x ) const
	{
		assert( x<N );
		unsigned int k = N+x, ans = 0;
		while (k>1) { if ((k&1)==0) ans += T[k+1]; k >>= 1; }
		return ans;
	}
 
	/** liczba punktów mniejszych od x */
	unsigned int how_many_less( unsigned int x ) const { return size() - how_many_equal(x) - how_many_greater(x); }
};
Osobiste