# Array in Binären Suchbaum umwandeln



## carlos1976 (23. Januar 2010)

Hallo zusammen,

ich habe folgendes Problem, ich möchte einen sortierten Array int a[] = {1, 2, ..., 15} in einen Biänaren Suchbaum umwandeln der *vollständig ausgeglichen* ist.

Dazu hab ich folgende 2 Funktionen zur Verfügung die die Wurzel und die Blätter erzeugen:



```
void insert(int t) {
		if ( root == NULL ) {
			root = new BinaryNode(t);
		}
		else {
			insertRecur(t, root);
		}
	}
```


```
// rekursives Einfügen (Binary-SearchTree)!
	void insertRecur(int t, BinaryNode *curr) {
		// (rekursiv) links einfügen
		if ( curr->getKey() > t ) 
		{
			if ( curr->getLeft() == NULL ) 
			{
				BinaryNode* newNode = new BinaryNode(t);
				newNode->setParent(curr);
				curr->setLeft(newNode); 
			}
			else {
				insertRecur(t, curr->getLeft());
			}
		}
		// (rekursiv) rechts einfügen
		else {
			if ( curr->getRight() == NULL ) {
				BinaryNode* newNode = new BinaryNode(t);
				newNode->setParent(curr);
				curr->setRight(newNode); 
			}
			else {
				insertRecur(t, curr->getRight());
			}
		}
	}
```
*
So bekommt man den Baum ausgeglichen:*
1. Der Median (mittlere Wert) der Schlüssel wird zur Wurzel.
2. Die Schlüssel die kleiner als dieser Median sind, bilden den linken Teilbaum
der Wurzel, während die grösseren Schlüssel den rechten Teilbaum bilden.
3. Das gleiche Vorgehen wird dann angewendet um die Teilbäume zu bilden.

Wie implementiere ich eine Funktion, die die Elemente eines (beliebigen) sortierten
Arrays in einer Reihenfolge einfügt, die einen vollständig ausgeglichenen Suchbaum
entstehen lässt?

Danke für Eure Hilfe!


Hier der gesamte Code:


