Diskussion:Binärbaum

Meines (begrenzten) Wissens nach zeigt die Grafik einen nicht vollen, aber vollständigen Binärbaumbaum. Möchte es aber nicht selbst korrigieren, da ich das noch nie auf Wikipedia gemacht hab.

Höhe eines Trees

Ich kenen die Definition der Höhe eines binären Baums ein bisschen anders ... leerer Baum: Höhe -1 Wurzel und sonst nix: Höhe 0 usw. d.h., die Höhe ist definiert als die maximale "Tiefe", gezählt ohne der Wurzel. Somit sind natürlich die Formeln alle falsch ...!!! Höhe 5 bedeutet nämlich 2^(5+1) - 1 Knoten = 63 und nicht 2^5 - 1 Knoten = 31. Also ist leider der Artikel hier falsch. (nicht signierter Beitrag von SternBogen (Diskussion | Beiträge) 12:18, 9. Jun. 2010 (CEST))

• Also bei uns im Studium hat der leere Baum die Höhe 0.. Quellen?

--178.24.115.93 00:40, 5. Jan. 2011 (CET)

Out-Tree etc.

Wow, mal langsam: Ein Binärbaum soll ein Out-Tree sein? Ein gerichteter Graph also? Doch wohl eher nicht! Vielmehr basiert die Definition doch auf einem ungerichteten Graphen (und kann bei Bedarf für Indexstrukturen in Datenbanken etc. auch gerichtet definiert werden). --Thetawave 15:48, 4. Aug 2005 (CEST)

der baum ist weder voll noch vollständig!!!!!!!! falsche definitionen!!

2^(n-1) innere Knoten?

Macht irgendwie keinen Sinn, Beispiel vollständiger Binärbaum mit n=3 Leveln:

2^3 = 8 Blätter: korrekt 2^(3-1) = 4 innere Knoten: Unsinn, hat 7 innere Knoten, also 2^0 + 2^1 + 2^3 Knoten...

Wie erstellt man einen balancierter Binärbaum?

Das würde mich mal sehr interessieren. Wie man einen B-Tree linearisiert ist hier ja aufgeführt. Ich könnte natürlich auch danach googlen, was ich jetzt auch machen werden, aber meine erste Anlafustelle für solche Infos ist mittlerweile nunmal Wikipedia.

Danke und Gruss Fabian

• guckst du mal bei AVL-Baum Gruß--Falk 17:35, 4. Mai 2006 (CEST)

Was soll eigentlch das hier?

"Es gibt einen Algorithmus, der entscheidet, ob zwei gegebene Permutationen einer Menge von Knoten pre- und post-order eines Binärbaums sind. Mit seiner Hilfe kann der zugehörige Binärbaum ggf. auch konstruiert werden."

Das hatte mich schon am Arikel Linearisierung von Binärbäumen gestört. Also wenn da jemand einen Algorithmus kennt, sollte der noch hinzugefügt werden, ansonsten ist mit der Information eigentlich niemandem geholfen. Aus dem Stehgreif fiele mir jetzt nur eine Möglichkeit ein, eine Inorder-Traverse zu erkennen. Indem man sich die Liste oder Folge temporär merkt, sie sortiert und mit der temporär gemerkten vergleicht. Sind sie gleich, so ist es eine Inorder-Traverse und man kann sie dann auch leicht wieder EINEN(nicht unbedingt den ursprünglichen) korrekten Suchbaum erstellen (sofern es sich überhaupt um einen Suchbaum gehandelt hat, ansonsten wäre es aus meiner Sicht garnicht möglich irgendetwas zu erkennen und zu rekonstruieren).

Für die Erkennung und "Rekonstruktion" von Post- und Präorder fällt mir jetzt aus dem Stehgreif nichts sinnvolles ein.

Hier mal die Variante für Inorder:

Funktion ReconstInorder(Liste)
	Baum <- NULL
	If Liste.notEmpty AND Liste = Sort(Liste)
		temp <- Liste.First
		While temp.Next <> NIL
			Baum.Insert(temp)
			temp <- temp.Next
	Return Baum

Ist die übergebene Liste leer oder handelt es sich um keine korrekte Inorder-Traverse eines Suchbaums, so wird NULL zurückgegeben. Ansonten wird irgendein(!!!) Suchbaum zurückgegeben, der - würde man ihn mit Inorder linearisieren - wieder genau die selbe Liste ergeben würde.

