optimaler linksorientierter binärer Baum mit Heap-Bedingung

[Soleil]

Ich möchte aber die Methoden selber definieren und möglichst von den STL-Bibliothek ausweichen. Hat jemadn eine Idee

[CStoll]

http://de.wikipedia.org/wiki/Heap

[don_basto]

Soleil schrieb:

[..], wleche Klassen ich brauche, um diesen binären Baum darzustellen. Wohlgemerkt: ein optimaler, linksorientierter binärer Baum.

Was stellst du dir darunter vor?

Zum Anzeigen des STL-Heaps hatte ich mir mal ein Template zusammengebastelt:

template <class RandomAccessIterator>
void show_heap(RandomAccessIterator first,		// Anfang des Heap-Bereichs
			   RandomAccessIterator last,		// Ende des Heap-Bereichs
			   int maxLength)					// max. Länge der Werte
{
	std::iterator_traits<RandomAccessIterator>::distance_type n =
		std::distance(first, last);
	assert(n>0);

	// Berechne die Baumtiefe
	int depth = 0;
	int powerOfTwo = 1;
	while (powerOfTwo < n)
	{
		powerOfTwo *= 2;
		++depth;
	}

	// Zeichne den Baum
	std::cout << "Der Heap-Baum:" << std::endl;
	RandomAccessIterator it = first;
	int count = 1;
	int curDepth = 1;
	int space = (maxLength)* pow(2.0f, depth-curDepth);
	powerOfTwo = 1;
	while (it != last)
	{
		if (count > powerOfTwo)
		{	
			powerOfTwo *= 2;
			count = 1;
			++curDepth;
			space = (maxLength)* pow(2.0f, depth-curDepth);
			std::cout << std::endl;
		}
		std::cout.width(space);
		std::cout << *it;
		for (int i=0; i<space; ++i)
			std::cout << ' ';

		++count;
		++it;
	}
	std::cout << std::endl;
}

Vllt. hilft dir das weiter. Die STL-Funktionen sind IMHO ein guter Ausgangspunkt, um die Funktionsweise von binären Bäumen zu verstehen.

[hustbaer]

Guck mal da:
http://de.wikipedia.org/wiki/Binomial-Heap

Und:

class BaumImpl;

class Baum {
    BaumImpl* m_wurzel;
};

class BaumImpl {
    T m_daten;
    BaumImpl* m_linkerTeilbaum;
    BaumImpl* m_rechterTeilbaum;
};

