Ist das Design der Klasse sinnvoll? Oder soll ich besser einen boost::shared_ptr verwenden?

icarus2

Stimmt, ein einfacher Pointer wäre wohl das beste. Die Klasse Node besitzt die anderen Knoten ja gar nicht, habe ich ganz vergessen ^^

Danke.

314159265358979

Ich würde hier gar nicht so weit gehen und den Baum auf einen std::vector abbilden.

icarus2

314159265358979 schrieb:

Ich würde hier gar nicht so weit gehen und den Baum auf einen std::vector abbilden.

Ich weiss jetzt nicht genau was für eine Abbildung du wählen würdest und wie std::vector implementiert ist.
Aber ich könnte mir vorstellen, dass meine Implementierung bei häufigem Einfügen und Entfernen effizienter ist.

*Edit
Was ich vielleicht noch hätte sagen sollen: Auf dem Suchbaum sind die Operationen search, insert und remove erklärt. Der Baum muss nicht irgendwelche speziellen Kriterien wie z.B. maximale Höhendifferenz oder so erfüllen. Er kann also theoretisch zu einer linearen Liste degenerieren. Deshalb sehe ich keine effiziente Implementierung (auch was den Speicher angeht) mit einem std::vector. Das heisst natürlich nicht, dass es keine gibt ^^

volkard

search gibt dann nur einen bool zurück? oder eine const& auf die Nutzdaten?

Ich denke eher an

class Tree{
	struct Node
	{
		int value; // Value of this node
		Node* left;
		Node* Node right;

		Node( int a_value) 
                : value(a_value )
                , left(NULL)
                , right(NULL) {
                }
        };
        Node* root;
        public:
        Tree()
        : root(NULL) {
        }
        void insert(int value) {
           //ab hier schwierig
};

Wenn ich mich recht erinnere, kannst Du als Zwei-Sterne-Programmierer die anfallenden 12 Fallunterscheidungen vom remove auf 4 runterdrücken. Indem Du Knoten und Kanten denkst, typedef Node* Kante; und eine Suchfunktion anbietest, an welcher Kante der Wert hängen müßte, also wo man den Knoten dran finden müßte, wenn man danach sucht, und wo man den Knoten dranhängen müßte, wenn man ihn einfügen wöllte und wo man den ganzen Unterbaum dranhängen müßte, den man leider abhängen mußte, als bei remove ein Knoten verschwand, der zwei Kinder(-Bäume) hatte.

private:
      Node** searchItsParentsChildpointer(int value) {
           Node** p=&root;
           while(*p!=0) {
               if(value==(*p)->value)
                  return p;
               else
                  if(value>(*p)->value)
                     p=&(*p)->right);
                  else
                     p=&(*p)->right);
           }
           return p;
      }

und die dann in search, in insert und in remove verwenden.
(Ist aber 13 Jahre her, daß ich das machte und obiger Code ist nur zur Anschauung hingehudelt, könnte auch gerade mal total fwehlerhaft sein.)

314159265358979

http://magazin.c-plusplus.net/artikel/Binary%20Heaps

volkard

314159265358979 schrieb:

http://magazin.c-plusplus.net/artikel/Binary%20Heaps

Paßt hier nicht. Den Heap kann man nur deswegen linksaufgefüllt machen und in ein Array packen, weil die Heap-Bedingung
Papa ist kleiner als die beiden Kinder
schwächer ist als die Binärsuchbaumbedingung
Papa liegt zwischen den Kindern.
Im Heap kann man ein kleines rechtes Kind einfach zu einem kleinen linken Kind machen, wenn da Platz ist.

icarus2

314159265358979 schrieb:

http://magazin.c-plusplus.net/artikel/Binary%20Heaps

Ich möchte keinen binären Heap. Das ist nicht das gleiche wie ein Suchbaum. Aber trotzem danke.

@volkard
Meine Klasse Tree sieht in etwa gleich aus. Von der Theorie her weiss ich wie der Suchbaum funktioniert, das müsste dann gehen.
Könntest du mir kurz das ** erklären? Ich verstehe nicht ganz was z.B.

Node** p=&root;

macht. Ich hab noch nie ** verwendet ^^

Nexus

Zeiger auf ein Zeiger. Ermöglicht es zum Beispiel, den Zeiger selbst und nicht nur das Objekt zu ändern. Sinnloses Beispiel:

void SetToNull(int** ptr)
{
    *ptr = NULL;
}

int main()
{
    int* ptr;
    SetToNull(&ptr);
}

Aber das braucht man sehr selten. Das gleiche könnte man mit Referenzen erreichen.

Artchi

Roger Wilco schrieb:

shared_ptr würde gehen, aber ich glaube ein reiner Zeiger wäre hier besser, da shared_ptr wiederrum "geteilter Besitz" bedeutet. Aber node besitzt left und right nicht.

Nein, Parent besitzt nicht Child? Das ist mir neu.

icarus2

@Nexus:
Danke für die Erklärung.

volkard

icarus2 schrieb:

Könntest du mir kurz das ** erklären? Ich verstehe nicht ganz was z.B.
Node** p=&root;
macht. Ich hab noch nie ** verwendet ^^

Das ist auch recht verrückt. Schön, daß Du mit Nexus es klären konntest.
Dein Prof erwartet sicher nicht ** zu sehen, sondern die normale Version, die im Vergleich dazu beim remove halt ein wenig in die Breite geht, na bei den anderen auch. Meine **-Version ist nicht produktiver Code, sondern ein Gedicht⁽¹⁾. Damals hat Prof Weber in Darmstadt die Aufgabe gestellt und ich war in einer sehr explorativen Phase.
Falls Du auch im 2. Semester bist, sollst Du sowas noch gar nicht hinkriegen. Ich dachte nur, vielleicht hast Du ja auch Spaß daran. Denn das Ergebnis ist einfach hübsch, kann man nicht anders sagen.

⁽¹⁾
Eher ein Wortspiel, wie "Der Torwart, dieser Volksheld, hält, trotz Regen auf das Spielfeld fällt."

icarus2

@volkard
Ich werde mir das mit den ** dann später mal anschauen, sieht interessant aus.

Im Moment möchte ich zuerst allerdings den SearchTree zum laufen bringen. Ich habe schon länger nicht mehr mit Pointern hantiert in C++ und habe entsprechend ein bisschen Probleme mit dem ganzen.

Ich habe bis jetzt folgenden Code:

class SearchTree
	{
	private:
		struct Node
		{
			int value;
			Node *left;
			Node *right;

			Node( int a_value ) : value(a_value), left(NULL), right(NULL) {}
		};

		Node* root;

	public:
		SearchTree() : root(NULL) {}

		void insert( int a_value )
		{
			Node* current_node = root; // current_node is a node where a_value might me inserted
			bool inserted = false;

			while ( !inserted )
			{
				if ( current_node == NULL ) // Insertion location found
				{
					current_node = new Node( a_value );
					inserted = true;
				}
				else if ( a_value < current_node->value ) // Go left
					current_node = current_node->left;
				else if ( a_value > current_node->value ) // Go right
					current_node = current_node->right;
				else // Value already in tree
				{
					std::cout << "Value already in tree" << std::endl;
					inserted = true;
				}
			}
		}
	};

Wenn ich jetzt z.B. diesen Code hier schreibe

int main()
{
	SearchTree tree;

	tree.insert( 10 );
	tree.insert( 8 );
	tree.insert( 12 );
}

dann habe ich das Problem, dass trotzdem noch alle Nodes NULL sind. Ich glaube das Problem liegt bei

Node* current_node = root; // current_node is a node

Wenn ich current_node verändere, ändert sich root nicht. Liegt das daran, dass beim Kopieren der Adresse root NULL ist? Wenn ja, wie kann ich das Problem am besten umgehen?

icarus2

So, es scheint nun soweit zu funktionieren mit dem Einfügen. Für diejenigen, die es interessiert wie ich es gelöst habe:

class SearchTree
	{
	private:
		struct Node
		{
			int value;
			Node *left;
			Node *right;

			Node( int a_value ) : value(a_value), left(NULL), right(NULL) {}
		};
	public:
		Node* root;

	public:
		SearchTree() : root(NULL) {}

		void insert( int a_value )
		{
			bool inserted = false;

			if ( root == NULL ) // If there is no root yet, directly insers the new Node there
			{
				root = new Node( a_value );
				inserted = true;
			}

			Node* current_node = root; // Start at the root

			while ( !inserted )
			{
				if ( a_value < current_node->value ) // Go to left
				{
					if ( current_node->left == NULL ) // Left child is NULL
					{
						current_node->left = new Node( a_value );
						inserted = true;
					}
					else // Else continue with left child
					{
						current_node = current_node->left;
						continue;
					}
				}

				else if ( a_value > current_node->value ) // Go to right
				{
					if ( current_node->right == NULL ) // Right child is NULL
					{
						current_node->right = new Node( a_value );
						inserted = true;
					}
					else // Else continue with right child
					{
						current_node = current_node->right;
						continue;
					}
				}
				else // Value already in tree
				{
					std::cout << "Value already in tree" << std::endl;
					break;
				}
			}
		}

	};