Aber umso mehr ich drüber nachdenke, umso trivialer erscheint mir das ;) Gruß--Falk 21:24, 11. Mai 2006 (CEST)

• Achso: Mir fällt da gerade ein wo die Rekonstruktion einer Linearisierung eines Baums Sinn macht und möglich ist: Nämlich beim Level-Order eies möglichst vollständigen binären Baumes (findet Anwendung bei der speicherung von Heaps in Feldern. Dabei sind die Kindknoten des i-ten Elementes im Feld das (i*2)-te und das (i*2+1)-te Element. und der Vater des i-ten Elementes ist das i/2-te Element (wobei i/2 abzurunden ist, sofern es nicht ganzzahlig ist). Allerdings funktioniert das auch wieder nur, wenn das Level-Order die Linearisierung eines Heaps oder eines vollständigen binären Suchbaums ist. Gruß--Falk 22:15, 11. Mai 2006 (CEST)
  • Ich lösch den Part jetzt einfach, weils keine Quellen gibt und weils meiner Meinung nach so nicht stimmt Gruß--Falk 22:45, 22. Mai 2006 (CEST)
    • Ich nehme mal eben alles zurück und behaupte das Gegenteil. Es ist zumindest möglich die Prä- und Postorder Linearisierungen eines Suchbaums wieder zu rekonstruieren. Ich schau mal, ob ich da nen paar schöne Pseudocodes dazu schreiben kann. Gruß--Falk 19:29, 19. Jun 2006 (CEST)

Sollte auch eigentlich die Möglichkeit bestehen einen Algorithmus zu schreiben, welcher aus Inorder und Preorder Listen einen kompletten (nicht vollständigen) Binärbaum rekonstruiert.--Mezzo 14:31, 26. Mai 2008 (CEST)

Code-Beispiele preoder etc. schlecht lesbar

Für mich sind die Codebeispiele etwas schwer verständlich, vorallem der Pseudocode (oder ist das ne reale Sprache). Ich fänds besser wenn die in z.B. C implementiert wären. 134.106.11.158 16:28, 29. Jun 2006 (CEST)

• Nee, das ist schon ein Pseudocode. Gibt es da irgend eine Stelle im Code, die Dir da besonders zu schaffen macht, bzw. etwas zu "highlevel" ist, dann könnte ich da sicher noch ein bischen konkreter werden, oder sind da vielleicht irgendwelche Operatoren wie "<>"(ungleich) oder "<-"(zuweisung) usw. das Problem? Oder verstehst Du da so gut wie garnichts in dem Code? Ich könnte eine Java-Implementierung schreiben, mein C ist zur Zeit etwas eingerostet, aber die Syntax ist ja sehr ähnlich (allerdings müsste man da auch wieder das allgemeine Konzept von Java verstanden haben). Ansonsten kannst Du Dich auch mal auf meiner [Diskussionsseite] melden und dann erklär ich es Dir. Dabei kommen dann vielleicht auch allgemein verständlichere Codes herraus. --Falk 14:27, 1. Jul 2006 (CEST)

• Werter Nutzer mit der IP 134.106.11.158 würdest Du Dich bitte nochmal äußern, wo bei den Pseudocodes jetzt genau das Verständnisproblem liegt? Es ist ja nicht so, dass das mit Absicht unverständlich geschrieben wurde, also werde bitte etwas präziser bezüglich des Problems, ansonsten wird es auch keine Verbesserung geben! Das mit der C- bzw. Java-Implementierung kann noch ein bischen dauern, da ich im Moment nicht wirklich viel Zeit hab und der Artikel nicht stark genug frequentiert ist, dass zu erwarten wäre, dass sich ein anderer Wikipedianer dem in nächster Zeit annimmt. Mfg--Falk 23:59, 5. Jul 2006 (CEST)

Die Beispiele unter en:Tree_traversal sind wesentlich verständlicher. Dort wird auch klar, woher der Name kommt. Die Beispiele in unserem Artikel sind irgendwie wirr. Denke, die meisten verstehen nicht, was mit der Verkettung als Rückgabe gemeint ist. --StYxXx ⊗ 05:32, 25. Jan. 2009 (CET)

Was heißt “wirr”? Der einzige Unterschied ist halt, dass die Linearisierung zurückgegeben und nicht direkt ausgegeben wird. Das Prinzip der Verkettung sollte eigentlich über String-Verkettungen oder z. B. ((List)foo).add(bar) aus den gängigen Programmiersprachen bekannt sein. Aber von mir aus kann man’s auch über die direkte Ausgabe machen. --Falk _{Sprich^zumir…} 00:41, 29. Mai 2009 (CEST)

So, hab’s mal ohne die Verkettung formuliert …--Falk _{Sprich^zumir …} 22:35, 29. Mai 2009 (CEST)

Sperrung

Ich habe die Seite nunmehr gesperrt, ohne jedes Wissen in der Sache, jedoch bedenkend, das alle anderen Edits des Einstellers wegen Begriffsbildung gelöscht wurden. --Gerbil 10:38, 16. Jan. 2007 (CET)

Bitte mach Dich kundig!

Die Darstellung der reellen Zahlen des Intervalls [0, 1] (s.u.) durch einen unendlichen binären Baum ist keine neue Begriffsbildung sondern eine bekannte Anwendung und ein legitimes Anwendungsbeispiel.

Der gesperrte Artikel ist übrigens fehlerhaft. In den Exponenten gehört nur das n gesperrt gedruckt, nicht die Zeichen und Zahlen. Soll das nun für alle Zeiten so gesperrt stehen bleiben, weil der ganze Artikel gesperrt ist?

Ne,ne Du sollst Quellen nennen siehe WP:QA da muß sich niemand kundig machen. --Mathemaduenn 19:06, 16. Jan. 2007 (CET)

Sollte wirklich jemand die Binärdarstellung reeller Zahlen im binären Baum anzweifeln? Google nach "binary tree" in Verbindung mit "real " und "number". 487000 Ergebnisse, z.B. http://theory.csail.mit.edu/classes/6.897/spring03/scribe_notes/L13/lecture13.pdf (The idea is to encode each string as a unique real number in [0; 1].)

WM 17. Jan 2007

Es gibt sicher sehr viele denen der "unendliche binäre Baum" nichts sagt. Dann mußt Du eben Quellen liefern. Wenn ich sage das Jacobi Davidson Verfahren konvergiert quadratisch sollte ich vllt. auch eine Quelle liefern. Ansonsten hat sich dein Abschnitt imho wenig in den Artikel eingefügt. Ebene - Höhe, Pfade - Blätter, muß dein Baum nicht vollständig sein um eine Aussage über die Anzahl der Pfade zu machen? Die Ergänzung bzgl. transfiniter(naiver?) Mengenlehre verkomplizieren den Artikel imho nur ohne wirklichen Informationsgewinn zu bieten Grüße --Mathemaduenn 15:21, 18. Jan. 2007 (CET)

Darstellung der reellen Zahlen des Intervalls [0, 1]

Der unendliche binäre Baum dient zur Binärdarstellung aller reellen Zahlen aus dem Intervall [0, 1] in Form von Pfaden (Knotenfolgen).

Ein endlicher binärer Baum mit n Ebenen besitzt weniger Pfade als Knoten. Bis zur Ebene n > 0 gibt es 2ⁿ Pfade und 2ⁿ⁺¹ - 1 Knoten.

Die Vereinigung aller endlichen binären Bäume ist bezüglich aller Knoten identisch mit dem unendlichen binären Baum. Nach Aussage der transfiniten Mengenlehre besitzt der unendliche binäre Baum jedoch mehr Pfade als Knoten, also mehr Pfade als die Vereinigung aller endlichen binären Bäume.

WM, 16. Jan. 2007

Traversierung?

Hallo allerseits, ich wundere mich, dass im ganzen Artikel das Wort "Traversierung" nicht vorkommt, das in der Informatik doch des öfteren verwendet wird.

Beide Begriffe werden jetzt erläutert. --Der Ersteller Diskussion 09:49, 23. Feb. 2007 (CET)

Hast recht. Ich meine eigentlich, dass das sogar mal so drinn stand, kann mich aber auch irren.--Falk 00:31, 28. Feb. 2007 (CET)

Linearisierung

Ist es nicht so daß zwei beliebige aber verschiedene Linearisierungen eines Baumes, diesen eindeutig beschreiben? Wenn Ja könnte das ja mal jemand einbauen.

Wenn ich so darüber nachdenke, könntest du recht haben. Allerdings wäre eine Quelle, oder ein Beweis von Nöten --Falk 00:19, 2. Apr. 2007 (CEST)

stimmt nicht.. die bäume (L:B;W:A;R:C) und (L:(L:C;W:B);A) haben die selbe pre und postorder.. man brauch pre/post und inorder

Doch das geht bei uns in der Vorlesung kam der Satz: "Ist von einem (unbekannte) Binärbaum mit eindeutigen Werten sowohl die Inorder-Linearisierung als auch entweder die Preorder- oder die Postorder-Linearisierung gegeben, dann ist der Baum eindeutig bestimmt." (nicht signierter Beitrag von 91.59.145.114 (Diskussion | Beiträge) 16:39, 8. Mai 2010 (CEST))

Höchstens zwei Kinder oder genau zwei Kinder?

"Genauer gesagt handelt es sich um einen gewurzelten Baum, bei dem jeder Knoten höchstens zwei Kindknoten besitzt." -> Ein Knoten kann 0, 1 oder 2 Kinder haben.

"Ein Binärbaum ist entweder leer, oder er besteht aus einer Wurzel mit einem linken und rechten Teilbaum, die wiederum Binärbäume sind." -> Jeder Knoten muss entweder 0 oder genau zwei Kinder haben.

Diese Definitionen widersprechen sich. Falk 12:50, 10. Dez. 2007 (CET)

Aus der englischen Version des Artikels geht hervor, dass die erstere Definition richtig ist. Ich habe die zweite dementsprechend erweitert. Falk 18:51, 11. Dez. 2007 (CET)

Auch wenn es schon länger her ist: An sich sind beide Definitionen äquivalent: Hat ein Knoten einen linken, aber keinen rechten Kindknoten, dann ist der rechte Teilbaum gleich dem leeren Baum, der nach Def. auch ein Binärbaum ist... 80.141.127.143 23:52, 27. Apr. 2008 (CEST)

Jein. Die Sätze sind nicht ganz äquivalent. Der erste lässt genau genommen offen, weilche Anzahlen an Kindern erlaubt sind. Es wird nur gesagt, dass es höchstens zwei Kinder sein dürfen, nicht aber, ob 0 Kinder, oder 1 Kind erlaubt sind. Daher widerspricht der zweite Satz dem ersten aber auch nicht, sondern konkretisiert ihn lediglich. So wie es da stand, war es also vollkommen richtig. Man möge es gerne probieren, aber mit dem zweiten Satz ist jede erdenkliche Konstruktion eines Binärbaumes möglich (mit dem ersten Satz auch, sofern man alles erlaubt, was dort nicht verboten wurde). Ich bin also dafür dass das wieder so hergestellt wird, wie es war. Jemand anderer Meinung?--(auch wenn die Unterschriften identisch aussehen, ich bin ein anderer Falk, als mein Vorvorredner ;))Falk 01:20, 28. Apr. 2008 (CEST)

