Podejście pierwsze

Na drzewie BST, jak na każdej innej strukturze, mamy zdefiniowanych kilka operacji. Kod wyjściowy wygląda następująco (dla czytelności olewam szablony i robię na intach):

class TreeNode
{
	public:
		TreeNode(const int pValue);
		~TreeNode();
 
		// Tutaj operacje
	private:
		TreeNode *parent;
		TreeNode *left;
		TreeNode *right;
		int value;
};

Wiadome jest, że metody powinny wykonywać jakąś pracę na obiekcie, spod którego zostały wywołane, z tym że ten obiekt musi faktycznie istnieć, a nie być np. pustym wskaźnikiem. Dlatego zestaw operacji musimy podzielić sobie na dwie części: te, które nie mają sensu w przypadku braku węzłów (ergo, zakładamy, że nie będą mogły być wywołane na pustym drzewie) oraz takie, które potrafią coś z pustym drzewem już zrobić. W tej pierwszej grupie mamy:

• Element najmniejszy w danym poddrzewie
• Element największy w danym poddrzewie
• Poprzednik węzła
• Następnik węzła
• Rotacja węzła w lewo
• Rotacja węzła w prawo
• Usuwanie węzła
• Wyszukiwanie węzła o podanym kluczu

W grupie drugiej formalnie znajduje się tylko operacja dodawania, ale zdecydowałem się przerzucić tutaj jeszcze dwie ostatnie. Zauważmy, że w przypadku binarnego drzewa wyszukiwawczego nie możemy tak po prostu potraktować sobie węzła z niechcianą wartością operatorem delete. Formalnie operacja ta zdefiniowana jest tylko dla liści lub węzłów z jednym synem, natomiast dla dwóch robimy sztuczkę, że szukamy poprzednika/następnika, zamieniamy wartości węzłami i teraz niechciany klucz może już polecieć jako liść. Fakt - można kombinować jakoś z odpowiednim przepinaniem wskaźników zamiast skopiowaniem klucza, ale z racji tego, że robiłem to na kolokwium, wolałem trzymać się bardziej "kanonu" :).

Wyszukiwanie zostało wydzielone z innego powodu. Dla zadanego ciągu liczb można utworzyć wiele różnych drzew mających własność BST i ograniczając się tylko do nich, formalnie żadne z nich nie jest "lepsze" od dowolnego innego. Gdybyśmy więc wywołali operację "znajdź" dla podwęzła, jej zachowanie dla końcowego użytkownika jest więc niezdefiniowane - w zależności od konkretnego drzewa może on uzyskać odpowiedź, że klucz jest lub że go nie ma. W praktyce ma to tylko znaczenie dla wewnętrznej implementacji, natomiast użytkownik klasy powinien mieć tylko dostęp do globalnej metody wyszukującej.

Ostatecznie więc implementacja drzewa bazująca wyłącznie na obiektach węzłów w OOP nie zda swojego egzaminu. W normalnej praktyce istotny jest też jeszcze jeden powód; mianowicie, co się stanie, jeżeli wskaźnik do drzewa będziemy mieć w kilku miejscach? Drzewa BST mają to do siebie, że możliwe jest zastąpienie korzenia innym węzłem, a w przypadku równoważenia splay jest to nawet niezbędne, żeby cokolwiek sensownego tam zrobić :). Wtedy takie funkcje modyfikowałyby jeden wskaźnik, a wszystkie pozostałe wskazywałyby zły węzeł jako korzeń. Nie trzeba mówić, że taki program wysypałby się jeszcze zanim zdążylibyśmy go uruchomić :D.

Podejście drugie

