optimaler linksorientierter binärer Baum mit Heap-Bedingung



  • 😕 Ein Hallo an alle.

    Also ich habe ein Problem mit dem Programm anzufangen. Wie soll ich diesen Heap schreiben, damit ich ein optimaler, linksorientierter binärer Baum darstellen kann. Welche Klassen brauche ich und wie sind diese Klassen strukturiert?Ich denke ich brauche auf jeden Fall eine Klasse "Heap", in der der Heap vektoriell implementiert wird + dessen Grösse(dynamisch), die Klasse "Cell" mit den Datenelementen(Zeiger auf Kindknoten) Left und Right und die Klasse Node, um die einzelnene Knoten darzustellen, durch key und das Atom(Inhalt). In diesen Heap sollen zwei Datentypen eingefügt werden. String und int. Hat jemand eine Idee, wie ich anfangen soll? Natürlich müssen später Schnittstellen programmiert werden, die die Elemente einfügen,löschen,sortieren,... (insert(), sort(),deleteMin(), search() ).

    Wäre euch für jede weiterführende Hilfe dankbar 🙄

    Soleil 🙂



  • Such doch mal im Internet nach "Heap" (Google dürfte da helfen), da findest du einige Hilfen.

    Ansonsten bietet die STL noch die Algorithmen make_heap(), push_heap() etc an, um einen linearen Datenbereich als Heap aufzufassen - die Nachfolger von Knoten i sind 2*i und 2*i+1.



  • Der Standard bietet Funktionen, um innerhalb eines Containers die Elemente als Heap zu sortieren: make_heap(), sort_heap(), push_heap(). Vllt. helfen die enstrechenden Implementierungen weiter. 🙂



  • Danke euch für die Antwort. Das Problem ist, es ist eine Template-Klasse und ich möchte auch wissen, wleche Klassen ich brauche, um diesen binären Baum darzustellen. Wohlgemerkt: ein optimaler, linksorientierter binärer Baum. Ich habe schon im Internet recherchiert, aber es steht nichts Spezielles über Heap für diesen binären Baum 😞

    Soleil



  • Die STL-Algorithmen arbeiten mit jeder beliebigen Containerklasse zusammen - solange diese etwas Iterator-ähnliches mitbringt. (also zur Not auch mit blanken Arrays)



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





  • 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.



  • 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.



  • 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.



  • 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.



  • 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.



  • @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".



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



  • 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 🕶



  • @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/...



  • 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.



  • 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.



  • 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).



  • 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= 2
    i+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


Anmelden zum Antworten