Da scheinbar keiner anderer Meinung ist, stelle ich den Satz jetzt wieder so her. --Falk 15:11, 29. Apr. 2008 (CEST)

Strukturelle und nicht Vollständige Induktion

Meiner Meinung nach lassen sich die genannten Eigenschaften des Baums nicht durch vollständige Induktion, sondern nur durch strukturelle Induktion zeigen, weil in den Beweise die rekursive Definition des Binärbaums und eben nicht die rekursive Definition der natürlichen Zahlen einfließt. Deswegen sollte der Verweis hinter "Induktiv" auf Strukturelle Induktion zeigen. --Dr.Kemmer 16:20, 11. Dez. 2007 (CET)

Da kein Kommentar dazu kam, jetzt auf Strukturelle Induktion geändert.

ausgabe in level order und niveau, artikel nicht komplett

guten tag community!

es fehlt noch in der erklärung die ausgabe im level order und wie man die knoten eines niveaus ausgibt: z.B.:

       A
    /     \ 
   B       C
 /   \       \
D     E       G

dann wäre niveau 3: D E G und level order: A B C D E G (womöglich auch hintereinander!)

=D

Stimmt, das fehlt noch. Allerdings fällt mir da jetzt aus dem Stehgreif keine wirklich schöne Lösung ein. Wer eine schöne Lösung kennt, möge sie aufschreiben --Falk 12:38, 6. Mai 2008 (CEST)

