optimaler linksorientierter binärer Baum mit Heap-Bedingung

[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