Zmieńmy więc trochę podejście i przyjmijmy, że mamy dwie klasy: jedna reprezentuje węzeł oraz operacje dotyczące tylko jego (poprzednik, następnik, rotacje) oraz klasę drzewa, której operacje dotyczą struktury danych jako całości, a w dodatku zawierają jedyny wskaźnik na aktualny korzeń. Dodając do tego polimorfizm, możemy elegancko rozszerzać oryginalne BST np. o równoważenie AVL, czerwono-czarne czy splay, po prostu nadpisując kolejne metody. Żeby wszystkie typy mogły operować na tych samych obiektach węzła, z definicji dokładamy tam pole "option" będące w przypadku AVL wagą gałęzi, a w czerwono-czarnych kolorem węzła. Splay i oryginalne BST do niczego tego pola nie potrzebują; ono po prostu tam sobie jest i tyle.

 
class BST;
 
class TreeNode
{
	public:
		TreeNode(const int pValue);
		~TreeNode();
 
		TreeNode *getParent(){ return parent; }
		TreeNode *getLeft(){ return left; }
		TreeNode *getRight(){ return right; }
		int getValue(){ return value; }
 
		TreeNode *min();
		TreeNode *max();
		TreeNode *successor();
		TreeNode *predecessor();
 
	private:
		bool rotateLeft(TreeNode **root);
		bool rotateRight(TreeNode **root);
 
		TreeNode *parent, *left, *right;
		int value;
		char option;
 
		friend class BST;
};
 
class BST
{
	public:
		BST();
		virtual ~BST();
 
		TreeNode *getRoot(){ return root; }
		virtual TreeNode *find(const int pValue);		
 
		virtual bool insertItem(const int pValue);
		virtual bool deleteItem(const int pValue);
 
		virtual bool rotateLeft(const int pValue);
		virtual bool rotateRight(const int pValue);
 
		void print();
	protected:
		virtual void displayNode(TreeNode *n, char branch);
 
		TreeNode *locate(const int pValue);
		TreeNode *root;
 
	private:
		void recursivePrint(TreeNode *n, int level, char branch);
};

Ponieważ operacje rotacji mogą zmienić korzeń, potrzebują one wskaźnika na wskaźnik do aktualnego - a w związku z tym nie mogą być bezpośrednio udostępnione użytkownikowi. Jednak taki kij ma dwa końce. Żeby drzewa mogły się do nich dostać, trzeba oznajmić, że one wszystkie są przyjaciółmi klasy TreeNode i mamy klops, jako że dokładając nowy rodzaj drzewa BST, musimy i tak nadpisać, że jest on przyjacielem węzłów (niestety nie jest to dziedziczone, a przynajmniej mi się nie chciało dziedziczyć :)). Trzeba więc poszukać innych mechanizmów, które nie naruszą hermetyzacji, a jednocześnie sprawią, że kod będzie bardziej przenośny. Innymi słowy, trzeba pozbyć się jakoś tego friend class BST z TreeNode.

Zastanawiające może być umieszczenie w jednej klasie dwóch funkcji wyszukujących: find() oraz chronionej locate(). Zrobiłem tak dlatego, że pierwsza przeznaczona jest dla użytkownika, druga dla twórcy klasy. W normalnych warunkach są one dokładnie tym samym, lecz już w przypadku drzew splay wyszukiwanie działa tam inaczej - modyfikuje korzeń drzewa. Jednocześnie już dla samego uproszczenia implementacji tego wyszukiwania, potrzebujemy jego wersji podstawowej; tak więc w przypadku splay metoda find() korzysta z locate(), ale nie jest już tym samym.

Podsumowanie

Programu ostatecznie nie zdążyłem skończyć przed kolokwium, ale temat pozostawiam wciąż otwarty, gdyż BST stwarza kilka ciekawych problemów projektowych, które naprawdę warto spróbować rozwiązać.

Powrót

Na Zyxist.com panuje swoboda wyrażania opinii oraz krytyki pod dowolnym adresem. Jedyny warunek: musi być ona kulturalna i rzeczowa. Na chamstwo, prostactwo lub jawne obrażanie kogokolwiek nie ma tu miejsca i takie komentarze są bardzo szybko usuwane. Jeśli zamierzasz polemizować z treścią wpisu, wpierw uważnie ją przeczytaj.