Lösung für Levelorder und Ausgabe per Niveau

Hi Community:

ich habe an einer Lösung gearbeitet (funktionierend!) und werde diese demnächst posten, sofern kein anderer schneller ist als ich.

hier mal ein code-snippet vom baum:

wenn jemand lust hat, kann er das noch in dem wiki eintrag hinzufügen ;P

template <class typ>
void bintree<typ>::levelorder(treenode<typ> *pnode)
{
	clock_t end, start;
	double dif;

	 queue<treenode<typ>*> qnode;
	int i=0;

	qnode.push(pnode);
	start = clock();

	while (!qnode.empty())
	{	
		i++;
		treenode<typ> *pnode = qnode.front(); qnode.pop();
		cout << pnode->data << " ";
		if (pnode->left != nullnode)
			qnode.push(pnode->left);
		if (pnode->right != nullnode)
			qnode.push(pnode->right);
	}
	end = clock();
	dif = ((float)(end-start)/CLOCKS_PER_SEC);
	cout << "\n" << setprecision(3) << dif << " Sekunden\n";

	return;
}

(Der vorstehende, nicht signierte Beitrag stammt von 92.227.18.125 (Diskussion • Beiträge) 19:29, 15. Mai 2008)

Bitte schließe Quelltext immer mit <syntaxhighlight lang=NameDerSprache> </syntaxhighlight> ein, ansonsten ist das kaum lesbar ;). Aso und Diskussionsbeiträge bitte immer mit ~~~~ am Ende signieren (auch wenn Du nicht angemeldet bist). Ich hab' das mal beides für Dich erledigt.

