Temat: Jak sobie poradzić bez wskaźników?

Przykład: implementacja drzew binarnych w C++ i Javie

Wstawianie elementów:
Jeżeli drzewo jest puste wstawiamy element, który staje się korzeniem. Gdy jest niepuste, od korzenia
wyszukujemy odpowiednie odpowiedniego miejsce, następnie wstawiamy go jako następnik lewy
(gdy mniejszy) lub prawy (gdy większy).
Gdy już istnieje - zgłaszamy błąd lub możemy inaczej obsługiwać - np. listę o takim samym kluczu,
czy też zamiast sprawdzać czy mniejszy, sprawdzać czy nie większy przy szukaniu.

Usuwanie elementów:
Wyszukujemy węzeł, który mamy usunąć. Gdy nie znaleźliśmy - błąd.
Przypadki:
- gdy ma jeden następnik lub nie ma wcale ma następników - należy połączyć poprzednika
z tym następnikiem który jest (albo ustawić poprzednika na NULL gdy nie ma wcale następników)
i usunąć element
- jeśli ma dwa następniki - sytuacja się komplikuje...

W C++:

struct BSTNode

{

	int key;

	BSTNode *left, *right;

	BSTNode(int k = NULL)

	{

		left = right = NULL;

		key = k;

	}

};

W C++ bardzo pomocny jest wskaźnik na wskaźnik, można np. zrobić wskaźnik na pole root albo na elem->left czy elem->right:

        void Insert(int key)

	{

		if (root == NULL)

			root = new BSTNode(key);

		else

		{

			BSTNode *node = root;

			BSTNode **field; //wskażnik na pole BSTNode: left lkub right

			do

			{				

				if (node->key == key) throw "Klucz musi byc unikalny!";

				if (key < node->key) field = &node->left;

				else field = &node->right;

				node = *field;

			} while (node != NULL);

			assert(node == NULL);

			*field = new BSTNode(key);			

		}

	}



	void Delete(int key)

	{

		BSTNode *node = root;

		BSTNode **field = &root;

		while (node != NULL)

		{

			if (node->key == key) break;

			if (key < node->key) field = &node->left;

			else field = &node->right;

			node = *field;

		}

		if (node == NULL) throw "Nie znaleziono klucza do usuniecia!";

		if (node->left == NULL || node->right == NULL)

		{

			BSTNode **second; //może być wskaźnikiem na NULL lub nie

			if (node->left == NULL) second = &node->right; else second = &node->left;

			*field = *second;

		}

		else

		{

			tu trudniejszy przypadek

		}

	}

A jak to zrobić w Javie? class BSTNode, klasa jest referencją, ale jak referencję na roota, lub na pole left lub right?

Temat: Jak sobie poradzić bez wskaźników?

A w Javie pewnie będzie się to musiało sprowadzić do jakichś ifów czy case'ów.

Albo od razu w tych ifach, które masz, musiałbyś dodać ustawianie odpowiednio left = new BSTNode(key) lub right = new BSTNode(key), zamiast zostawiać sobie tylko jedno przypisanie na koniec;

albo... może trochę bardziej wyrafinowanie - jakaś osobna klasa, w której zamkniesz tę selekcję węzła do modyfikacji, a później ją tylko "wykonasz". Coś jak poniżej. Choć prawdę mówiąc wydaje mi się to przerostem formy nad treścią, chyba nie ma co tak tego komplikować w tym przypadku.

public class BSTChildUpdate {

	public enum ChildSelector {

		LEFT, RIGHT;

	};



	BSTNode parent;

	ChildSelector child;

	public BSTNodeUpdate(BSTNode parent, ChildSelector child) {

		this.parent = parent;

		this.child = child;

	}



	public void execute(BSTNode value) {

		switch (child) {

		case LEFT:

			parent.left = value;

			break;

		case RIGHT:

			parent.right = value;

		}

	}

}

Przykład użycia:

		BSTNodeUpdate update;

		if (key < node.key) {

			update = new BSTNodeUpdate(node, ChildSelector.LEFT);

		} else {

			update = new BSTNodeUpdate(node, ChildSelector.RIGHT);

		}

		update.execute(new BSTNode(key));

Temat: Jak sobie poradzić bez wskaźników?

Polecam zapoznac sie z istniejaca juz implementacja w java.util.TreeMap. Jest ona co prawda oparta o drzewo czerwono-czarne, ale mozna latwo ja uproscic do drzewa binarnego.