Die Trennung Baum/BaumImpl brauchst du eigentlich nur für den Fall dass ein Baum komplett leer ist (aber da es den oft gibt brauchen wir's eben). IDs/Keys/... brauchst du dann nichtmehr.
Evtl. kann es noch Sinn machen einen "parent" Pointer in BaumImpl zu haben der immer auf den Parentknoten (also den Knoten "darüber") zeigt.

[Soleil]

Danke euch,

@hustbear: da geht es nicht um den binären Baum, sondern um den binominalen Heap. Ist ähnlich abe rnicht gleich.

@Don-basto: Also ich erkläre kurz, was ein optimaler, linksorientierter binärer Baum ist:

1. Ein optimaler binärer Baum ist, wenn jeder innere Knoten, außer rvtl. in der vorletzten Ebene, zwei Kinder hat(minim. Höhe)

2. Ein binärer linksorientierter Baum ist, wenn alle Knoten in einer bestimmten Ebene soweit wie möglich links liegen.

Leider kann ich es nicht grafisch zeigen, wäre einfacher

D.h beim Einfügen wird immer soweit wie möglich links eingefügt.

[wolle petry]

Soleil schrieb:

1. Ein optimaler binärer Baum ist, wenn jeder innere Knoten, außer rvtl. in der vorletzten Ebene, zwei Kinder hat(minim. Höhe)

das ist ein strikt binärer baum.

[don_basto]

Soleil schrieb:

1. Ein optimaler binärer Baum ist, wenn jeder innere Knoten, außer rvtl. in der vorletzten Ebene, zwei Kinder hat(minim. Höhe)

2. Ein binärer linksorientierter Baum ist, wenn alle Knoten in einer bestimmten Ebene soweit wie möglich links liegen.

AFIAK bauen die Heap-Fkt. der STL genau so eine Struktur.

[hustbaer]

@Soleil: Ok, sorry, dann hab ich den binären Heap und den binomial Heap verwechselt. Egal. Die C++ Konstrukte mit denem man einen Baum darstellen kann bleiben sich gleich. Und ja, std::make_heap (...) macht einen "Heap", also einen "binären".

[Apollon]

Ein Heap ist automatisch ein linksorientierter Binaerbaum. Ist eine Sache der Definition. Kannst also nur nach Heap suchen und den Rest getrost vergessen.

[Soleil]

Wohlgemerkt, dieser Baum, den ich oben erwähnt habe soll im Heap dargestellt werden und die Hep-Bedingung erfüllen, d.h. es soll sortiert werden. Wurzel= 0 und von links nach rechts nach unten durchnummeriert werden

[hustbaer]

@Soleil: so wie du das geschrieben hast hiess das für mich du willst nen Baum haben, und nicht die Array Darstellung eines Baumes. Das zweite nennt man Heap, das erste einfach Baum. Da du immer von einem Baum geschrieben hast... Gelle?

Und für die Array Darstellung braucht du wie gesagt keine speziellen Strukturen/Klassen/...

[volkard]

Soleil schrieb:

Wohlgemerkt, dieser Baum, den ich oben erwähnt habe soll im Heap dargestellt werden und die Hep-Bedingung erfüllen, d.h. es soll sortiert werden. Wurzel= 0 und von links nach rechts nach unten durchnummeriert werden

soll er nun ein sortierbaum sein oder ein heap?

im sortierbaum gilt: linkesKind <= ich und ich <= rechtesKind
im heap gilt: ich <= linkesKind und ich <= rechtesKind

dadurch kann man im heap wunderbar immer das kleinste element finden. es ist die wurzel. ob man den heap jetzt zusätzlich als linksaufgefüllten baum macht, als unballancierten, als stets ballancierten, als spreizbaum-ähnliches, als wald in einer liste, das ist dem heap eher egal. es bleibt ein heap. linksaufgefüllt ist automatisch ballanciert.

falls man den heap zufällig linksaufgefüllt macht, bietet sich die darstellung in einem array an. dann hat man den üblichen heap.

was willst du eigentlich haben? es scheint fast, als wölltest du einen linksaufgefüllten sortierbaum in ein array legen (ganz schlechte idee!). der heap lebt linksaufgefüllt sehr froh. durch die schwaächere integritätsbedingung (die heapbedingung schreibt mir die reihenfolge meiner kinder nicht vor), hab ich nmehr freiheiten, nach einfügungen oder lschungen die integritätsbedingung wiederherzustellen.

[Apollon]

Ich habe nocmal den Eingangpost gelesen. Das ist die Rede von Key und Inhalt. Es wird also ein Suchbaum benoetigt und kein Heap.

Stichwort: AVL-Baum.

[volkard]

Apollon schrieb:

Das ist die Rede von Key und Inhalt. Es wird also ein Suchbaum benoetigt und kein Heap.

jup. dann warte ich mal, bis er sich vom heap verabschiedet.

(mal nicht annehmen, daß er doch key-value paare in eine priority-queue stecken mag und dann immer mal den value mit dem bisher kleinsten key braucht und rausnimmt).

[Soleil]

Hallo nochmal

Ich werde mich nicht vom Heap verabschieden. Ich brauche einen Baum, der im Heap dargestellt wird und vektoriell. Ich muss einen Heap als Array dynamisch definieren und die Indexe im Heap werden die Positionen der Knoten darstellen. Die Wurzel hat die Position 0, das linke Kind die Poistion 1 und das rechte Kind die Position 2. So kann man von einer Position aiusgehend auf die rechten und linken Kinder zugreifen und auch den Elternknoten heruasfinden. Mit den Formeln:

rechtes Kind= 2i + 2 //i: Index im Heap
linkes Kind= 2i+1
parent= (i-1)/2

Da der Baum linksorientiert und binär ist, wird immer so weit wie möglich in der untersten Ebene links eingefügt. jedes Knoten hat max 2 Kinder(binär).

Beim Löschen dagegen wird das kleinste Atom gelöscht(Wurzel; deleteMin()) dann wird der letzte Knoten im Baum auf die Wurzel kopiert. Der Heap muss immer sortiert werden. Nach dem Einfügen wird bubble up und nach dem Löschen wird Bubble down verwendet.

Ich hoffe ich habe mich jetzt ein bischen verständlicher ausgedruckt? :p

Danke nochmal für euere Mühe mir zu helfen

Soleil

[Soleil]

........ noch etwas: es ist kein Suchbaum

Kann jetzt jemand das Rätsel lösen?

Soleil

[hustbaer]

Was für ein Rätsel? Du hast garkeinen Baum, du hast einen Heap. Das ist nicht dasselbe. Dass es so-gut-wie-das-selbe ist ist auch klar aber irrelevant. Für einen Heap brauchst du bloss einen std::vector wo du deine Elemente reintust, hab ich aber auch schon 3x geschrieben.

Also was ist nun deine Frage???

[volkard]

Soleil schrieb:

Ich hoffe ich habe mich jetzt ein bischen verständlicher ausgedruckt? :p

vielleicht.
hab da mal code ausgegraben. vielleicht isses ungefähr das, was du suchst.

template<class T>
class Heap
{//Ein Heap ist ein Binärbaum mit der Bedingung, daß jeder 
	//Knoten kleinergleich seinen beiden Kindern (falls 
	//vorhanden) ist. Diese Implementierung als Array 
	//garantiert außerdem, daß der Baum ballanciert ist. 
	//Einfügen eines beliebeigen Elements und Ausfügen 
	//des kleinsten haben nur logarhitmischen Zeitbedarf. 
	//Weil die Integritätsbedingung schwächer als beim 
	//normalen Binärbaum ist, ist der Heap auch ein wenig 
	//schneller.
private:
	int size;
	T *data;
	int maxSize;
public:
	Heap(int s=300)
	{
		data=new T[maxSize=s];
		size=0;
	};
	~Heap(void)
	{
		delete[] data;
	};
	bool isEmpty(void) const
	{
		return size==0;
	};
	void grow()
	{
		maxSize=maxSize*3/2;
		T *oldData=data;
		data=new T[maxSize];
		for(int i=0;i<size;++i)
			data[i]=oldData[i];
		delete[] oldData;
	};
	template<class C>
	void push(const T &t,const C &comparator)
	{
		if(size>=maxSize)
			grow();
		int pos=size++;
		//Ganz hinten einfügen
		data[pos]=t;
		while(comparator.lessThan(data[pos],data[pos/2]))
		{//Solange ich kleiner als mein Papa bin, darf ich 
			//ihn verdrängen. Spätestens beim ersten Element 
			//hört die Schleife auf, weil es sein eigener Papa
			//ist. 
			swap(data[pos/2],data[pos]);
			pos/=2;
		};
	};
	T &top(void) const
	{
		return data[0];
	};
	template<class C>
	void pop(const C &comparator)
	{
		assert(size>0);
		if(--size)
		{
			int p=1,c1,c2;
			data[0]=data[1];
			while(c1=p*2,c2=c1+1,c1<size)
			{//Wenn der Papa verschwindet, dann muß das kleinere 
				//Kind seinen Platz einnehmen, dessen kleineres 
				//Kind seinen, solange, bis jemand keine Kinder 
				//mehr hat
				if(comparator.lessThan(data[c2],data[c1]))
					c1=c2;
				data[p]=data[c1];
				p=c1;
			};
			//Und in die Lücke wird das letzte Element ganz 
			//normal eingefügt. 
			data[p]=data[size];
			while(comparator.lessThan(data[p],data[p/2]))
			{
				swap(data[p/2],data[p]);
				p/=2;
			};
		};
	};
};

[Soleil]

Hallo nochmal

Danke Volkard, jetzt kommen wir zu meiner Lösung und Vorstellung etwas näher. Aber ich weiß nicht, ob ein optimaler, linksorientierter binärer Baum, der die Heap-Bedingung erfüllt auch automatisch balanciert ist??? Was bedeutet balancier?

der Vektor soll dynamisch implementiert werden. Die Klasse als Template zu implementieren ist gut gedacht. Denn ich möchte auch verschiedene Objekte in ein Heap speichern, der sogar zwei Elemente in einem Knoten speichern kann, wie z.B. Heap <Autos> mit den Datenelementen "Sting name" und "int ID". template<class T, int n>. n steht für die Größe des Heaps, die dynamisch vom Benutzer eingegeben werden kann.

Da es sich um Objkete handelt müssen wir natürlich einen Kopierkonstruktor definieren und den Zuweisungsoperator überladen. Der Baum wird immer wieder nach dem Einfügen oder Löschen sortiert.

Einfügen: immer am weitesten links unten, dann bubble up, vorher wird verglichen, ob das Objekt im Vektor schon vorhanden ist. Es wird eine Exception ausgeworfen, sonst eingefügt.

Löschen: da braucht man die Methode deleteMin(). Es wird der kleinste Atom gelöscht--> die Wurzel. zuvor wird zum letzten Knoten gewandert und der letzte Knoten in die Wurzel kopiert, dann bubbleDown. Damit der Baum wieder sortiert wird. Die ANzahl der Knoten verringert sich um ein.

Also es gibt keine Lücken

Um den Heap ein- und auszulesen werden die beaknnten fstream Klassen verwendet. Das ist jetzt nicht wichtig für mich

PS: ich würde so gerne hier eine Grafik vom Baum einfügen, ist es möglich? Um das bildlich zu vernaschaulichen.

Liebe Grüße,

Soleil