Schön, dass Du eine Lösung gefunden hast. Und Danke, dass Du Dir die Arbeit gemacht hast. :)

Zu Deinem Code: Ich hab's jetzt nicht getestet und glaube Dir einfach mal, dass es läuft. Aber bitte reduziere solche Sachen auf das Wesentliche, also möglichst ein Minimalbesipiel − so Sachen wie Zeitmessungen sind da eher weg zu lassen. Und schön wäre das ganze auch als Pseudocode − man kann ja nun nicht unbedingt voraussetzen, dass jeder jede Sprache beherrscht. Konkrete Implementierungen sind natürlich trotzdem erwünscht.

Beste Grüße

Falk 23:02, 15. Mai 2008 (CEST)

Traversierung, Beispiele

Hallo, kann vllt. jemand ein knappes Beispiel (am besten mit Bild) bringen, wo er mal alle 3 Reihenfolgen darstellt? Ich habe was ähnliches in en.wiki gefunden. Wäre echt nett. Danke --WissensDürster 19:51, 24. Jan. 2009 (CET)

Definition "geordneter Binärbaum"

Folgender Satz stellt mich vor ein Rätsel: "Ein Binärbaum heißt geordnet, wenn jeder innere Knoten ein linkes und eventuell zusätzlich ein rechtes Kind besitzt (und nicht etwa nur ein rechtes Kind)". Erstens verstehe ich den Sinn des Worts "eventuell" darin nicht, zweitens kenne ich den Begriff "geordnet" nur als Eigenschaft binärer Suchbäume (so sehen es auch diverse Unis --> google) und drittens erkenne ich keinen strukturell sinnvollen Unterschied zur danach folgenden Definition eines "vollen" Binärbaums: "Man bezeichnet ihn als voll, wenn jeder Knoten entweder Blatt ist (also kein Kind besitzt), oder aber zwei (also sowohl ein linkes wie ein rechtes) Kinder besitzt." Vielleicht kann mich ja jemand erleuchten..? -- 84.61.186.11 17:01, 13. Mai 2009 (CEST)

Das heißt für mich: Wenn ein Knoten Kinder hat, so muss er ein linkes haben und kann ein rechtes haben (o. B. d. A., was links und rechts angeht).

Bsp.:

Geordnet:
     A
    / \
   B   D
  /   / \
 C   E   F
    /
   G

Ungeordnet (B hat kein linkes, aber ein rechtes Kind):
     A
    / \
   /   \
  B     D
   \   / \
    C E   F

--Falk _{Sprich^zumir…} 01:45, 29. Mai 2009 (CEST)

Schön und gut, aber welchen Sinn hat das? Wie oben schon gesagt, kenne ich den Begriff "geordnet" nur bezogen auf die Knoteninhalte und kenne keinen Anwendungsfall, in dem solch ein Baum (wie im ersten Beispiel) gefordert ist (Worin liegt der Vorteil ggü. dem zweiten Baum?) -- 84.62.204.229 16:34, 1. Jun. 2009 (CEST)