```
#include <iostream>
#include <math.h>
#include <assert.h>
using namespace std;

class BinaryNode {

public:
	BinaryNode(int key) {
		this->key    = key;
		this->parent = this->left = this->right = NULL;
	}

	BinaryNode* getParent()              { return this->parent;  }
	void        setParent(BinaryNode* p) { parent = p; }
	BinaryNode* getLeft()                { return this->left;  }
	void        setLeft(BinaryNode* l)   { left = l; }
	BinaryNode* getRight()               { return this->right; }
	void        setRight(BinaryNode* r)  { right = r; }
	int         getKey()                 { return this->key;  }
	void        setKey(int key)          { this->key = key;  }

private:
	BinaryNode* parent; // Eltern-Knoten
	BinaryNode* left;   // linkes Kind
	BinaryNode* right;  // rechtes Kind
	int key;            // referenzierte Daten
};    


class BinarySearchTree {
public:
	BinarySearchTree(void)   
	{ 
		root = NULL; 
		arrOut = NULL;
	}


	BinaryNode* getRoot()
	{
		return root;
	}

	bool isEmpty(void) { return (root == NULL); }

	// baut einen Binary-SearchTree auf!
	void insert(int t) {
		if ( root == NULL ) {
			root = new BinaryNode(t);
		}
		else {
			insertRecur(t, root);
		}
	}

	// lösche Element aus Baum
	void remove(BinaryNode* node)
	{
		// node ist Blatt
		if ( node->getRight() == NULL && node->getLeft() == NULL ) { 
			removeLeaf(node);
		}
		// node hat einen Unterbaum
		else if ( node->getRight() == NULL || node->getLeft() == NULL ) { 
			removeSingle(node);
		}
		// beide Teilbäume vorhanden: Tausche mit min. des re. Teilbaums
		else {
			BinaryNode* minRight = findMinBelow(node->getRight());
			node->setKey(minRight->getKey());   // kopiere Inhalte
			remove(minRight);  // muss Blatt oder Knoten ohne li. Teilbaum sein
		}
	}

	void removeLeaf(BinaryNode* leaf)
	{
		if ( leaf != root ) { // Blatt ist nicht Wurzel
			BinaryNode* parent = leaf->getParent();
			if ( parent->getLeft() == leaf ) // linkes Kind 
				parent->setLeft(NULL);
			else                             // rechtes Kind
				parent->setRight(NULL);
		}
		delete leaf;
	}

	void removeSingle(BinaryNode* node)
	{
		BinaryNode* child= (node->getLeft()==NULL ? node->getRight():node->getLeft());
		// Fall: Wurzel
		if ( node == root ) {
			root = child;
			child->setParent(NULL);
			delete node;
		}
		else {  // Fall: Zwischenknoten
			BinaryNode* parent = node->getParent();
			if ( node == parent->getLeft() ) { // linkes Kind von Eltern
				parent->setLeft(child);
			}
			else { // rechtes Kind von Eltern
				parent->setRight(child);
			}
			child->setParent(parent);
			delete node;
		}
	}

	// suche nach k; NULL als Ergebnis, falls k nicht vorhanden
	BinaryNode* searchNode(int k) 
	{ return searchNodeRecur(root, k); }

	BinaryNode* searchNextNode(int k, BinaryNode* prior=NULL) 
	{ 
		if ( prior == NULL ) 
			return searchNodeRecur(root, k); 
		else
			return searchNodeRecur(prior->getRight(), k); 
	}

	BinaryNode* findMin(void) 
	{ return findMinBelow(root); }

	BinaryNode* findMax(void) 
	{ return findMaxBelow(root); }

	BinaryNode* findPrev(BinaryNode* node) {
		// linker Teilbaum vorhanden
		if ( node->getLeft() != NULL )          
			return findMaxBelow(node->getLeft());

		// verfolge "linke Flanke" rückwarts
		BinaryNode* parent = node->getParent(); 
		while ( parent != NULL && parent->getLeft() == node ) {
			node   = parent;
			parent = node->getParent();
		}
		return parent;
	}

	void inOrder(void)   { inOrderRecur(root); }

	//Liefert die Tiefe eines Baumes
	int getMaxDepth(BinaryNode* node) 
	{
		if(isEmpty())
		{
			return 0;
		}
		int d1 = 0; 
		int d2 = 0;
		if(node->getLeft() != NULL) {
			d1 = getMaxDepth(node->getLeft());
		}
		if(node->getRight() != NULL) {
			d2 = getMaxDepth(node->getRight());
		}
		return (max(d1,d2) + 1);
	}



	/************************************************************************/
	/* Hilfsfunktion zur Ausgabe des Baumes                                 */
	/************************************************************************/
	void printTree()
	{
		//unschön, weil schon mal woanders berechnet: 
		int depth = getMaxDepth(root);
		loadToArray(depth);
		int nLineWidth = 2 << depth;

		int idx = 0;
		for(int d = 0; d < depth; d++) {
			for(int j = 0; j < (1 << d); j++) {
				int nNumSkips = (2<<(depth-d))-2;
				for(int s = 0; s < nNumSkips/2; s++) {
					cout << " ";
				}

				if (arrOut[idx] >= 0) {
					cout << arrOut[idx];
				} else {
					cout << " ";
				}
				int nNumSpaces = (1<<(depth-d));
				for(int s = 0; s < nNumSpaces; s++) {
					cout << " ";
				}
				idx++;
			}
			cout << "|" << endl; //markiert das Zeilenende (zum debuggen...)
		}
	}


private:

	/************************************************************************/
	/* Hilfsfunktion zur Ausgabe des Baumes                                 */
	/************************************************************************/
	void loadToArray(int depth)
	{
		//maximale Anzahl der Knoten im Baum
		int maxNumNodes = int((1 << depth) - 1);
		//arrOut ist das später sequenziell auszugebende Array.
		if(arrOut!=NULL) 
		{
			delete [] arrOut;
		}
		arrOut = new int[maxNumNodes];
		for(int i = 0; i < maxNumNodes; i++)
		{
			arrOut[i] = -1;
		}
		loadToArray(root,0,0);
	}

	/************************************************************************/
	/* Hilfsfunktion zur Ausgabe des Baumes                                 */
	/************************************************************************/
	void loadToArray(BinaryNode* node, int depth, int index)
	{	 
		//j ist der Index des Arrays, wo der Knoten gespeichert werden muss.
		int j =  (1 << depth) + index - 1;
		arrOut[j] = node->getKey();
		if(node->getLeft() != NULL)
		{
			loadToArray(node->getLeft(), depth + 1, (index << 1) + 0);
		}
		if(node->getRight() != NULL)
		{
			loadToArray(node->getRight(), depth + 1, (index << 1) + 1);
		}	  
	}

	// min-node unterhalb
	BinaryNode* findMinBelow(BinaryNode* node) 
	{
		while ( node->getLeft() != NULL )
			node = node->getLeft();

		return node;
	}

	// max-node unterhalb
	BinaryNode* findMaxBelow(BinaryNode* node) 
	{
		while ( node->getRight() != NULL )
			node = node->getRight();

		return node;
	}


	// rekursives Einfügen (Binary-SearchTree)!
	void insertRecur(int t, BinaryNode *curr) {
		// (rekursiv) links einfügen
		if ( curr->getKey() > t ) 
		{
			if ( curr->getLeft() == NULL ) 
			{
				BinaryNode* newNode = new BinaryNode(t);
				newNode->setParent(curr);
				curr->setLeft(newNode); 
			}
			else {
				insertRecur(t, curr->getLeft());
			}
		}
		// (rekursiv) rechts einfügen
		else {
			if ( curr->getRight() == NULL ) {
				BinaryNode* newNode = new BinaryNode(t);
				newNode->setParent(curr);
				curr->setRight(newNode); 
			}
			else {
				insertRecur(t, curr->getRight());
			}
		}
	}

	// rekursive Suche
	BinaryNode* searchNodeRecur(BinaryNode* node, int k) 
	{
		if ( node == NULL || node->getKey() == k )
			return node;

		if ( k <= node->getKey() ) 
			return searchNodeRecur(node->getLeft(), k);
		else                      
			return searchNodeRecur(node->getRight(), k);
	}


	void inOrderRecur(BinaryNode* curr) {
		if ( curr ) {
			inOrderRecur(curr->getLeft());
			cout << curr->getKey() << ", ";
			inOrderRecur(curr->getRight());
		}
	}

	BinaryNode* root;

	int* arrOut;
};

int main()
{
	BinaryNode* res = NULL;

	BinarySearchTree tree;
	int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};

	/************************************************************************/
	/* Rufen Sie hier Ihre Einfügeoperation auf                             */
	/************************************************************************/

	//tree.printTree(); //Kommentarzeichen entfernen

	cout << "=====================================\n"; 
	cout << "Sortiertes Ergebnis (in-order):\n"; 
	//tree.inOrder();   //Kommentarzeichen entfernen
	cout << endl;
	
	return 0;
}
```