PS:
Ich habe mir noch nicht genau überlegt, ob sich der Code noch vereinfachen oder optimieren lässt. Könnte also durchaus bessere Lösungen geben

padreigh

schreit das nicht eigentlich nach einer rekursiven Lösung statt dem while() drumrum?

void insert( int a_value )
        {
                if ( a_value < current_node->value ) // Go to left
                {
                    if ( current_node->left == NULL ) // Left child is NULL
                    {
                        current_node->left = new Node( a_value );
                        return;
                    }
                    else // Else continue with left child
                    {
                        current_node->left.insert(a_value);
                    }
                }

                else if ( a_value > current_node->value ) // Go to right
                {
                    if ( current_node->right == NULL ) // Right child is NULL
                    {
                        current_node->right = new Node( a_value );
                        return;
                    }
                    else // Else continue with right child
                    {
                        current_node->right.insert(a_value);
                    }
                }
                else // Value already in tree
                {
                    std::cout << "Value already in tree" << std::endl;
                    break;
                }
            }
        }

Abgesehen davon .... warum merkst du dir in jedem Node den root? Eigentlich wird es doch eher so gemacht das du in deiner Applikation einen root-node (member) hältst, willst du was wissen benutzt du das als Einstiegspunkt in den Baum. Dafür brauchst du natürlich auch noch neben insert() sowas wie find().
Was dir definitiv fehlt ist jemand, der die ganzen new's wieder löscht - da du das anlegen jetzt ja in deiner Struct erledigst solltest du das Löschen auch dort erledigen --> Destructor der seine childs löscht. Deinem Insert fehlt auch noch sowas wie eine Balacierung oder Korrekturmethodik damit du vernünftig suchen kannst. Sonst kannst du bei ungeeigneten Eingaben sehr tiefe unbalancierte sowie suchtechnisch völlig Unsinnige Bäume erzeugen:

inserte mal 10 9 8 7 6 5 4 3 2 1 und guck was passiert. Oder als root: 0, dann 4 und -4 und dann 2.

Suchbäume sind mE ein eher nichttriviales Problem - zumindest wenn du da was selbst entwickeln willst. Irgendwie was zu speichern und irgendwie wiederzufinden (zur Not alles durchsuchen) ist einfach, das ganze geschickt zu lösen braucht meist etwas mehr Aufwand - als Einstieg zB
http://de.wikipedia.org/wiki/Binärer_Suchbaum
http://de.wikipedia.org/wiki/Balancierter_Baum
http://de.wikipedia.org/wiki/Rot-Schwarz-Baum

volkard

padreigh schrieb:

schreit das nicht eigentlich nach einer rekursiven Lösung statt dem while() drumrum?

Nein. Die rekursive Lösung ist nur langsamer und unzuverlässiger.

padreigh schrieb:

Deinem Insert fehlt auch noch sowas wie eine Balacierung oder Korrekturmethodik damit du vernünftig suchen kannst. Sonst kannst du bei ungeeigneten Eingaben sehr tiefe unbalancierte sowie suchtechnisch völlig Unsinnige Bäume erzeugen

Das weiß er.
Es ist ein sehr guter Einstieg, zuerst einen Suchbauum zu machen, der kein balancing hat. Und erst, wenn man mit dem zufrieden ist, sich an anderere wagt.
Und das macht er gerade.

icarus2

@padreigh
Ich schliesse mich dem was volkard gesagt hat an.

Ich weiss, dass ich den Speicher noch nicht frei gebe, das kommt noch. Es gibt dafür dann auch ein remove. Ich muss dann noch genau schauen wie ich das mit dem delete mache.

Der Suchbaum ist natürlich auch noch nicht fertig und ich bin mir ziemlich sicher, dass er noch nicht korrekt funktioniert. Ich arbeite noch dran