Mit Deinem “zweitens” hast Du Recht: Der Begriff “geordnet” ist hier wohl ungünstig gewählt – ich finde das auch nur als Synonym zur Suchbaumeigenschaft; ich schaue mal, ob ich da eine bessere Bezeichnung finde. Ein konkreter Anwendungsfall fällt mir gerade auch nicht ein. --Falk _{Sprich^zumir …} 14:06, 2. Jun. 2009 (CEST)

Einfügen und Löschen

Meiner Meinung nach gehören die Abschnitte "Einfügen" und "Löschen" nicht in den Artikel Binärbaum, da sie eine Ordnung der Knoten voraussetzen, in diesem Fall in der Art eines binären Suchbaums. Dahin sollten die Abschnitte wohl auch verschoben werden, was vor der Änderung am 20. Juli 2010 wohl auch der Fall war. -- 92.231.7.10 (14:07, 28. Aug. 2010 (CEST), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

1. Eine Ordnung der Knoten ist auch beim Binärbaum wohl immer irgendwie geartet vorhanden, nicht aber notwendigerweise eine solche, die den binären Suchbaum charakterisiert, nämlich eine Totalordnung.
2. Auch bei einem Binärbaum, dessen Ordnung völlig unspezifiziert ist, muss man auf irgend eine Weise einfügen und löschen können.
3. Es ist schon wahr, dass es fast keine Binärbäume gibt, die keine binären Suchbäume sind.

-- Nomen4Omen 14:52, 8. Sep. 2010 (CEST)

Elementare Definitionen fehlen

Vielleicht gehört dies auch in den allgemeinen Artikel zu Baum (Graphentheorie) - aber hier wie da fehlen die Definitionen für Grad und Tiefe eines Knotens und für Höhe und Grad des Baumes. (nicht signierter Beitrag von 84.60.42.202 (Diskussion) 21:39, 10. Nov. 2010 (CET))

Viele von den angesprochenen Begriffen werden in Glossar Graphentheorie einigermaßen erläutert. Ist das nicht gut genug? -- Nomen4Omen 18:32, 11. Nov. 2010 (CET)

Aufwand bei der rekursiven Traversierung

Danke für die Verbesserung. Jedoch:

Wird die Traversierungs-Funktion ( z.B. postOrder() ) nicht exakt ein mal für jeden Knoten aufgerufen, so wie ja auch das print() genau ein mal kommen soll ? -- Nomen4Omen 18:15, 4. Jan. 2011 (CET)

Indizierung <--> Indexierung

Abschnitt Repräsentation durch ein Array:

"Die Indexierung beginnt bei 1 mit Verweis auf die Wurzel."

Ist hier nicht eher die Indizierung gemeint?

-> Indexierung

-> Indizierung (nicht signierter Beitrag von 92.224.198.0 (Diskussion) 18:14, 8. Jan. 2012 (CET))

Sehe ich auch so. -- Nomen4Omen 10:34, 9. Jan. 2012 (CET)

voll, optimal und balanciert

Unter 'weitere Begriffe' steht:

'Man bezeichnet volle Binärbäume als vollständig, wenn alle Blätter die gleiche Tiefe haben, wobei die Tiefe eines Knotens als die Anzahl der Bögen bis zur Wurzel definiert ist.'

Das passt nicht ganz zu dem Abschnitt über balancierte Bäume:

'Ein vollständig balancierter Binärbaum ist ein voller Binärbaum, bei dem die Abstände zweier beliebiger Blätter von der Wurzel um höchstens 1 voneinander abweichen. Ein vollständiger Binärbaum ist ein vollständig balancierter Binärbaum. (Siehe auch Balancierter Baum oder AVL-Baum.)'

Der Abschnitt würde IMHO mehr Sinn machen, wenn er einfach 'balancierte Bäume' und nicht 'vollständig balancierte Bäume' definieren würde. Oder wie ist das gemeint?

Abgesehen davon, was im Artikel als 'vollständiger' Binärbaum definiert ist, wird woanders auch als 'optimaler' Binärbaum bezeichnet. Auch wird woanders durchaus ein 'vollständiger' Binärbaum 'nur' mit einem maximalen Höhenunterschied von 1 definiert, wobei dann ein Level-Order-Traversal keine 'Lücken' enthalten darf (wie bei einem binären Heap). --Gms 23:43, 10. Feb. 2012 (CET)