----------



## Vereth (25. Januar 2010)

*Zu deinem Vorgehen:* Das mittlere Element, das du als Wurzel verwenden möchtest, splittet dein Array in einen linken Teilbaum und einen rechten Teilbaum. Auf diese kannst du dann wieder deinen Algorithmus des Splittens anwenden, bis du nur noch einzelne Elemente hast. Diese kannst du dann nach und nach zu einem Gesamtbaum zusammenfügen. Das kann man in einer relativ kurzen rekursiven Funktion implementieren. Allerdings ist der so erhaltene Baum sehr statisch, das Einfügen und Löschen von Elementen kann wieder dazu führen, dass du wieder einen Baum bekommst, der nicht mehr ausgeglichen ist. Ich vermute, das dein Array nur deswegen sortiert worden ist, um einen ausgeglichenen Baum erstellen zu können, der dann garantiert nur eine logarithmische Suchzeit benötigt. Wenn das wirklich so ist, dann solltest du das Problem anders angehen, denn die Zeit für Sortierung des Arrays ist höchstwahrscheinlich grösser als der Zeitgewinn beim Suchen.
*Zur allgemeinen Thematik:* Binärbäume werden in der Informatik oft verwendet, um Daten so zu organisieren, dass ein Suchalgorithmus nur eine logarithmische Zeit braucht. Allerdings können durch häufige Einfüge- und Löschoperationen Binärbäume entarten, sodass sie einer linearen Liste ähnlicher werden. Deswegen sind Verfahren entwickelt worden, Binärbäume so zu verwalten, dass sie auch bei Einfüge- und Löschoperationen garantiert ausgeglichen bleiben. Eines der bekanntesten Verfahren ist der Rot-Schwarz-Baum, der auch von diversen Programmiersprachen (z.B. Java) unterstützt wird. Eine noch bessere Alternative ist der AVL-Baum; es gibt auch eine (englische) Einführung in das Thema inklusive einer Implementation von AVL-Bäumen in C++.


----------

