Diskussion:AVL-Baum

Dieser Artikel war am 8. Februar 2023 der Artikel des Tages.

Traverse? Eher Tarversierung, oder?

Das Wort Traverse ist mir bisher in keinem Buch untergekommen. Hier wird von der in-order-Traverse gesprochen, das sollte aber in-order-Traversierung heißen, oder? Wenn es keinen Einspruch gibt, ändere ich das bald. 92.195.75.42 12:24, 10. Feb. 2011 (CET)

Noch eine Anmerkung: Im Englischen gibt es traverse, aber nur als adjektiv, nicht als Nomen. "Algorithmen in Java" von R. Sedgewick kennt laut Inhaltsverzeichnis auch nur Traversierung, oder eben traverse als Methodenname. 92.195.75.42 12:28, 10. Feb. 2011 (CET)

Im Englischen gibt es freilich "traverse" als Verb, siehe en:tree traversal, und zwar ganz genau in dem Sinn, wie's hier gebraucht wird. Die Engländer nehmen dann noch "Iteration" und "Enumeration" - auch nicht schlecht, nur hat es die Konnotation, dass man immer in der gleichen Richtung geht. Hier wollen wir explizit beide Richtungen erlauben.

Ups, sorry ich meinte auch verb und nicht adjektiv. Hier wird allerdings ein Nomen gebraucht. 92.195.75.42 09:02, 11. Feb. 2011 (CET)

Also im deutschen Wiki findet sich unter Quergang Traverse, was wirklich nicht schlecht passt, denn es wird irgendwie waagrecht geklettert. "Traversierung" ist natürlich auch OK, aber recht umständlich, weil so lang. Wenn man sich mit "Traverse" wirklich nicht anfreunden kann, dann wäre mir das deutsche "Querung" am Ende lieber. -- Nomen4Omen 20:42, 10. Feb. 2011 (CET)

Wie gesagt, ich habe Traverse noch nie in der Uni gehört oder in irgendeinem Buch gelesen, Traversierung ist der richtige Kandidat. Querung wäre ebenfalls völlig neu und würde meiner Meinung nach nicht passen, da es nirgends benutzt wird. Man sollte sich doch der Eindeutigkeit an das Standardvokabular halten. Die Anderen relevanten Datentypen die Traversierung erlauben benutzen hier auf Wikipedia doch auch Traversierung. 92.195.75.42 09:02, 11. Feb. 2011 (CET)

OK, jetzt steht ja überall Traversierung, sehr gut ;) 130.133.49.92 12:12, 16. Feb. 2011 (CET)

Sprache

"...eine etwas sophistischere Suchoperation angebracht...", man kann nicht wörtlich Sätze aus dem Englischen übersetzen. Sprachlich bitte nachbessern. (nicht signierter Beitrag von 95.223.159.24 (Diskussion) 14:52, 30. Dez. 2010 (CET))

Programmcode & Diagramme

Hm, sollte da vielleicht ein bisschen Programmcode und ein paar Diagramme rein? Allerdings könnte ich die höchstens aus der Literatur kopieren, da der AVL-Baum eine vielfach beschriebene Standard-Datenstruktur ist und ich eher keine Lust habe, das Rad neu zu erfinden, nur um Code zu produzieren, der dann erst wieder mit dem in der Literatur identisch ist...

Bei nem AVL-Baum gibt es eigentlich kaum ein "bisschen" :) --mGla 16:53, 9 November 2005 (CET)

Ein paar Literaturhinweise wären vielleicht auch nicht schlecht, obwohl eine einfache Google-Suche schon massig Resultate liefert.

Gibt es da nicht diesen klassiker von Niklaus Wirth? --mGla 16:55, 9. Nov 2005 (CET)

ausgeglichener Baum $\neq$ AVL-Baum

Mich stört der Satz "Ein Binärbaum heißt vollständig ausgeglichen oder AVL-Baum, [...]". Ich meine, ein AVL-Baum wird eher über die Methoden definiert, die einen höhenbalancierten Baum aufbauen, d.h. es gilt AVL-Baum ==> ausgeglichener Baum, aber nicht umgekehrt, es gibt ja noch andere ausgeglichene Bäume. Außerdem ist ein AVL-Baum garantiert kein Binärbaum, weil binärer Baum und Binärbaum auch zwei verschiedene Sachen sind.

Anzahl der Fälle

Also eigentlich sind's ja vier Fälle (zwei symmetrische kommen hinzu).

Vielleicht sollte man auch die genauen Bezeichnungen der Rotationen nennen und wie die jeweils nötige Rotation bei der Implementation erkannt werden kann? (LL-,RR-,LR-,RL-Rotation) --Samx 15:28, 27. Jul 2006 (CEST)

Falsche Definition im Abschnitt Balance?

Dort heißt es:

Ein Binärbaum B ist genau dann ein AVL-Baum, wenn für alle Teilbäume c von B gilt: $\operatorname {bal} (c)\in \{-1,0,1\}$

Ich denke nicht, dass dies korrekt ist; immerhin beschreibt Absatz "Suchen eines Elementes find" das Kriterium von AVL-Bäumen, dass "der Suchbaum jederzeit so sortiert ist, dass rechts eines Knoten nur Knoten mit größeren Schlüsseln, und links vom Knoten nur Knoten mit kleineren (oder gleich großen) Schlüsseln gespeichert sind".

Daher denke ich, es müsste heißen:

Ein binärer Suchbaum B ist genau dann ein AVL-Baum, wenn für alle Teilbäume c von B gilt: $\operatorname {bal} (c)\in \{-1,0,1\}$

--Oleson 07:59, 10. Jul 2006 (CEST)

Ich hab das jetzt geändert, ein AVL-Baum ist immer ein binärer Suchbaum, sonst macht das Ganze auch keinen Sinn. --Samx 14:55, 27. Jul 2006 (CEST)

links und info

Es wird zwar auf drei applets verlinkt (imho reicht eins) aber weder im artikel noch in den verlinkten seiten finden sich genauere überlegeungen zu den baumhöhen in abhängigkeit der elemente. vor allem nicht über das worst-case verhalten der höhe (was z.b. bei iterativen implementationen in einigen programmiersprachen recht wichtig zu wissen ist)

Habe mal ein paar Links aus der englischsprachigen Wikipedia übertragen, damit nicht nur Java Applets präsent sind (wovon auch meiner Meinung nach tatsächlich eins reichen würde). In den Source-Codes sind teilweise extrem reich kommentierte Überlegungen zu den Baumhöhen eingeflossen, aber natürlich von der praktischen Seite her: die theoretische Überlegung ergibt sich ja eigentlich von selbst aus der Definition der AVL Datenstruktur. Gulliveig 08:08, 12. Jan. 2007 (CET)

Maximale Höhe

Die maximale Höhe von 1,4404 * log n kann nicht stimmen, wie die einfache Betrachtung des AVL-Baums mit zwei Knoten zeigt: Die Formel ergibt eine maximale Höhe von 1,4404, während der AVL-Baum mit zwei Knoten eine Höhe von 2 hat. Ich werde die Angabe aus dem Artikel entfernen; wer eine korrigierte Formel kennt, möge sie bitte mit Quellenangabe einfügen. --81.173.148.174 17:55, 23. Apr. 2007 (CEST)

H(n) ≤ 1.44 log(n + 2) − 0.328 haben wir im Studium gelernt. --213.211.224.43 13:50, 11. Mai 2007 (CEST)

Ich weiß nicht, ob die Formel stimmt, aber die Höhe eines AVL-Baums mit zwei Knoten ist nicht 2, sondern 1, und da 1 ≤ log 2 , ist das kein Gegenbeispiel. --Daniel Mex 18:09, 20. Jul. 2007 (CEST)

Ich habe die Schranken mal aus TAOCP abgeschrieben. Für n=2 ergibt sich demnach eine obere Schranke von 2,5533. Der ausschlaggebende Punkt war vermutlich das Argument n+2 des Logarithmus. Von der Größenordnung her hat's jedenfalls gepasst ;) -- octo 23:51, 15. Apr. 2009 (CEST)

Fehler bei der Beschreibung von Insert?

"Der rekursive Rücksprung kann beendet werden, wenn die Balance eines Knotens zu 0, −1 oder 1 wird." Das verstehe ich nicht ganz... Es muss doch lauten: wenn die Balance eines Knotens zu 0 wird. Wenn die Balance zu -1 bzw 1 wird, wird wahrscheinlich der Vater vom Knoten den Wert -2 bzw +2 besitzen und da muss man ja "reparieren" und danach kann man die Rekursion abbrechen... --Sarteto 19:42, 6. Mai 2009 (CEST) EDIT1: Gleich der nächste Satz sagt dieses indirekt aus: "Wird der Balance Faktor zu 0 [...]" Ich finde es muss aber betont werden, dass dann der Rekursionsabbruch kommt... --Sarteto 19:45, 6. Mai 2009 (CEST)

Korrekturen am 28.04.2010:

Generell: Einheitlich "Höhe" und nicht auch gelegentlich "Tiefe"

1) Balance: Ungenaue Zahlenangabe

2) Suchen eines Elements find:

2a) Andeutung anderer Navigationsmöglichkeiten als nur find

2b) Zwar "links mit kleineren (oder gleich großen) Schlüsseln", und rechts keine gleich Großen, klappt nicht.

2c) Erwähnung der Vergleichsfunktion mit Verweis auf wiki Totalordnung

2d) Einführung des Begriffs (Halb-)Blatt korrekterweise erforderlich.

2e) Möglichkeit expliziterer Duplikatkontrolle wenigstens erwähnt.

2f) Komplexität im avg + worst case

3) Einfügen eines Elements insert:

3a) Korrektur der Balance-Faktoren, die zur "Rekursion" führen.

3b) Diskussion des Stops nach Rebalancierung sofort.

3c) Erwähnung der im avg konstanten Komplexität.

4) Entfernen eines Elements remove:

4a) Diskussion der Eskalationen nach Rebalancierung sofort.

4b) Erwähnung der im avg konstanten Komplexität.

5) Implementierung: Bemerkung zu Rekursionen

-- Nomen4Omen 15:55, 28. Apr. 2010 (CEST)

Kommentar

ACHTUNG: der Fall "gleich hoch" existiert nicht, denn gleich hoch impliziert, dass beide rechten Teilbäume zwei größer sind als die linken Teilbäume -- Widerspruch, da nur ein Element eingefügt wurde! Ebenso illustriert die Grafik diesen unmöglichen Fall fälschlicherweise --2010-07-21T02:22:08 89.247.147.44

Kommentar

Richtig gesehen: "gleich hoch" existiert beim Einfügen nicht. Aber beim Entfernen, wie auch im Text ausgeführt.

Änderungen bis 2010-07-22:

1) InfoBox mit 4. Spalte "gesamt" für Massen-Operationen

2) "Suchen mit Duplikaten" mit Verweis

3) "Suchen per Index" rüber zu binärer Suchbaum.

4) Proximitäts-Suche (statt GrößerGleichKleiner-Suche).

5) Bulk-Insert und -Delete mit Begründung in "Implementierung".

6) Klassisches Speichermanagement als Anwendungsbeispiel.

-- Nomen4Omen 16:10, 22. Jul. 2010 (CEST)

Suche mit Duplikaten

Hallo, ich verstehe irgendwie folgenden Satz nicht: "...Eine solche Suchoperation erlaubt z. B., eine (möglicherweise unbekannte) Vorsortierung im Régime von Duplikaten über eine Neusortierung hinweg zu retten...". Kann dafür jemand ein Beispiel geben? --Sinuhe20 19:34, 23. Jan. 2011 (CET)

Lieber Sinuhe20, die Formulierung stammt von mir - und es ist natürlich nicht so gut, dass man sie nicht versteht. Aber es ist an eine Situation gedacht, wo ich mehrere Attribute (Spalten od.ä.), z.B. SpalteA und SpalteB, habe, nach denen u.U. gesucht wird. Nehmen wir an, dass es einen Suchbaum gibt, der es gestattet, nach einem Schlüssel, der in die SpalteA gehört, zu suchen. Etwas später erfordert es die Anwendung oder der Anwender, dass nach SpalteB sortiert werden soll. Ich nehme an, wir haben Werte:

SpalteA|SpalteB

101201 |bar

101203 |Futter

101203 |Miete

101207 |bar

Dann ist es doch auf jeden Fall besser, wenn ich die Vorsortierung nach SpalteA nicht unnötigerweise kaputt mache. Das Ergebnis soll also sein:

101201 |bar

101207 |bar

101203 |Futter

101203 |Miete

und auf keinen Fall:

101207 |bar

101201 |bar

101203 |Futter

101203 |Miete

(es sei denn dies wäre ausdrücklich so gewollt). Im Beispiel haben wir Duplikate bei "bar" - und die sollen nicht irgendwie beliebig hinter einander gebracht werden, sondern wie vorher gezielt aufsteigend oder, wenn's dem Anwender lieber ist, auch absteigend.

Das ist auch, was man mit einem "stabilen" Sortierverfahren meint. -- Nomen4Omen 22:48, 23. Jan. 2011 (CET)

Danke, jetzt ist es schon verständlicher. In dem Text sollte erwähnt werden, dass von einer Neusortierung in einer anderen Spalte (und in einem anderen AVL-Baum?) die Rede ist...--Sinuhe20 23:07, 23. Jan. 2011 (CET)

Traversierung in O(1)?

Hallo zusammen,

ich habe gerade gelesen, dass die Traversierung eines AVL-Baumes laut der Tabelle in O(1) liegen soll. Bedeutet Traversierung nicht, dass man den Graphen abläuft und sich jeden Knoten anschaut? Muss das nicht mindestens in O(n) liegen, da alle n Knoten angeschaut werden müssen? --Martin Thoma 18:21, 10. Jun. 2012 (CEST)

Ja, das kann man so verstehen. Gemeint ist aber der einzelne Querungs-Schritt. Ich bessere das nach. --Nomen4Omen (Diskussion) 21:08, 10. Jun. 2012 (CEST)

Anwendung?

Für was ist ein AVL-Baum eigentlich nützlich? --Oli92 (Diskussion) 21:15, 12. Aug. 2013 (CEST)

Vllt ist die Nützlichkeit in Binärer Suchbaum ganz gut erklärt. --Nomen4Omen (Diskussion) 14:49, 13. Aug. 2013 (CEST)

Review vom 03. Dezember 2013 bis 15. Januar 2014

Der AVL-Baum ist eine Datenstruktur in der Informatik, und zwar ein balancierter binärer Suchbaum, bei dem sich die Höhe der beiden Teilbäume an jedem Knoten höchstens um 1 unterscheidet.

AVL-Bäume gehören zu den ersten Datenstrukturen und Algorithmen, die an der Hochschule behandelt werden, die aber auch schon an der Schule im Leistungskurs behandelt werden können. Ich habe darauf geachtet, dass möglichst alle einschlägigen Funktionen besprochen werden.

Algorithmen und Beweise sind alle einfach, alle belegt mit Referenzen bis auf "Verketten", "Spalten" und "AVL-Baum impliziert Rot-Schwarz-Baum". Obwohl auch diese (hoffentlich!) sofort verständlich sind, wäre es fein, wenn sich Referenzen dazu auftreiben ließen. Andererseits wäre es m.E. auch wieder nicht schlimm, wenn die erst später gefunden würden.

Mit deshalb sind die Fußnoten aufgeteilt in group="Ref" für die Einzelnachweise und group="Anm" für die Anmerkungen, die eben diese Beweise, aber auch andere erläuternde oder weiterführende Informationen enthalten. Man kann aber auch alles in einen großen Haufen geben.

Natürlich hätte ich gerne von der Community die Bestätigung, dass die Darstellung des Themas in die richtige Richtung geht. Dann würde ich auch den Artikel Rot-Schwarz-Baum, der zwar den Adel "Lesenswert" schon hat, bei dem ich aber manches nicht verstehe, genauer mal ansehen.

--Nomen4Omen (Diskussion) 16:07, 3. Dez. 2013 (CET)

Der Artikel fängt etwas abrupt an, mit "Balance". Vielleicht sollte man erst mal erklären, wozu Suchbäume verwendet werden. Dann nochmal die Höhe erklären und dann noch ein paar Beispiele geben, auch welche, die nicht balanciert sind und welchen Effekt dies auf die Suche hat.--Jocme (Diskussion) 17:12, 6. Dez. 2013 (CET)

Bezgl. der Balance habe ich eine neue Version gemacht. Bei den linearen Listen sind dann auch Beispiele für Entartungen.

Bezgl. Suchbaum und Höhe meine ich, dass es zumutbar ist, dem Link zu folgen, wo alles schön erklärt ist. (Das ist doch gerade der große Vorteil einer Enzyklopädie am PC.) --Nomen4Omen (Diskussion) 21:49, 6. Dez. 2013 (CET)

Du hast natürlich recht, die Verweise unter balancierter und binärer Suchbaum sind allerdings etwas versteckt. Besser wäre es, wenn es einen Artikel Balancierter Suchbaum gäbe. Um den Verweis deutlicher zu machen wäre evtl. doch eine Einleitung sinnvoll mit Verweis auf die entsprechenden Hauptartikel (Ausgeglichener Baum und Suchbaum).--Jocme (Diskussion) 12:17, 11. Dez. 2013 (CET)

Der Abschnitt AVL-Baum#Balance hat jetzt den Inhalt, der die Balance-Problematik beschreibt. Der frühere Abschnitt "Balance" heißt jetzt AVL-Baum#Definition, was vllt sowieso besser ist, da immer eine Definition da sein soll. --Nomen4Omen (Diskussion) 17:45, 18. Dez. 2013 (CET)

Ich finde die Änderung gut, jetzt wird zunächst erzählt was die Zielsetzung der Datenstruktur ist. Ich vermute aber, der Abschnitt Balance ist noch etwas schwer verständlich.--Jocme (Diskussion) 15:41, 28. Dez. 2013 (CET)

Ich habe den Abschnitt noch einmal umformuliert. --Nomen4Omen (Diskussion) 17:40, 9. Jan. 2014 (CET)

Die Mathematische Formeln sehen bei mir im Browser unschön aus. Man könnte sie auch vermeiden, indem man den Sachverhalt im Text schildert.--Jocme (Diskussion) 17:12, 6. Dez. 2013 (CET)

Unschöne Formeln sind natürlich unschön. Vielleicht kriegen wir mal eine Software, bei der alle Formeln in jedem Browser schön aussehen. --Nomen4Omen (Diskussion) 21:49, 6. Dez. 2013 (CET)

Die Formeln zum Balance-Wert scheinen mir halt hier überflüssig zu sein. Was kompliziert mit Formeln ausgedrückt wird, steht doch schon in der Einleitung im ersten Satz. Ich verstehe den Mehrwert hier nicht.--Jocme (Diskussion) 12:17, 11. Dez. 2013 (CET)

Ich habe viele <>math>-mathematische Formeln durch HTML ersetzt. Hoffentlich stimmt's nachher auch. --Nomen4Omen (Diskussion) 17:45, 18. Dez. 2013 (CET)

@Jocme zur Änderung des Artikels: Das mit dem Abschnitt "Quellen" ist eine Idee, der man anhängen kann.

Die Anmerkungen in der group="Anm" sind gedacht für einen Leser, der mehr und gründlicher wissen will, was los ist. Sie stellen also eine vom Autor vorgedachte Abstufung dar, die den nicht zu interessieren brauchen, der nur die knackigen "facts" wissen will. Vielleicht wären sie besser aufgehoben in einem Einschub, den man aufklappen kann. Aber erstens gefällt das Konstrukt wichtigen Leuten auch nicht und zweitens stören sie den Fließtext erheblich mehr, ohne dass man sofort sieht, was man da aufklappt.

@Jocme: Insofern bin ich gegen die Umodnung nach ganz hinten. Sie gehören näher zum Körper des Artikels als die Quellen. Trotzdem lass ich das erstmal so. --Nomen4Omen (Diskussion) 21:49, 6. Dez. 2013 (CET)

Du hast Dir viel Mühe gegeben, aber ich weiss nicht ob das mit den Anmerkungen wirklich so sinnvoll ist. Kaum einer wird das Kleingedruckte studieren wollen. Ich würde versuchen einen Teil in den Text einzuarbeiten, zumindest bei den ersten 4 Punkten geht das doch gut, ohne den Text aufzublähen.--Jocme (Diskussion) 12:17, 11. Dez. 2013 (CET)

Ich habe einige Anmerkungen in den Fließtext eingearbeitet. Andererseits: gerade wenn einer das Kleingedruckte nicht studieren will, ist ihm mit den "Anmerkungen" doch eine Überholspur angeboten. Und einer, der wirklich punktuell mehr wissen will – zugegeben, das dürften nicht sehr viele sein – der würde vllt auch auf seine Kosten kommen. In den Abstract habe ich mal ein bisschen Gebrauchsanweisung rein. --Nomen4Omen (Diskussion) 17:45, 18. Dez. 2013 (CET)

An der jetzigen Version (AVL-Baum vom 6. Dez. 2013) gefällt mir an der Einleitung nicht so recht, dass schon so früh im Text die Entartung einscheint. Deshalb ein neuer Vorschlag, der der Balance und Entartungsgefahr der Binärbäume einen frühen Extra-Abschnitt widmet (obwohl das in Balancierter Baum noch ausführlicher gesagt ist).

Gleichzeitig ist der Vorschlag des Abschnitts "Quellen" von Jocme eingearbeitet. Die Anmerkungen sind dabei vor die "Einzelnachweise" platziert. --Nomen4Omen (Diskussion) 18:55, 8. Dez. 2013 (CET)

KALP-Kandidatur 15.1. bis 5.2.14 (Ergebnis: Lesenswert)

Der AVL-Baum ist eine Datenstruktur in der Informatik, und zwar ein balancierter binärer Suchbaum, bei dem sich die Höhe der beiden Teilbäume an jedem Knoten höchstens um 1 unterscheidet.

Der Artikel war vom 03. Dezember 2013 bis 15. Januar 2014 im WP:Review/Naturwissenschaft_und_Technik. Für die dort eingegangen Tipps und auch die Korrekturen am Artikel selbst möchte ich mich herzlich bedanken. Nachdem einige Tage keine neuen Tipps oder Vorschläge mehr eingegangen sind, können die ja immer noch kommen, und zwar dann halt hier und jetzt.

Bemerkungen:

• AVL-Bäume gehören zu den ersten Datenstrukturen und Algorithmen, die an der Hochschule behandelt werden. Sie können aber auch schon an der Schule im Leistungskurs drangenommen werden.

• Es gibt im Netz viele Implementierungen.

• Im Artikel wurde darauf geachtet, dass möglichst alle einschlägigen Funktionen besprochen werden. Es sind wohl mehr, als in einem einzelnen Buch zu finden sind. Algorithmen und Beweise sind alle einfach. Sie sind, sofern sie als länglich oder etwas speziell angesehen wurden, in den Fußnoten mit der Kennung group="Anm" untergebracht.

Natürlich hätte ich gerne von der Community die Bestätigung, dass die Darstellung des Themas in die richtige Richtung geht. --Nomen4Omen (Diskussion) 16:45, 15. Jan. 2014 (CET)

Sieht toll aus, aber die Regelungen und Gebräuche der Wikipedia sollten beachtet werden. Das betrifft Formalitäten, nicht den Inhalt. Ausgezeichnete Artikel sollen als Vorbilder für künftige Artikel gelten können. Bspe.: die Personennamen in der Einleitung sollten ganz normal verlinkt sein. Die Gliederung (Anmerkungen, Einzelnachweise, Literatur, Weblinks) ist eigenwillig und kann sich statdessen an bereits lesenswerten Artikeln orientieren. Die Wikilinks in den Einzelnachweisen sollten durch Literaturangaben gemäß Hilfe:Einzelnachweise ersetzt werden. --Mischa (Diskussion) 18:45, 15. Jan. 2014 (CET)

Vielen Dank für die Tipps. Klar müssen Regelungen und Gebräuche beachtet werden. Ich habe die erwähnten WP-Empfehlungen studiert und Folgendes geändert:

• Personennamen in der Einleitung: Jetzt mit Vornamen. Ist das dann OK?
• Gliederung: Ich habe im (exzellenten) Artikel ISU-152 die Gliederung (Weiterführende Informationen (Siehe auch, Literatur, Weblinks), Einzelnachweise, Anmerkungen) gefunden, die ich so implementiert habe.
• Einzelnachweise: Die Einzelnachweise habe ich alle mit Seitenzahl versehen. In Hilfe:Einzelnachweise ist zu lesen: „Soll dasselbe Werk mehrfach, jedoch mit unterschiedlichen Seitenzahlen zitiert werden, werden neue Fußnoten mit voller wiederholter Literaturangabe und genauer Seitenzahl verwendet.“ Begründung: das Pflegen und Ändern der Quellen ist einfacher. Nun kommt es im Artikel vor, dass aus den „Anmerkungen“ heraus auf eine Referenz Bezug genommen wird – das <ref>-Tag aber nicht geschachtelt verwendet werden kann. Aus diesem Grund und wegen der mehrfachen Bezugnahme auf das gleiche Werk mit unterschiedlicher Seitenangabe habe ich mit dem {{Anker}} gearbeitet, bei dem man ja sich was überlegen muss, bevor man es aus einem Artikel entfernt. Ist das auch OK?

--Nomen4Omen (Diskussion) 18:12, 19. Jan. 2014 (CET)

Zu den Einzelnachweisen: ich würd' vorschlagen, auch die restlichen ENs als Fließtext (ohne Anker) anzugeben (in Einzelnachweisen müssen die Wikilinks und ISBNs übrigens nicht nochmal angegeben werden, wenn schon im Abschnitt "Literatur" vorhanden). - Ansonsten hoffe ich, dass sich hier noch Leute finden, die was vom Thema verstehen und den Artikel angemessen bewerten können. Sieht aufwendig aber für mich leider auch sehr schwierig aus.--Mischa (Diskussion) 18:11, 20. Jan. 2014 (CET) Aja, Hauptartikel-Links stehen normalerweise direkt unter einer Überschrift, wenn sie gut mit deren Inhalt übereinstimmen, zB so: Informatik#Informatik und Gesellschaft. Also wenn ein Abschnitt eines Artikels auch einen eigenen, ausführlicheren Artikel hat. In deinem Fall würde ich auf die "Hauptartikel" ganz verzichten. Die betreffenden Artikel sind ohnehin bereits in der Einleitung verlinkt. Ist natürlich auch nur eine Kleinigkeit.--Mischa (Diskussion) 18:17, 20. Jan. 2014 (CET)

Vielen Dank für die super Hilfe. Die ENe habe ich alle gemacht. (Bisschen schade, dass das mit dem Anker nicht in den WP:Anleitungen vorkommt. Aber letztlich ist es eine Bagatelle. Jetzt ist das BibISBN überall gleich expandiert, wogegen manche anderen Referenzen nicht. Aber auch: Kleinigkeit)

Die Hauptartikel-Links waren eigentlich wirklich überflüssig.

Ja, ein paar Leute von Fach sollten schon noch reinschaun. Wohl wahr.

--Nomen4Omen (Diskussion) 20:50, 20. Jan. 2014 (CET)

Der Inhalt ist meiner (Wikipedia laien) Meinung nach auf jeden Fall lesenswert. Die Verschiedenen Szenarien (einfügen, löschen, usw.) sind ausführlich beschrieben und gut verständlich. Außerdem werden alle wesentlichen Aspekte behandelt. Auch die Verlinkung von Tutorials finde ich toll. Am Inhalt würde ich also nicht mehr wirklich viel ändern. Formal finde ich bei solchen Themen wichtig, dass die Einleitung zu den jeweiligen Unterpunkten auch für nicht profis halbwegs verständlich sein sollten. Ansonsten solltest du dich an den Wiki-Anforderungen und an bereits lesenswerten oder exzellenten Artikeln des selben Themenbereichs orientieren.  Lesenswert --Mike1988 (Diskussion) 15:50, 17. Jan. 2014 (CET)

Vielen Dank für die Anregungen. Bezüglich der Verständlichkeit der Einleitungen habe ich mich natürlich angestrengt – bin aber möglicherweise „betriebsblind“. Das Studium lesenswerter oder exzellenter Artikel habe ich angefangen, werde es aber noch weiter pflegen. --Nomen4Omen (Diskussion) 18:12, 19. Jan. 2014 (CET)

Das vorgelegte Thema ist in dem Artikel umfassender als je in einem Lehrbuch behandelt, die meisten beschränken sich auf Suchen, Einfügen und Löschen. Die sind als die wichtigsten Operationen auch hervorgehoben. Die Einbettung in den Kontext der Suchbäume und die Ausblicke auf die Software-Technik habe ich so noch nicht gesehen. Die Texte sind für einen Fachmann sehr flüssig. Die Illustrationen sind punktgenau und veranschaulichen den Sachverhalt aufs beste. Ob die Formatierungs-Richtlinien der Wikipedia immer beachtet sind, kann ich wegen Unkenntnis derselben nicht beurteilen. Alles in allem eine richtig gute Behandlung des Themas.  Exzellent (nicht signierter Beitrag von 92.203.36.6 (Diskussion) 07:47, 21. Jan. 2014‎) (Unterschied)

Danke fürs Votum. --Nomen4Omen (Diskussion) 18:35, 22. Jan. 2014 (CET)

Ich finde das Thema umfassend behandelt. Auch für einen Nicht-Informatiker sehr aufschlussreich und gibt einen guten Einblick in das, was die Informatiker so machen. Es ist richtig gut, dass sie sich um Effizienz kümmern – das kommt gut heraus. Ich gebe die Note  Exzellent. (nicht signierter Beitrag von 178.7.106.45 (Diskussion) 14:17, 21. Jan. 2014‎) (Unterschied)

OK, es ist ein Ansporn. --Nomen4Omen (Diskussion) 18:35, 22. Jan. 2014 (CET)

 Abwartend Hallo, bin Nicht-Informatiker, habe bisher nur die Einleitung gelesen und den weiteren Artikel überflogen. Da ist mir folgendes aufgefallen:

• „Der AVL-Baum ist eine Datenstruktur in der Informatik, und zwar ein balancierter binärer Suchbaum, bei dem sich die Höhe der beiden Teilbäume an jedem Knoten höchstens um 1 unterscheidet. Diese Forderung kann mit moderatem Aufwand erfüllt werden…“ Mir ist der Bezug des zweiten Satzes nicht klar: Kann diese Forderung an Datenstrukturen mit moderatem Aufwand erfüllt werden? Oder kann jeder balancierte binäre Suchbaum mit moderatem Aufwand in einen AVL-Baum überführt werden?

Wurde geändert in: Diese Forderung, die den binären Suchbaum zu einem balancierten macht, … erledigtErledigt

• „…verhindert, dass der Baum zu sehr aus der Balance gerät.“ Ist dieser Halbsatz evtl. redundant, da sowieso ein balancierter Baum vorliegt?

Wurde umformuliert. erledigtErledigt

• Bei $\definecolor {LinkBlue}{rgb}{0,0.27058823529411763,0.6784313725490196}\color {LinkBlue}\scriptstyle {\mathcal {O}}(\log n)$ funktioniert bei mir der Wikilink nicht, was ärgerlich ist. Otto Normaluser weiss nicht unbedingt, dass er im Quellcode nachschauen kann, um den Link auf Landau-Symbole zu finden.

Also bei mir funktioniert der Link bei 2 von meinen Browsern; der Mauszeiger verwandelt sich auch in eine Hand und in der Statuszeile unten erscheint Landau-Symbole; nur, dass der Link unterstrichen wird (wie sonst), das funktioniert nicht. Probier’s mal direkt hier oben mit linkem oder rechtem Mausklick. (Es ist also nicht nötig, im Quellcode nachzuschauen.)
Ich hab's aber umformuliert. erledigtErledigt

• „In $\scriptstyle {\mathcal {O}}(\log n)$ ist daher auch die maximale Anzahl der Schritte…“ Wenn ich es richtig verstehe, ist $\scriptstyle {\mathcal {O}}(\log n)$ keine Anzahl, sondern eine Grössenordnung. Und was bedeutet das Wort „In“ am Satzanfang?

Ja, das ist richtig: Es ist eine Menge, also sowas wie eine Grössenordnung. Ein konstanter Faktor > 0, den es ja immer geben muss, interessiert bei den Landau-Symbolen nicht. Kann man dort alles nachlesen. Dort wird auch das ∈-Zeichen verwendet. Die hier verwendete Sprechweise ist durchaus üblich.
Ist wohl durch die obige Umformulierung erledigt. erledigtErledigt

• Die Geschichte dieser Datenstruktur kommt viel zu kurz. Die beiden sowjetischen Mathematiker werden in einem Satz der Einleitung erwähnt, im ganzen weiteren Artikel ist kein weiteres Wort zur Geschichte oder Entstehung dieser Datenstruktur vorhanden.

Zur Geschichte der Datenstruktur gibt's, glaube ich, nicht wirklich viel zu sagen. Wer sich für Geschichte interessiert, kann den Links bei den Personen folgen. Dort kann man bei beiden Personen Links zu Biographien finden, aber nichts weiter zur Datenstruktur. Die Datenstruktur war mW eine Art Doktorarbeit der beiden, und dann gab es die Datenstruktur plötzlich. Wie im Artikel steht, gaben sie ihrem Paper den sehr ehrgeizigen Titel „An algorithm for the organization of information“ (russisch „Один алгоритм организации информации“ (ich hab das in den Artikel rein)). Und der Name AVL wurde mW nicht von den Autoren selbst vergeben, sondern von Englisch sprechenden Informatikern – im Deutschen würde man AWL transskribieren. Aber ich habe keine Ahnung, wer den Namen eingeführt hat, und richtig kreativ ist er ja nicht: es ist absolut üblich, dass in der Mathematik ein Theorem den Namen seines/seiner Schöpfer kriegt. ((Beim Rot-Schwarz-Baum ist bekannt, dass erst Leo J. Guibas und Robert Sedgewick auf den heutigen Namen umgetauft haben und nicht der Erfinder Rudolf Bayer.)) (In den Artikel möchte ich das alles aber nicht reinnehmen.)

Das sind mMn doch erwähnenswerte Informationen: Dass es eine Art Doktorarbeit war (btw: was heisst eine Art?), wer wann den Namen vergeben hat, ob und wie das Thema evtl. in einem Gesamtzusammenhang zu sehen ist – einerseits der Forschung der beiden Mathematiker, andereseits der balancierten Bäume oder Datenstrukturtheorie generell. Das müsste doch ein Kapitel ("Entstehung" / "Geschichte" o.ä.) oder wenigstens einen ganzen Artikelabsatz hergeben. Die beiden Sätze dazu in der Einleitung finde ich zuwenig, auch weil die Einleitung ja eine Artikelzusammenfassung sein soll und nicht Informationen enthalten sollte, die im weiteren gar nicht mehr vorkommen. Will damit sagen, die beiden Sätze sind völlig in Ordnung, wenn das dann im Artikel näher erläutert wird. Gruss --Toni am See (Diskussion) 20:30, 23. Jan. 2014 (CET)

Also erstmal vielen Dank für die Anregungen. (Ich hab sie jetzt erst wahrgenommen.) Sicher ist, dass es ein „Paper“ war, also ein Beitrag in eine wissenschaftliche Zeitschrift. Das steht aber schon da. Welchen genauen Rang dieser Beitrag in der Karriere der Autoren hatte, weiß ich eigentlich nicht. Deshalb oben die wachsweiche Formulierung „eine Art“. (Ich werde versuchen, da mehr zu recherchieren, was aber dauern kann.) Sicher ist, dass der Beitrag sehr schnell von der „Wissenschaft“ aufgegriffen wurde. Das ist (implizit) daran erkennbar, dass die englische Übersetzung im gleichen Jahr veröffentlicht wurde. (Belege dazu sind jetzt drin, sogar URLs.)

Dann: Der erste der beiden Sätze ist eine Behauptung, die durch die Referenz belegt ist und so vom skeptischen Leser leicht nachgeprüft werden kann. Der zweite Satz ist ebenfalls eine Behauptung, die nur sehr umständlich belegt werden kann. MMn kommt jedoch zwischen den Zeilen des Artikels heraus, dass der Rot-Schwarz-Baum eine Art Weiterentwicklung (und Konkurrenz – so mein nicht leicht belegbarer persönlicher Eindruck) darstellt. (NB: Es gibt den Abschnitt AVL-Baum#Vergleich mit Rot-Schwarz-Baum.) Die Historie zwischen den beiden deutlich zu machen, gehört mMn aber eher dort hinein als hier. (Wenn meine Texte Anklang finden, versuche ich das auch. Aber jener Artikel ist Lesenswert.) Zudem muss man wegen WP:NPOV aufpassen. --Nomen4Omen (Diskussion) 12:45, 24. Jan. 2014 (CET)

Der Artikel mag fachlich hervorragend sein (ich kann es nicht beurteilen), aber nach meinem ersten Eindruck eher nicht auszeichnungswürdig für Wikipedia, bei ehrlich gemeintem Respekt. Sorry und Gruss --Toni am See (Diskussion) 07:29, 22. Jan. 2014 (CET)

Vielen Dank für deine Anregungen. Es liegt mir sehr am Herzen, dass das Zeug gut verständlich ist. Hoffentlich ist es das jetzt eher.

Antworten jeweils reingequetscht. --Nomen4Omen (Diskussion) 18:35, 22. Jan. 2014 (CET)

Die Einleitung ein bisschen geglättet. Abschnitt „Balance“ in „Vorbemerkung“ umbenannt. --Nomen4Omen (Diskussion) 10:08, 24. Jan. 2014 (CET)

Der Artikel ist meiner Meinung nach sehr verständlich, gut strukturiert und fachlich hervorragend. Die Kernpunkte des AVL-Baums werden mit allen relevanten Details dargestellt, wobei die ausführliche Funktions- und Aufwandsanalyse positiv auffällt. Darüber hinaus deckt der umfassende Artikel viele praxisrelevante Aspekte und Verbindungen zu verwandten Themen ab. Der Artikel ist sehr gut mit verwandten Wikipedia-Artikeln abgestimmt und verlinkt. Ich wünsche mir mehr Artikel dieser hohen Qualität auf der deutschsprachigen Wikipedia und stimme daher mit  Exzellent. --Matroid (Diskussion) 02:25, 25. Jan. 2014 (CET)

(zwischenquetsch) Info: dieser account wurde nur angemeldet (One-Purpose-Account), um hier als Jubelperser(-socke?) abzustimmen. nachdem dies bereits die zwei IPs oben mit jeweils nur einem einzigen Beitrag getan haben. --Jbergner (Diskussion) 15:23, 3. Feb. 2014 (CET)

Was ist mit WP:GVGAA? Kann doch sein, das ein nichtangemeldeter Benutzer den Artikel liest, gut findet, sieht, dass er gerade um eine Auszeichnung kandidiert, und abstimmen möchte (und sich denkt, dass es besser kommt, wenn er/sie sich dazu anmeldet). Wir sollten Nicht-WP-Insider nicht noch mehr abschrecken, um nicht endgültig zu einem hermetischen Kreis von Eigeweihten zu werden. KALP fordert ausdrücklich auch IPs und Neulinge zur Abstimmung auf, Stimmberechtigung ist bewusst nicht erfordert. --Bujo (Diskussion) 17:24, 3. Feb. 2014 (CET)

genau aus GVGAA steht da davor: Info. weil du recht haben könntest. oder auch nicht. sonst wäre die stimme ja auch schon gestrichen. jetzt wird sie mit abgewogen. --Jbergner (Diskussion) 17:36, 3. Feb. 2014 (CET)

Lieber Matroid, ich möchte mich ausdrücklich für das positive und m.E. gut begründete Votum bedanken. In dem, was ich gesehen habe, gehen die englischen Wikipedianer ganz anders „in die Vollen“ (wenn auch nicht direkt beim Konkurrenzartikel). --Nomen4Omen (Diskussion) 17:08, 27. Jan. 2014 (CET)

 keine Auszeichnung Dem Lob meiner Vorredner kann ich mich leider nicht anschließen. Dieser Artikel ist aus reiner Binnensicht eines Informatikers geschrieben und erinnert sehr an Abhandlungen in Lehrbüchern. Sicher ist viel Arbeit investiert worden, aber Wikipedia ist nunmal kein Lehrbuch oder Fachlexikon. Die Dinge sollen allgemeinverständlich auch für fachlich nicht versierte Leser dargestellt werden. Dazu gehört u.a., dass der unbedarfte Leser nicht bereits in der Einleitung mit Fachtermini und mathematischen Notationen erschlagen wird. Weiterhin wird nicht motiviert, welche Problemstellungen in welchem Fachgebiet üblicherweise zu einer solchen Baumstruktur führen können; ein konkretes Beispiel ist hier sinnvoll. Ein kurzer geschichtlicher Abriss fehlt ebenso. Wenn es sich um einen ganz speziellen Suchbaum handelt, was existiert dann noch (abgesehen vom verallgemeinerten Rot-Schwarz-Baum)? Eine Einordnung mit entsprechenden Vergleichen (Leistungsfähigkeit/Einschränkungen/Vor- und Nachteile ohne Formelkram) fehlt völlig oder ich habe sie im Formelwust völlig übersehen. Mathematische Formeln sollten nur in Ausnahmefällen (z.B. E=m*c²) in eines lesenswerten oder gar exzellenten Artikel einfließen. Fachliche Details, die den größten Teil des Artikel in seiner jetzigen Form ausmachen, findet der interessierte Leser in der anzugebenen weiterführenden Spezialliteratur. Exzellente Artikel sollen Vorzeigeartikel für ein breites Publikum sein. Das ist hier nicht gegeben. Ob der Artikel wenigstens lesenswert ist, darüber kann man sicher streiten. Ich persönlich denke, er ist aufgrund der fehlenden Allgemeinverständlichkeit nicht einmal das. 79.193.9.249 12:27, 25. Jan. 2014 (CET)

„Mathematische Formeln sollten nur in Ausnahmefällen (z.B. E=m*c²) in eines lesenswerten oder gar exzellenten Artikel einfließen.“ Das heißt Artikel zu einem Großteil der Themen aus Mathematik, Informatik oder Physik sind für dich nicht auszeichnungsfähig? --Chricho ¹ ² ³ 12:36, 25. Jan. 2014 (CET)

Ein guter Artikel in Wikipedia soll verständlich sein. Überprüfe neue Artikel oder Änderungen auf allgemeine Verständlichkeit, siehe Checkliste Verständlichkeit. Menschen ohne einschlägige fachliche Vorbildung sollen den Artikel verstehen können. Sie sollen zumindest die Einleitung sofort verstehen. Bei komplexen Themen sollen sie den Artikel zumindest grob verstehen. Zur Verständlichkeit erforderliche Erklärungen sollen direkt im Artikel gegeben werden. (Wikipedia:Allgemeinverständlichkeit) Bei besonders guten Artikeln, den lesenswerten und exzellenten also, sollte demnach mehr als nur ein grobes Verständnis beim Leser ohne einschlägige fachliche Vorbildung erzielt werden. Über die normale Schulbildung hinausgehende mathematische Formeln erschweren im Allgemeinen das Verständnis des dargestellten Zusammenhangs und sind daher hinderlich. Und damit liegt es in der Natur der Sache und hat rein gar nichts mit meiner persönlichen Einstellung (...sind für dich nicht auszeichnungsfähig) zu tun, dass nur durch viel oder nur durch komplizierten Formelkram beschreibbare Spezialthemen auch nicht auszeichnungswürdig sind. 79.193.23.23 13:29, 25. Jan. 2014 (CET)

Das is tkein „Spezialthema“, aber um Verständnis für Eigenschaften einer Datenstruktur zu erlangen, muss man nunmal verstehen, was asymptotische Laufzeit ist. So kompliziert ist das nicht, wird auch in so manchem Schulunterricht vermittelt, kann aber nicht in jedem Artikel dargestellt werden. --Chricho ¹ ² ³ 13:46, 25. Jan. 2014 (CET)

Wo habe ich behauptet, dass die Suchbaumthematik nur durch Formeln erläuterbar ist? Nirgendwo. Die Suchbaumthematik ist genau eines der Gebiete in der Informatik, das für den Laien überblicksartig fast allein durch Worte und Grafiken (Stichwort asymptotische Laufzeit) dargestellt und verständlich gemacht werden kann. Spezialfälle und restlicher Formelkram interessieren eh nur Fachleute und die nehmen dann die empfohlene Fachliteratur zur Hand. Nochmal: In der Wikipedia geht es um allgemeinverständliche Überblickartikel, nicht um Forschungsarbeiten für einen kleinen Kreis von Spezialisten. Und damit EOD für mich. 79.193.12.251 14:14, 25. Jan. 2014 (CET)

Wenn das Thema nunmal das Verständnis gewisser formaler Begrifflichkeiten voraussetzt, dann ist das kein Manko des Artikels. Wenn der Schulunterricht nicht über Logarithmen, asymptotische Laufzeit oder Landau-Notation aufgeklärt hat, möge man eben die entsprechenden Artikel bemühen. Das mit den „Fachleuten“ ist Unsinn. Wer schon Fachmann ist, der braucht nicht Introduction to Algorithms lesen. Der weiß das einfach schon oder will vllt. ein Detail nachschauen, wofür ein WP-Artikel auch gut sein kann. Irgendwelche benötigte Kenntnisse gibt es bei jedem Artikel. Fachmann für Algorithmen muss man hier sicherlich nicht sein (durch die Möglichkeit, die Landau-Notation zu verstehen, ist man noch lange kein Fachmann). Du stellst hier den Sinn mehrerer ganzer Themenbereiche in der Wikipedia infrage. --Chricho ¹ ² ³ 14:31, 25. Jan. 2014 (CET)

Hallo Ihr Lieben, ich bin zwar ein Betroffener (oder hier fastgar der Betroffene). Eine Meinung darf ich aber trotzdem haben zu dem Disput, der hier entsteht. Es ist doch nicht so, dass Wikipedia eine Volkshochschule ist, bei der sich Leute angemeldet haben, weil sie unbedingt Excel-Wissen für den Job brauchen. Wenn einer einen Artikel in der Wikipedia anschaut, dann geschieht das in einem Grad von Freiwilligkeit, die weit über die Teilnahme an einem Volkshochschulkurs hinausgeht. Ein Wikipedia-Autor kann einen Leser seines Artikels nicht dazu zwingen, bis zum Ende der Stunde durchzuhalten. Wenn jener den Antrieb verliert, der Artikel ihm zu blöd oder zu anstrengend ist, dann klickt er weiter.
Wikipedia ist ein Angebot! Ich habe nicht alle Artikel im Wikipedia durchgelesen, nicht alle exzellenten und nicht alle lesenswerten Artikel. Wenn ich mir einen Artikel genauer vornehme, dann weil mich das Thema interessiert, vielleicht auch weil der Artikel gut geschrieben ist, aber hauptsächlich, weil der Artikel „für mich was hergibt“. Jeder Artikel ist für sich ein Angebot. Wer einen Artikel zumacht, weil er eine Formel sieht, die über E=mc² hinausgeht, der hat das volle Recht dazu. Er hat aber auch die Möglichkeit, eine Herausforderung anzunehmen. Ich behaupte jetzt mal: Weder das Thema noch die Ausarbeitung des besagten Artikels schlägt eine anfängliche echte Neugier tot. Und: Wer sich nur für Algorithmen interessiert, kann die Formeln überspringen. Wer aber dazuhin auf die Effizienzüberlegungen neugierig ist, der möchte auch auf seine Kosten kommen. --Nomen4Omen (Diskussion) 22:18, 25. Jan. 2014 (CET)

Ich gebe aber zu, dass es einfach war, auf eine große Anzahl von Landau-Symbolen zu verzichten! (S. geänderten Artikel) --Nomen4Omen (Diskussion) 05:34, 26. Jan. 2014 (CET)

Der erste Schritt hin zu einer besseren Allgemeinverständlichkeit ist nun getan, danke. Aber es liegt noch viel im Argen. Eine gute und auch für Laien völlig ausreichende Erklärung, ganz ohne Formelkram, findet sich unter http://www.ai.wu.ac.at/~koch/courses/wuw/archive/inf-sem-ss-01/pinterits/text.html (nein, ich bin nicht der Autor). Kurz und knapp ohne viel wissenschaftlich verbrämtes Geschwafel. So stelle ich mir eine allgemeinverständliche Beschreibung vor. Für Wikipedia müßten allerdings noch einige Dinge ergänzt werden (historisches etc.). 79.193.55.224 19:49, 26. Jan. 2014 (CET)

Ich habe mir die Ausarbeitung angesehen. Da gibt es die Rechtschreibfehler: "Algorythmus" ist konsequent durchgehalten. Das ist schnell korrigiert. Dann fehlt bspw. völlig, dass die "Balance" (d.i. in der Literatur der Balance-Faktor) in größerem Umfang als nur durch Rotationen gepflegt werden muss: wenn sich nämlich eine "Balance" ändert, muss nicht, aber kann das zur Folge haben, dass sich die "Balance" darüber auch ändert. Dies sollte auch einem Laien nicht vorenthalten werden. Und zum "wissenschaftlich verbrämten Geschwafel": mancher Leser (zugegeben nicht jeder) möchte vielleicht durchaus auch die Fachbegriffe kennenlernen, die zum Gegenstand seines Interesses gehören. (So viele sind's ja nun auch wieder nicht.)

Aber wir sind ein freies Land, und Wikipedia ist eine freie Enzyklopädie: Nur zu, niemand kann dich hindern! --Nomen4Omen (Diskussion) 23:28, 26. Jan. 2014 (CET)

Der Internetartikel dient lediglich als Beispiel, wie allgemeinverständlich mit Hilfe passender Grafiken formuliert wird. Dass dort unter Umständen einige Fakten fehlen und Rechtschreibfehler auftreten, spielt dabei keine Rolle. In deiner Version mögen alle Fakten enthalten sein, aber man versteht als Nicht-Informatiker gar nichts. Was ist schlimmer? Davon einmal abgesehen schrieb ich, dass für Wikipedia noch einige Dinge ergänzt werden müssten. Nur zu, niemand kann dich hindern! Dann müsste ich den Artikel komplett neu schreiben und das würde bei dir und deinen Fans wohl auf wenig Gegenliebe stoßen - insofern ist Wikipedia nicht wirklich eine freie Enzyklopädie. Aber wenigstens kann ich hier bei der Abstimmung auf grobe Misstände hinweisen. Nimm es bitte nicht persönlich. 79.193.20.49 10:03, 27. Jan. 2014 (CET)

Ich habe den Wikipedia-Artikel noch einmal überflogen und von meiner Sicht aus nichts gefunden, was dir Schwierigkeiten machen könnte, außer vielleicht dem Logarithmischen. (Zumindest, wenn du die Anmerkungen überspringst.) Ist es das Logarithmische? Das sind Effizienzüberlegungen, die m.E. zwingend zu einem Wikipedia-Artikel über ein solches Thema gehören. Denn ohne sie müsste man ein derartiges algorithmisches Theater gar nicht veranstalten. Wenn du über den Internet-Artikel den AVL-Baum verstanden hast, sehe ich eigentlich keinen Grund, warum du den Wikipedia-Artikel nicht verstehen solltest. Auch im Internet-Artikel steht: "Vorteil dieses Vorgehens ist, dass der AVL-Baum immer möglichst ausgeglichen gehalten wird, also nicht degeneriert, woraus sich eine möglichst kleine Anzahl von Suchschritten bzw. eine Möglichst kurze Suchzeit für Elemente ergibt." Nur nicht: möglichst kurz = logarithmisch; und nicht, dass das auch fürs Einfügen und Löschen gelten soll. Aber es dürfte dir schon klar sein, dass man das in einem Wikipedia-Artikel besser quantifizieren muss, wenn man kann und wenn die Viecher extra zu dem Zweck erfunden wurden.

Wenn es das aber nicht ist, müsste ich dich um einen konkreten Ansatzpunkt bitten. --Nomen4Omen (Diskussion) 17:08, 27. Jan. 2014 (CET)

Es geht hier nicht um's Logarithmische. Das Gesamtpaket stimmt in vielerlei Hinsicht nicht. Neben den bereits namentlich genannten Mängeln (Motivation inkl. Beispiel (z.B. konkretes Suchproblem und resultierender Baum), historischer Abriss, Einordnung) verliert sich der Artikel zu sehr im wissenschaftlichen Detail, will möglichst alles ganz korrekt und mit allen möglichen Sonderfällen darstellen. Sätze wie:

Ähnlich wie es bei einem unbalancierten binären Suchbaum eine hohe Wahrscheinlichkeit gibt, dass er bei zufälligen Einfügungen eine gewisse Balanciertheit erlangt,[6] ist auch beim AVL-Baum die Wahrscheinlichkeit sehr hoch, dass er besser balanciert herauskommt als seine am schlechtesten balancierte Ausprägung, der Fibonacci-Baum. Strebt beim Fibonacci-Baum die Anzahl n der Knoten gegen unendlich, dann verhält sich seine mittlere Suchtiefe über alle Knoten asymptotisch wie a log2 n mit a := c Φ⁄√5 = Φ⁄√5 log2 Φ ≈ 1,042298, weicht also nur um 4 Prozent von der idealen eines vollständig balancierten Binärbaums ab. Wird über alle AVL-Bäume einer festen Höhe bzw. über alle Einfügereihenfolgen zu einer festen Knotenzahl gemittelt, liegt der Mehraufwand gegenüber den jeweils bestmöglichen, den vollständig balancierten Binärbäumen zwischen 0 und 2 Prozent (Zahlen für kleine Bäume im Abschnitt Mittlere Suchtiefe bei AVL-Bäumen).

sind eine Zumutung für den fachfremden Leser. Hier muss Genauig-/Ausführlichkeit eben Allgemeinverständlichkeit weichen und der wirklich interessierte Leser auf Spezialliteratur verwiesen werden. Dieser verquaste Stil zieht sich durch den gesamten Artikel und macht ihn nach wie vor unverständlich. Ich habe dir ein Beispiel gegeben, wie es auch anders dargestellt werden kann. Wenn du die Unterschiede nicht erkennst oder erkennen willst, kann ich leider auch nicht weiterhelfen. Damit hier Ende der Diskussion für mich. 79.193.15.184 10:15, 29. Jan. 2014 (CET)

Ich habe den inkriminierten Satz in die Anmerkungen verschoben. --Nomen4Omen (Diskussion) 20:25, 29. Jan. 2014 (CET)

Ich habe den Artikel nun einmal überfolgen, aber als Nicht-Informatikerin gibt er einen guten Einblick in die Informatikerwelt. Die einzelnen Operationen sind auf jeden Fall gut verständlich. Die Beispiele bzw. Anwendungsbeispiele finde ich auch gut gewählt. Ich würde nicht mehr viel ändern – meiner Ansicht nach ist der Artikel auf jeden Fall lesenswert. LG --Chulia2409 (Diskussion) 14:27, 29. Jan. 2014 (CET)

• Ich muss leider auch anmerken, dass der Artikel eine zu starke fachspezifische Binnensicht für einen allgemeinbildenden Enzykopädieartikel hat. Dass er fachlich genau ist (was ich als Laie einfach mal annehme), ist natürlich lobenswert und für einen auszuzeichnenden Artikel auch unabdingbar. Ein ausgezeichneter/auszuzeichnender Wikipedia-Artikel muss aber den Spagat schaffen, sowohl in fachlicher Hinsicht korrekt und tiefgründig zu sein, als auch allgemein verständlich (siehe WP:OMA). Ich finde in dem Artikel z.B. überhaupt nichts über die Anwendung eines AVL-Baums. Das ist ein wesentlicher Aspekt, der zu einer umfassenden Darstellung des Themas fehlt. Wenn der Artikel nur erklärt, was ein AVL-Baum ist und wie er funktioniert, nicht aber wozu man ihn braucht, ist er nicht umfassend, sondern lückenhaft.

IP 92... sagt in ihrem Exzellent-Votum, der Artikel behandele das Thema "umfassender als je in einem Lehrbuch". Das ist aus meiner Sicht ein zweifelhaftes Lob. Wikipedia-Artikel sollten sich überhaupt nicht mit Lehrbüchern vergleichen. Eine Enzyklopädie ist kein "besseres Lehrbuch", sondern hat einen ganz anderen Rahmen und eine andere Zielgruppe. Nomen4Omens Argument, dass WP ja keine Volkshochschule sei, möchte ich fast ins Gegenteil verkehren: Meinem Verständnis nach ist sie eher eine Volkshochschule, als eine Fachtextsammlung. Im Idealfall sollte sie beides sein und sowohl Fachleute als auch Laien zufrieden stellen. Nur ein Artikel, dem das gelingt, ist ein vorbildliches Beispiel und deshalb auszeichnungswürdig. Der größte Mangel in diesem Fall ist aus meiner Sicht die fehlende Darstellung der Anwendung. Wenn das in der Kürze der Zeit noch auf ansprechende Weise behoben werden kann, bin ich ggf. bereit, mein Votum zu revidieren. --Bujo (Diskussion) 16:19, 29. Jan. 2014 (CET)

Danke für die Anregungen. Ich habe daraufhin die Vorbemerkung in Motivation umbenannt und hoffentlich adäquat ausgebaut. Zum vorhandenen (dynamischen) Beispiel ein statisches und ein dynamisches Anwendungsbeispiel zugefügt. --Nomen4Omen (Diskussion) 20:25, 29. Jan. 2014 (CET)

Noch etwas: Der Stil des Artikels ist keinesfalls so, wie ich ihn bei einem auszuzeichnenden WP-Artikel erwarten würde. Ich weiß nicht, ob du mal den Autoreviewer benutzt hast? Er bestätigt, was mir auch beim Lesen aufgefallen ist: Der Artikel verwendet sehr viele Füllwörter, außerdem Konstruktionen, die in enzyklopädischen Artikeln vermieden werden sollten ("Wenn nicht, ob man besser weiter vorn oder weiter hinten weitersucht." ist z.B. überhaupt kein vollständiger Satz.) Das persönliche Einbeziehen des Lesers "Haben wir beispielsweise...dann haben wir..." (besonders schlechter Stil auch noch durch Wortwiederholung!) "das heißt wir kommen...", "dann kommen wir von einem Ast,..." "wir beziehen uns in diesem Abschnitt auf die Abbildung 2" (fragt sich, wer hier mit wir gemeint ist) usw. Mag sein, dass man in einem Lehrbuch so schreibt (schon da fände ich es eher keinen guten Stil), in einer Enzyklopädie ist es jedenfalls völlig ungewöhnlich. Der Artikel liest sich in weiten Strecken, wie eine Anleitung. Und das ist Punkt 9 auf der Liste Wikipedia:Was Wikipedia nicht ist. In der Tat wäre der Artikel wohl eher ein Kandidat für das Schwesterprojekt Wikibooks. Dort sollen nämlich freie Lehrbuchtexte erstellt werden. Zu Wikipedia passt er weniger. Von einer Auszeichnung ist er von daher leider noch meilenweit entfernt. --Bujo (Diskussion) 22:09, 30. Jan. 2014 (CET)

• Autoreviewer: Wurde Anfang Dezember gemacht mit dem Ergebnis: weniger Füllwörter als der Durchschnitt der exzellenten Artikel. Hat sich allerdings seither wieder etwas erhöht, weil dadurch größere Verständlichkeit erhofft wird.
• „wir“: Hab’s konsequent ersetzt durch „man“, wie es der (exzellente) Artikel Rasterung von Linien hat, resp. durch eine passivische Konstruktion.
• Nicht Anleitung: Sind bei der Beschreibung einer Datenstruktur und eines Algorithmus Code-Schnipsel (wie im (lesenswerten) Artikel Rot-Schwarz-Baum) besser geeignet als Beschreibungen der Vorgehensweise? Da hätte ich gerne einen präzisen Rat. --Nomen4Omen (Diskussion) 19:57, 31. Jan. 2014 (CET)

 Exzellent Ein guter umfassender Artikel über diese bedeutende Datenstruktur. Andim (Diskussion) 12:13, 30. Jan. 2014 (CET)

Danke für die Anerkennung. --Nomen4Omen (Diskussion) 19:57, 31. Jan. 2014 (CET)

Vollkommen OMA-ungeeignet, der Hauptteil ist wahrscheinlich notwendiger Weise für mich Technobabel, aber die Einleitung sollte verständlicher sein. Und praktische Anwendungsbeispiele wären wirklich nett. Vorläufig leider  keine Auszeichnung. syrcroпедия 15:00, 30. Jan. 2014 (CET)

Praktische Anwendungsbeispiele waren drin, haben aber jetzt einen eigenen Abschnitt, und es sind jetzt mehr davon. --Nomen4Omen (Diskussion) 19:57, 31. Jan. 2014 (CET)

Liebe/r syrcroпедия! Man kann sich fragen, wie sinnvoll es ist, bei einem Artikel ein Urteil abzugeben, der „wahrscheinlich notwendiger Weise Technobabel“ (für den/die Juror/in) ist, dessen Thema einen also überhaupt nicht interessiert und den man nicht wirklich lesen möchte. Dabei ist an deinem Desinteresse überhaupt nichts zu kritisieren! Es gibt einfach zu viel auf der Welt und in der Wikipedia, als dass einen alles interessieren könnte oder gar müsste. Ich habe zB überhaupt nichts gegen Zwergkaninchen, ich finde sie auch „süß“. Aber mein thematisches Interesse an ihnen ist zu niedrig, als dass ich mich aufgerufen fühlen würde, ein Urteil über einen entsprechenden Artikel abzugeben, und ich möchte mich definitiv nicht in das Thema einarbeiten.
Und zur Einleitung: wenn dir die Einleitung nicht verständlich genug ist, hast du vielleicht außerordentlich viel Zeit gespart. Bei einer Einleitung, die dir verständlicher ist, könntest du in Gefahr geraten, mit den Klicks weg und zurück, die in der Mathematik und Informatik für einen Neuling unabdingbar sind, unnötig Zeit zu vergeuden, bis du feststellst, dass der Stoff dich trotzdem definitiv nicht interessiert. Immerhin scheinst du so viel verstanden zu haben, dass „der Hauptteil wahrscheinlich notwendiger Weise Technobabel“ für dich ist. Ist doch gut! --Nomen4Omen (Diskussion) 14:35, 2. Feb. 2014 (CET)

Ich finde deinen Kommentar ziemlich seltsam. Mag sein, dass du dich über das sehr knapp begründete und unverblümte Votum Syrcros geärgert hast. Aber laut Kriterien für exzellente Artikel sollen diese Interesse anregen, zum Weiterlesen einladen. Wenn du nun schreibst, dass deine Einleitung Benutzer, die sich sowieso nicht so sehr interessieren, abschrecken soll, um ihnen die Zeitvergeudung zu ersparen, muss ich mich doch sehr wundern. "OMA" bedeutet in der Wikipedia-Terminologie, wie schon jemand hier geschrieben hat, nicht Großmutter, sondern "ohne mindeste Ahnung". Artikel sollen also so sein, dass Benutzer ohne mindeste Ahnung sie verstehen. Nun schreibst du, dass dein Artikel für Neulinge in der Mathematik und Informatik quasi zwangsläufig uninteressant und unverständlich und seine Lektüre für sie Zeitvergeudung ist. Damit sagst du selbst, dass er die Exzellenz-Kriterien nicht erfüllt (nämlich auch für komplette Laien ansprechend und bereichernd zu sein). Genau diese "Neulinge", die kein "Technobabel" verstehen, sind die Zielgruppe von Wikipedia-Artikeln. Sie einzuladen und mitzunehmen, ihr Interesse zu wecken und zu erfüllen, ist die Aufgabe exzellenter Artikel. Mit der Einstellung "Wer meinen Artikel lesen will, muss sich eben ein bisschen zusammenreißen" kriegt man keinen exzellenten Artikel. Einen exzellenten Artikel erkennt man daran, dass er einen anspricht und zum Weiterlesen lockt, obwohl man überhaupt keine Ahnung von dem Thema hat und sich normalerweise auch gar nicht so dafür interessiert. --Bujo (Diskussion) 22:52, 2. Feb. 2014 (CET)

Danke, liebe/r Bujo! Jetzt weiß ich, was OMA bedeutet. (Ich hatte es in WP:OMA nicht finden können.) Dann ist ja alles klar. Dann haben es so Wissenschaften wie Mathematik, (theoretische) Informatik und ähnliche unendlich schwer, gute Artikel hervorzubringen. Denn es ist bei ihnen ein Charakteristikum, dass die Inhalte stark aufeinander aufbauen und der Stoff in der ersten Etage ohne mindeste Ahnung vom Erdgeschoss nicht verstanden werden kann. Und man möchte ja nicht allezeit das Erdgeschoss wiederholen, das wäre ja gar zu langweilig. Schönen Gruß und nochmals danke!
Noch eine Frage: Sind diese Inhalte dann in WP generell unerwünscht? Werden sie bald getilgt? {Immerhin scheint sich das Klima zu verschärfen (s.u. Nintendo-Nerd).} --Nomen4Omen (Diskussion) 09:13, 3. Feb. 2014 (CET)

Es ist immer sehr schwer, exzellente Artikel zu schreiben (ich habe selbst bisher erst zweimal lesenswert geschafft, obwohl ich viel Arbeit investiert habe). Es ist auch sehr schwer, geschichtliche, biologische etc. etc. Themen so verständlich zu schreiben, dass sie jemand ohne mindeste Ahnung versteht. Ich denke, da unterscheiden sich die Wissenschaften untereinander nicht besonders. Wenn es leicht wäre, dann wäre die Exzellent-Auszeichnung ja nichts besonderes. Mag sein, dass manche Benutzer so einen guten Stil und so eine große Routine haben, dass es ihnen inzwischen leicht fällt, und sie jeden Artikel, den sie sich vornehmen, zur Exzellenz führen. Aber für die meisten ist das sehr schwer. Guter, verständlicher, ansprechender Stil hat auch etwas mit Begabung und Übung zu tun. Meinem letzten ausgezeichneten Artikel wurde vorgeworfen, er sei "stumpf und eintönig". Das wollte ich natürlich nicht, aber vielleicht kann ich es einfach nicht besser. Werden diese Inhalte gelöscht? Sicherlich nicht, aber eben auch nicht mit "exzellent" ausgezeichnet. Bei lesenswerten Artikeln wird Fachjargon laut Kriterien "trotz schlechterer Verständlichkeit toleriert, wenn die Darstellung des Themas ihn erfordert", bei exzellenten nicht. Nicht jeder Artikel kann ein Vorzeigebeispiel sein, gelöscht werden sie deshalb noch lange nicht. (Dein Artikel ist doch nicht schlecht, das hat ja niemand behauptet. Es gibt hier hunderttausende Artikel, die viel, viel schlechter sind). --Bujo (Diskussion) 14:56, 3. Feb. 2014 (CET)

Danke für diesen exzellenten Beitrag, Bujo! Du sprichst mir damit aus dem Herzen. 79.193.40.108 09:03, 3. Feb. 2014 (CET)

Generell zu WP:OMA: In jedem der (exzellenten) Artikeln Ackermannfunktion, Komplexitätstheorie, Problem des Handlungsreisenden gibt es mehr und schwierigere Formeln zu verdauen als im vorliegenden. Ich möchte gerne die OMA kennenlernen, die diese packt – und die OMA, die sich für den AVL-Baum wirklich interessiert und es nicht packt. Zugegeben: Jene Artikel sind gut geschrieben (und ich habe sie kapiert). Andererseits erwartet man vom AVL-Baum (wohl zu Recht) nicht so tiefen Erkenntnisgewinn wie von der Komplexitätstheorie (obwohl er mehr angeklickt wird als die ersteren beiden(!), aber nicht so oft wie TSP). M.a.W. die OMA ist vermutlich bereit, dort mehr geistige Anstrengung zu investieren als beim AVL-Baum. IMHO mein Statement: wenn sie jene packt, packt sie dieses auch, wenn sie wirklich will.
Weitere Anwendungen und Historisches wurden nachgereicht. --Nomen4Omen (Diskussion) 19:57, 31. Jan. 2014 (CET)

Ackermannfunktion (2004), Komplexitätstheorie (2006), Problem des Handlungsreisenden (2006) sind vor Urzeiten als exzellent eingestuft worden, wohl weil ein paar Autorenkumpel und bestellte Jubelperser diese durchgewunken haben. Solch ein Wikipedia-schädigendes Abstimmungsverhalten muss man leider auch heutzutage noch bei einigen Exzellenz-Kandidaturen beobachten. WP:OMA hat übrigens nichts mit Großmüttern zu tun. Und der Artikel zum AVL-Baum ist nach wie vor nicht auszeichnungswürdig, auch wenn stellenweise nachgebessert wurde. 79.193.32.250 20:25, 31. Jan. 2014 (CET)

„wohl weil ein paar Autorenkumpel und bestellte Jubelperser diese durchgewunken haben.“ - wohl eher, weil damals noch nicht so strenge Forderungen an ausgezeichnete Artikel gestellt wurden wie heute. Nintendo-Nerd 12:15, 1. Feb. 2014 (CET)

 keine Auszeichnung ich versteh nur bahnhof. sogar nach lesen der einleitung ist für mich unklar, worum es genau geht. so ist das mMn kein beispielhafter artikel. unverständliche fachdarstellungen, und wenn sie doktorarbeitswürdig sind, gehören nicht in eine enzyklopädie. --Jbergner (Diskussion) 09:24, 3. Feb. 2014 (CET)

Na ganz so einfach, wie Jberger u.a. meinen, kann man sich die Sache auch nicht machen. Ich verweise ganz beliebig nur mal auf die chemischen Metallcarbonyle, die mathematische Mandelbrot-Menge sowie auf die Amyloidschichtpilze und den sprachwissenschaftlichen I-Umlaut - alles als lesenswert ausgezeichnete Fachartikel, die hier in WP keinen Platz mehr haben sollen, nur weil sie von vielen nicht verstanden werden? Ich blicke bei den Metallcarbonylen genausowenig durch wie beim hier diskutierten AVL-Baum, spreche aber keinem die Existenzberechtigung ab. (Und Mandelbrot habe ich lange sowieso für ein Süßgebäck gehalten.) Zu "unverständliche fachdarstellungen ... gehören nicht in eine enzyklopädie": Es gibt auch Fachenzyklopädien, und WP hat wohl Artikel zu fast allen fachlichen Fächern und Feldern, das wird wohl niemand ernsthaft bestreiten. Auerßerdem: Die Grenzen zwischen Fachsprache und Allgemeinsprache sind halt hinsichtlich ihrer Verständlichkeit nicht überall gleich. (Vgl. Geschichtswissenschaft vs. Biochemie.) IMHO ist es eine Grundsatzgfrage, ob man "fachchinesische" Artikel nach den geltenden Richtlinien der WP überhaupt auszeichenn soll/darf oder nicht, die es aber erst zu klären gilt. Bis dahin sollte man sich nach dem richten, was bisher vorliegt - und das sind sehr wohl Auszeichnungen für Fachartikel in Fachsprache.

Ich halte den Artikel - so weit ich es als blanker Laie beurteilen kann - für gelungen und gut aufbereitet, lediglich der Abschnitt "Motivation", der einzige, den ich so ungefähr verstehe, entspricht stilistisch schon sehr einem Lehrbuch, nicht einem enzyklopädischen Artikel. Ich habe daher die dringlichsten Passagen umformuliert und auch ein paar Interpunktionsfehler korrigiert. Außerdem ist "herauskommen" hier sehr umgangssprachlich, das ich in einem Fall ersetzt habe.

Eine Kleinigkeit: Es heißt: "Die wichtigsten Operationen bei den Suchbäumen ... sind: Suchen einerseits sowie Einfügen und Löschen andererseits." Die Phrase "einerseits - andererseits" setzt inhaltlich einen Gegensatz voraus, ich würde eher "sowohl Suchen als auch Einfügen und Löschen" sagen; passt das, oder ist hier wirklich etwas Gegenüberstehendes gemeint?

Ich halte den Artikel "gefühlsmäßig" für 'lesenswert', gebe aber aufgrund fehlender fachlicher Kompetenz nur ein Neutral ab. --Eweht (Diskussion) 12:45, 3. Feb. 2014 (CET)

 keine Auszeichnung Es tut mir leid. Ich habe leider überhaupt nichts verstanden. OK, ich bin kein Informatiker, sondern nur Jurist; das macht die Sache sicher nicht besser. Aber ein exzellenter (oder auch nur lesenswerter) Artikel muss so geschrieben sein, dass sich ein Außenstehender die praktische Bedeutung erschließen kann. Fachtermini müssen jedenfalls ansatzweise im Artikel erklärt werden. Blaulinks reichen da nicht, da ich nicht wegen jedem Kleinkram auf eine andere Seite klicken möchte. Ich kann mir gut vorstellen, dass der Artikel fachlich nicht zu beanstanden ist, aber im Darstellerischen gäbe es noch eine Menge zu tun. Sorry.--Matthias v.d. Elbe (Diskussion) 13:18, 3. Feb. 2014 (CET)

 Lesenswert Von mir gibt’s noch ein Lesenswert. Der Artikel ist sehr ausführlich und erscheint mir fachlich vollständig. Für eine Exzellenzauszeichnung sollte die Einleitung noch etwas laientauglicher werden, und vor allem der Anwendungsabschnitt noch ausgebaut werden, der ist mir momentan auch viel zu listenhaft. Wenn man noch mehr zur Geschichte auftreiben könnte, wäre das sicher auch nützlich für eine Auszeichnung. Ich bin auch kein Freund des sehr langen Anmerkungsabschnitts, da sollte man mMn schauen, ob man nicht das Wichtigste davon in den Haupttext übernimmt bzw. nicht so Relevantes einfach weglässt. Schließlich denke ich, dass noch etwas mehr Grafiken als Verständnishilfe sehr nützlich wären, vor allem in den Abschnitten „Operationen“ und „Implementierung.“ -- HilberTraum (Diskussion) 13:59, 3. Feb. 2014 (CET)

Anmerkungen, um den unsinnigen Forderungen mancher Reviewer gerecht zu werden, halte ich für den falschen weg. Aber  Lesenswert allemal. --Chricho ¹ ² ³ 14:27, 3. Feb. 2014 (CET)

 Lesenswert Eweht hat mit seinen Ausführungen m.E. Recht. Die Allgemeinverständlichkeit kann sich nur auf den Intro-Text beziehen, etliche Artikel hier sind ohne Abi-Leistungskurs Chemie, ohne Grundlagenkenntnisse in Medizin usw. unverständlich. Die Ausführung, dass der AVL-Baum nicht zur Botanik sondern zur Informatik gehört, ist für Leser ohne jede Informatik-Vorkenntnisse hinreichend. Wer mehr wissen will benötigt Grundkenntnisse deren Vermittlung nicht Aufgabe eines einzelnen Enzyklopädieartikels ist.

Der Intro-Text könnte m.E. noch etwas klarer werden. Es sollte deutlich werden, dass die Datenrepräsentation und die definierten Operationen eine Einheit bilden. Der englisch-amerikanische Fachbegriff selfbalancing drückt aus was wir leider umschreiben müssen.

Für einen exzellenten Artikel ist mir die Zahl der Einzelnachweise deutlich zu gering. Ganze Abschnitte ohne Einzelnachweis sind unakzeptabel. Mindestens am Abschnittsende erwarte ich einen Einzelnachweis, der klar Auskunft gibt, mit welchem Buch der Literaturliste und welchen Seiten das überprüft werden kann.

Der Sprachgebrauch ist mitunter suboptimal, z.B. :

• Eine entwickelte Datenstruktur kann nicht altern, gemeint war die früheste bzw. älteste Veröffentlichung der Entwicklung einer Datenstruktur aus der Kategorie balanzierte Bäume.
• Im Gegensatz zu Telefonbüchern: Softwaresysteme bilden keinen Gegensatz zu Telefonbüchern. Ein jährlich erscheinendes gedrucktes Buch und eine kontinuierlich gepflegte elektronische Variante unterscheiden sich u.a. in Zahl und Frequenz der Aktualisierungen.

<hineinquetsch> Das ist von mir. Ich wollte nicht den Gegensatz der Dinge ausdrücken, sondern die Andersartigkeit. Vielleicht wäre dann "Anders als bei Telefonbüchern ..." o.ä. besser. --Eweht (Diskussion) 23:55, 3. Feb. 2014 (CET)

• Der Sprachgebrauch driftet gelegentlich vom enzyklopädischen Stil zum Stil fachwissenschaftlicher Arbeiten. Der Umfang der Anmerkungen und Formulierungen wie "Es sei angenommen..." sind enzyklopädisch m.E. unangebracht.
• Die im Abschnitt #Motivation erwähnte, sehr bekannte Suchstruktur : Überflüssig und "sehr bekannt" ist zudem eine unbelegte Wertung. Die Binäre Suche im Array gilt als Vorläufer der dynamischen Suchbaumstrukturen. reicht.
• großen Einsatzbereich als grundlegende Hilfsmittel : Das ist semantisch undefiniert und darunter kann sich jeder vorstellen was er will. Was ist ein Hilfsmittel in der Informatik und wo ist "großer Einsatzbereich" definiert? Solche Füllformulierungen transportieren keine wirklichen Information und sind verzichtbar.

Für weitere Detailkritik fehlt mir momentan die Zeit.

Im entsprechenden Artikel im englischsprachigen Wiki gibt es eine ausklappbare interne Linkliste (besser als hier Siehe auch) zu allen Baumstrukturen sowie eine externe Linkliste zu Implementierungen der AVL-Struktur in gängigen Programmiersprachen wie C, PHP usw.. Beides halte ich für sinnvolle Ergänzungen.

Insgesamt bewerte ich den Artikel positiv mit genügend Substanz für Exzellenz nach Beseitigung der skizzierten Schwächen bzgl. Sprache und mehr Einzelnachweisen. --Hgn-p (Diskussion) 14:41, 3. Feb. 2014 (CET)

"Die Allgemeinverständlichkeit kann sich nur auf den Intro-Text beziehen" Nö, das stimmt nicht. Wikipedia definiert Allgemeinverständlichkeit für Artikel: Ein guter Artikel in Wikipedia soll verständlich sein. Überprüfe neue Artikel oder Änderungen auf allgemeine Verständlichkeit, siehe Checkliste Verständlichkeit. Menschen ohne einschlägige fachliche Vorbildung sollen den Artikel verstehen können. Sie sollen zumindest die Einleitung sofort verstehen. Bei komplexen Themen sollen sie den Artikel zumindest grob verstehen. Zur Verständlichkeit erforderliche Erklärungen sollen direkt im Artikel gegeben werden. Und genau diese Mindestkriterien erfüllt der Artikel nicht. Selbst der Autor des Artikels gesteht das ein. 79.193.13.138 14:57, 3. Feb. 2014 (CET)

Schau dir doch noch mal genau die Kriterien für lesenswerte Artikel genau an: „Fachjargon wird trotz schlechterer Verständlichkeit toleriert, wenn die Darstellung des Themas ihn erfordert.“ heißt es da. Und oben auf dieser Seite wird in diesem Zusammenhang ausdrücklich auf die Rolle der Einleitung hingewiesen: „besitzen eine verständliche Einleitung, können jedoch aufgrund tolerierter Fachsprache im Detail für Laien unverständlich sein“. -- HilberTraum (Diskussion) 15:13, 3. Feb. 2014 (CET)

wenn die Darstellung des Themas ihn erfordert Es geht auch ohne Fachchinesisch bei diesem Thema (siehe z.B. http://www.ai.wu.ac.at/~koch/courses/wuw/archive/inf-sem-ss-01/pinterits/text.html ). im Detail für Laien unverständlich Hier ist der gesamte Artikel für Laien unverständlich und die Einleitung obendrein (s. Abstimmungen oben). Aber ich schrieb bereits, dass man über eine Lesenswert-Einstufung durchaus streiten kann. Für mich ist Allgemeinverständlichkeit aber das wichtigste Kriterium, für dich mag es das nicht so sein. Vielleicht sollte mal ein Meinungsbild dazu gestartet werden. 79.193.25.30 16:22, 3. Feb. 2014 (CET)

Ein Wikipedia-Artikel ist kein Lehrbuch. Bei deinem Link wird ja gar erst einmal definiert, was ein Baum ist. Das ist nicht Aufgabe des AVL-Baum-Artikels. --Chricho ¹ ² ³ 16:25, 3. Feb. 2014 (CET)

Den zweiten Teil zum AVL-Baum hast du aber auch gesehen, oder? 79.193.56.35 16:31, 3. Feb. 2014 (CET)

 Lesenswert Ich bin auch Jurist aber ein wenig kenne ich mich auch in der Informatik noch aus. Insofern ein m.E. derzeit knappes lesenswert. Die Allgemeinverständlichkeit der Einleitung halte ich NOCH für gegeben. Der Rest naturgemäß fachsprachlich. Ich denke aber da gibt es durchaus noch enormes Verbesserungspotential an Allgemeinverständlich. Formal ist mir negativ die Siehe-auch-Liste aufgefallen. Die bloße Existenz ist imho schon ein Zeichen für Schwächen des Artikels. Verschärft wird die Sache dadurch, dass (fast) alle Links auch schon im Fließtext vorhanden sind. Gruß. --Tavok (Diskussion) 17:53, 3. Feb. 2014 (CET)  Lesenswert Allzu unverständlich finde ich den Artikel nicht. Allerdings ließen sich einige Dinge wirklich einfacher ausdrücken. Dies steht einer Exzellenz-Auszeichnung im Weg. Lesenswert ist der Artikel aber allemal. Gruß Chewbacca2205 (Diskussion) 23:29, 3. Feb. 2014 (CET)

 Lesenswert Der Abschnitt Motivation ist gut gelungen und gibt einen Zugang für die Allgemeinheit. Im Gegensatz zu anderen Meinungen finde ich auch gut, dass das Thema auch fachlich detailiert behandelt wird, ich finde die englische Wikipedia dazu oft vorbildhaft. Mir gefällt die Formatierung nicht ganz, mit Kleingedrucktem und Anmerkungen. Einige Formulierungen sind auch noch sprachlich etwas verbesserungsfähig, könnte man aber eigentlich gleich selbst verbessern ;-). Den Abschnitt Definition könnte man etwas weniger Formelbehaftet schreiben. Derzeit steigt vermutlich der Nichtfachmann an dieser Stelle aus, was nicht sein müsste. Auch könnte man nochmals kurz die Höhe erklären, natürlich wäre ein Beispiel sehr gut. Dennoch: sicher lesenswert.--Jocme (Diskussion) 17:02, 4. Feb. 2014 (CET)

 Lesenswert Diesen Artikel habe ich in den vergangenen Tagen drei Mal vorgenommen, erst heute habe ich mich gezwungen zwei Mal komplett zu lesen. Und ich habe immer noch nicht wirklich durchgeblickt. Ich bin IT-System-Kaufmann, und trotz meiner grottenschlechten Ausbildung hatte ich immerhin Guru-Status bei Dozenten und Mitschülern. Zunächst einmal wären grobe inhaltliche Fehler in den letzten beiden Wochen aufgefallen, sind also wohl keine drin. Die Namen der Entwickler sollten vereinheitlicht werden für Adelson-Velski und Landis sind je zwei Schreibweisen im Artikel, mit den Einzelnachweisen (die bleiben natürlich wie in den Katalogen erfasst) sind es jeweils drei. Dass der Artikel in seiner Gesamtheit für die meisten Menschen völlig unverständlich ist liegt in ganz erheblichem Umfang an der Materie. Er teilt das Schicksal vieler sehr spezieller Themen, sei es Molekularbiologie oder Quantenphysik oder klassische Philologie. WP:OMA-Tauglichkeit um jeden Preis kann nicht der Maßstab sein. Dennoch bin ich der Auffassung, dass die Einleitung stärker auf den Durchschnittsmenschen abzielen sollte, bevor "der Zug abgeht". Das ist es was in meinen Augen ein "exzellent" (noch) verhindert, und was für mich bei anderen Artikeln ein stets willkommener Anlass ist, den Superlativ zu wählen: eigentlich Unerklärbares verständlich zu erklären. Ein exzellenter Artikel muss in meinen Augen alleine stehen können, und dazu gehört auch in der gebotenen Kürze eine Einordnung vorzunehmen und den Begriff "Baum" eben nicht als bekannt vorauszusetzen. Alles andere, der ziemlich anspruchsvolle fachliche Teil nach der Einleitung, der eigentlich unerwünschte Anmerkungsapparat, die angeblich zu vielen "Siehe auch"-Links, sind dem sehr speziellen Thema geschuldet. --Cimbail (Diskussion) 19:45, 4. Feb. 2014 (CET)

 Lesenswert Ich habe mir den Artikel in der aktuellen Version durchgelesen und kenne mich fachlich halbwegs in dem Bereich aus. Hier sind meine Kritikpunkte:

• Einleitung: Zu knapp für einen so langen Artikel. Die Einleitung soll den Artikel zusammenfassen, hier fehlen einige wichtige Inhalte.
• Motivation: Insgesamt zu umständlich beschrieben. Für das Verständnis reicht das Suchproblem (nur Schlüssel) statt dem Wörterbuchproblem (Schlüssel + Wert) aus. Das Fass mit der Speicherplatz-Allokation würde ich an dieser Stelle auch nicht aufmachen. Durch die kurzen Absätze liest sich der Abschnitt etwas zerfleddert.
• Definition: So ist das keine vernünftige Definition. Die Höhenabschätzung ist kein Teil der Definition sondern gehört in einen Abschnitt "Eigenschaften" o.ä. Auch der Nebensatz "wenn es Vorkehrungen gibt" passt nicht so recht in meine Vorstellung einer halbwegs mathematischen Definition. Ich würde das so beschreiben, dass das Wesentliche die AVL-Bedingung ist. Einfügen und Löschen von Knoten wird dann so realisiert, dass die AVL-Bedingung erhalten bleibt. Wenn man informeller bleiben möchte, kann man den Abschnitt auch in "AVL-Kriterium" oder "Balancierungskriterium" umbenennen.
• Eigenschaften: Auf der anderen Seite würde ich mir für die Höhenabschätzung eine Herleitung oder zumindest eine genauere Begründung wünschen. Einiges steht offenbar im Artikel Fibonacci-Baum (habe ich jetzt nur überflogen), wo sich auch viele Inhalte zu AVL-Bäumen finden. Warum stehen die nicht in diesem Artikel, wo sie eigentlich hingehören?
• Operationen: Die einleitenden Sätze sind nicht schön geschrieben. Der Abschnitt zum Suchen ist ziemlich redundant zu Suchbaum. Außerdem ist kein Bezug zu AVL-Bäumen dargestellt. Die Abschnitte Traversieren und Aufsuchen sind ebenfalls nicht gut beschrieben. Auch hier wird kein Bezug zu AVL-Bäumen dargestellt. Bei Binärbäumen von "ganz links" und "ganz rechts" zu sprechen ist unnötig kompliziert, links und rechts reicht völlig aus. Der Fall des Einfügens zwischen zwei inneren Knoten wird nicht ordentlich abgehandelt.
• Rebalancierung: Die Analogie zur Wippe finde ich nicht so günstig, sogar missverständlich, da bei der Rotation sehr viel mehr passiert, nämlich ein Umhängen. Was soll der kleine Text?
• Operationen mit ganzen Bäumen: Die Bilder zur Verkettung und Aufspaltung sind ohne weitere Erklärung nicht verständlich.
• Implementierung: Streckenweise gelten die Aussagen nicht speziell für AVL-Bäume sondern für alle Suchbäume. Die verbleibenden Inhalte lassen sich dann gliederungstechnisch besser zusammenfassen.
• Vergleich mit Rot-Schwarz-Baum: Ich bin mir nicht sicher, ob der Abschnitt hierher gehört. Genauso könnte man im Artikel Rot-Schwarz-Baum einen Abschnitt "Vergleich mit AVL-Bäumen" anlegen. Das ist für mich eher ein Indiz, dass der Abschnitt in einen übergeordneten Artikel gehört.
• Anwendungen: Keine deutschen Sätze.
• Historisches: Der Abschnitt liest sich merkwürdig. Irgendwie fehlt die Historie vor AVL und die Nachfolgeentwicklungen scheinen eher in einen anderen Artikel zu gehören.
• Formales: Die Anmerkungen sind viel zu ausufernd. Entweder die Inhalte sind wichtig, dann gehören sie auch in den Text, oder sie sind unwichtig, dann gehören sie ganz raus und man verweist auf die Literatur bzw. lagert sie in entsprechende Spezialartikel aus. Es gibt zu viele unnötige interne Verweise. Die Hauptartikel-Vorlage wurde falsch verwendet. Die unterschiedlichen Abbildungsgrößen empfinde ich als optisch störend.

Insgesamt beschleicht mich das Gefühl, dass versucht wurde, die eher technischen mathematischen und informatischen Inhalte zum Thema in den Anmerkungen oder anderen Artikeln (z.B. Fibonacci-Baum) zu "verstecken". Das ist meiner Meinung nach der falsche Ansatz. Die Dinge sollen fachlich so beschrieben werden, wie sie sind, ansonsten haben wir hier nur mathematisch/informatische Artikel ohne Mathematik und Informatik. Bevor das eintritt pfeift man lieber auf die Auszeichnungen. Fazit: Ich sehe zwar noch einiges an Verbesserungspotential, erkenne aber die Arbeit an, die in dem Artikel steckt. Daher knapp lesenswert. --Quartl (Diskussion) 22:05, 4. Feb. 2014 (CET)

@Quartl: Danke fürs intensive Studium des Artikels und die Anerkennung. Die Vorschläge sind zahlreich und können nicht so schnell umgesetzt werden (wie manche der obigen). --Nomen4Omen (Diskussion) 10:10, 5. Feb. 2014 (CET)

Schon etwas überfällig. Auswertung: Da manche Stimmen etwas versteckt sind, sind hier alle aufgelistet die ich gefunden habe. Benutzer, die außerhalb der Diskussion keinen Beitrag haben, sind mit * markiert:

• 4 mal keine Auszeichnung: 79.193.x.x*, Syrcro, Jbergner, Matthias v.d. Elbe
• 9 mal lesenswert: Mike1988, Chulia2409 (gut versteckt), HilberTraum, Chricho, Hgn-p, Chewbacca2205, Jocme, Cimbail, Quartl
• 4 mal exzellent: 92.203.36.6*, 178.7.106.45*, Matroid*, Andim
• Bujo kann ich nicht klar zuordnen - er spricht sich anfangs gegen Auszeichnungen allgemein aus, argumentiert später dann aber nur gegen exzellent, und eine klare Stimme fehlt.
• Eweht: "Ich halte den Artikel "gefühlsmäßig" für 'lesenswert', gebe aber aufgrund fehlender fachlicher Kompetenz nur ein Neutral ab"

Die Stimmenzahl reicht also deutlich nicht für exzellent, und deutlich für lesenswert (unabhängig von der Betrachtung der Nur-Abstimm-Accounts). Alle 4 "keine Auszeichnung"-Stimmen kritisieren die Allgemeinverständlichkeit. Allerdings sehe ich keine Chance, einen AVL-Baum in der Einleitung von anderen Bäumen abzugrenzen (was die Einleitung machen muss!), ohne etwas Vorwissen (oder den Klick auf blaue Links) vorauszusetzen. Klar allgemeinverständlich ist die Einordnung in das Fachgebiet: "Der AVL-Baum ist eine Datenstruktur in der Informatik". Ich sehe es daher wie die meisten Auszeichnungsstimmen: Die Fachsprache auch schon in der Einleitung ist nötig und verhindert keine Lesenswert-Auszeichnung.

Ergebnis: lesenswert in dieser Version --mfb (Diskussion) 23:04, 5. Feb. 2014 (CET)

Später Nachtrag zum letzten Absatz von Quartl: Er meint „verstecken“ sicherlich nur in Anführungszeichen. Denn es ist auf keinen Fall „verheimlichen“, es ist ja alles unmittelbar verlinkt und zugreifbar. Zweitens hatte ich in der Version vom 19. Jan. 2014 den expliziten Disclaimer: „Fußnoten ohne besondere Kennung führen zu Einzelnachweisen, solche mit der Kennung ^[Anm] zu Anmerkungen, Detaillierungen, Algorithmen, Beweisen.“, den ein Reviewer herausgenommen hat. Es ist also richtig erkannt, aber auch erklärte Absicht und weiter oben angesprochen, dass der Artikel versucht, ein 2-stufiges Angebot zu machen. Eines für den schnelleren Leser, sagen wir "Gruppe 1", der von dem Thema schon mal gehört hat, oder jemand, der so reinstolpert, und sagt: „Hey, das interessiert mich jetzt geschwind.“ Dann wäre schön, wenn am Ende hängen bliebe: Tabelle oder Binärbaum, dynamisch, effizient, logarithmisch. Vielleicht will er ein bisschen wissen Warum und Wozu? Aber mehr als das Erwähnte und „AVL“ und, dass er notfalls nochmal nachschlagen kann, muss nicht bleiben. Dann gibt es mit Sicherheit auch die "Gruppe 2", die die Abgerundetheit, die „vollständige“ Behandlung des Themas sucht, die ahnt oder weiß, dass man einen solchen Mechanismus irre oft braucht, Teile davon richtig verstehen möchte, in die Anmerkungen geht, die Algorithmen nachvollzieht, die Beweise versteht und die Einzelnachweise in der Präsenzbibliothek nachschlägt. Die "Gruppe 1" ist bestimmt größer als die "Gruppe 2".

Ich habe den Eindruck, dass ein solches 2-stufiges Angebot von der Community als gar zu eigenwillig angesehen wird. (Für mich ist es eine „Grundsatzentscheidung“, wie ich mit dem Artikel weiter verfahre.) (Dabei finde ich z.B. bei Knuth den Satz: „Notmathematical readers, please skip to …“.) M.E. haben die Inhalte in den „Anmerkungen“ zu wenig Eigenständigkeit, sie hängen sehr vom Haupttext ab, als dass sie für Spezialartikel taugen würden. Und doch stützen sie (für mich) Wichtiges im Haupttext. --Nomen4Omen (Diskussion) 18:23, 6. Feb. 2014 (CET)

Ja, die Anführungszeichen waren schon beabsichtigt. Der Punkt ist: der Leser kann fantastisch selbst entscheiden, welche Teile eines Artikels für ihn interessant ist und welche er überspringen möchte. Den einen interessieren vor allem die Operationen, den nächsten die mathematischen Eigenschaften, den dritten die Implementierung und vielleicht die meisten möchten lediglich wissen, was ein AVL-Baum überhaupt für ein Ding ist. Einen längeren Artikel werden die wenigsten Leser in einem Zug von vorne bis hinten durchlesen. Daher ist eine gute Gliederung (die der Artikel auch ansonsten aufweist) so extrem wichtig. Das Setzen wesentlicher Inhalte in Fußnoten hat unter anderem folgende Auswirkungen:

1. Der Lesefluss wird gestört, weil man hin- und herspringen muss.
2. Der Text ist kleiner gesetzt, was das Lesen unnötig erschwert.
3. Der Artikelautor nimmt implizit eine Gewichtung vor, die ihm nicht zusteht.

Allein schon aufgrund des dritten Punkts sollte man hier Fußnoten so weit wie möglich vermeiden. Ein enzyklopädischer Artikel ist keine wissenschaftliche Arbeit und der Autor hat hier vollkommen in den Hintergrund zu treten. Ich würde vorschlagen, einen eigenen Abschnitt "Mathematische Eigenschaften" zu erstellen. Durch die Kapitelüberschrift wird der Leser automatisch gewarnt "Achtung, jetzt kommt Mathematik!" und er kann dann selbst entscheiden, ob er sich den Abschnitt reinzieht oder nicht. Viele Grüße, --Quartl (Diskussion) 15:21, 7. Feb. 2014 (CET)

Parallelisierung

Es ist für Autoren immer ärgerlich, wenn nicht im Review und nicht am Anfang einer Kandidatur Kritik und Beteiligung rege wird, sondern erst auf dem letzten Drücker. So ist es halt in Wiki oft. Ich meine eine Überarbeitung und eine weitere Kandidatur lohnt sich. Anregen möchte ich noch eine Überprüfung der Fachliteratur hinsichtlich Parallelisierung. Anders als früher geht es heute meist ja nicht um den Gesamtaufwand, denn Prozessoren sind weit preiswerter als 1972 und haben meist mehrere Rechnerkerne usw.. Das Antwortzeitverhalten erreicht durch Parallelisierung steht im Vordergrund. Hier stellt sich die Frage, ob es Untersuchungen gibt, die die Struktur und die notwendigen Operationen hinsichtlich Parallelisierung/ Thread-Programierung usw. untersucht haben. --Hgn-p (Diskussion) 13:42, 6. Feb. 2014 (CET)

Gute Frage. Ich muss bekennen, dass ich keine Untersuchung kenne. Bei Ben Pfaff geht es zwar um "System Software", aber von Parallelisierung derselben habe ich nichts gesehen. Die im Abschnitt vorgeschlagene ganz extrem hochgradige Parallelisierung lohnt sich nur, wenn der Baum riesig (oder die Vergleichsfunktion sehr teuer) und die Sperroperation billig ist (Spinlock! – ein Semaphor gilt als sehr teuer). Wenn aber eine Sperroperation so viel kostet wie eine ganze Suche, dann ist es sicherlich billiger, den Baum vor der Suche exklusiv zu sperren, zu suchen, ggf. einzufügen und den Baum zu entsperren.

Mehlhorn erwähnt die „Top-Down-Strategie“. Aber Knuth hat sie auch schon in seinem Suchen-Einfügen-Szenario und findet es vorteilhaft, im Abstieg beim Suchen die Balance-Faktoren schon angeschaut zu haben. Da kann ich überhaupt nicht mit, denn im Mittel ist der Aufstieg deutlich kürzer (konstant) als der Abstieg (log n), fast alle BFen sind also unnötig angeschaut worden. Wo m.E. die Top-Down-Strategie sich wirklich lohnt, ist beim parallelisierten (multi-threading) Suchen-Einfügen-Szenario. (Der Abschnitt Parallelisierung im Artikel deckt also gewissermaßen 2 Punkte ab: Erstens, dass man Top-Down machen kann, und zweitens, wo es sich lohnt.) --Nomen4Omen (Diskussion) 16:55, 6. Feb. 2014 (CET)

Mir fällt noch was ein: Hier und im Artikel habe ich Parallelisierung als Thread-Parallelisierung verstanden, nicht als SIMD-Parallelisierung (Single instruction on multiple data objects). Mehlhorn 2008 führt auf S. 162 aus, dass binäre Suchbäume sich für Letzteres nicht eignen. --Nomen4Omen (Diskussion) 19:00, 6. Feb. 2014 (CET)

Höhe in den Rotationsabbildungen

Bei den Abbildungen zu Einfach- und Doppelrotationen wird die '1' immer abhängig vom dem Startpunktes des Baumes t1 vergeben. In beiden Abbildungen erhöht sich jedoch die Höhe von t1. Ich halte es für sinnvoller, wenn die '1' an der gleichen Stelle bleibt und t1 an Strich 'h + 1' liegt, womit dann die Höhe über die Striche abgebildet wird. --Saqdefaq (Diskussion) 15:44, 10. Nov. 2015 (CET)

Die Anregung ist interessant.

1. Der Baum t1 ist der "Einstiegsbaum" in die Rotation oder der "Orientierungsbaum", dessen Höhe um 2 niedriger ist als die seines Geschwisters. Er ändert sich auch nicht durch die Rotationen.
2. Es ist gut, die Höhenskala von oben nach unten zu ansteigen zu lassen, weil in diese Richtung auch die Höhe der dreieckigen Teilbäume wächst.
3. In allen Skizzen bleibt die Skala in der oberen Hälfte des Rasters stehen, denn die Wurzeln liegen anfänglich und abschließend auf der Höhe 0. In der unteren Hälfte spielen sich die Rotationen ab, somit ist dort ohnehin etwas uneinheitliche Bewegung.

Ich werde das bei Gelegenheit ausprobieren. --Nomen4Omen (Diskussion) 20:32, 10. Nov. 2015 (CET)

Kommentar im Code-Beispiel rotate_RightLeft korrekt?

Als Kommentar ist vermerkt, dass das innere Kind des rechten Kindes des zu rotierenden Knotens, bei einer Einfügung niemals den Balance-Faktor 0 haben kann. Als Beispiel: Man bildet einen Baum mit den Elementen 0, -5, 1, 10, 5. Am Knoten 1 ensteht demnach eine RL-Situation, was eine entsprechende Rotation nötig macht (RL). Der genannte innere Knoten ist in diesem Beispiel die 5, welche an Blatt-Position steht und deshalb den BF = 0 besitzt. Dieser Fall kann also auch bei einer Einfügung vorkommen, oder verstehe ich etwas falsch?

Ich glaube, Du siehst das richtig. Es ist der Fall, bei dem (in Abb. 3 oben) alle 4 Dreiecksbäume t1, t2, t3, t4 die Höhe 0 haben. Die Veränderung geschieht durch Einfügung von Y.

Hat t4 eine Höhe > 0, dann ist die Bemerkung richtig, weil dann nur einer aus {t2,t3} gleich hoch sein kann wie t4, denn sonst wäre schon vor der Einfügung (in genau einen aus {t2,t3}) der Baum unbalanciert gewesen.

Egal, auch der obige Fall der Höhe 0 muss richtig behandelt werden und die Bemerkung raus. --Nomen4Omen (Diskussion) 17:34, 4. Jun. 2018 (CEST)

Soweit ich das sehe, ist das kein AVL-Baum

Ich tippe mal die AVL-Baum-Definition aus "Datenstrukturen und Algorithmen" von Prof. Dr. rer. nat. Ralf Hartmut Güting und Dr. rer nat. Stefan Dieker (ISBN 9783519121213) ab:

"Ein AVL-Baum ist ein binäerer Suchbaum, in dem sich für jeden Knoten die Höhen seiner zwei Teilbäume um höchstens 1 unterscheiden."

Ich vermute, man misst die Höhe von den Blättern aus. Die Höhe des Knoten p ist dann p.height = max(p.left.height, p.right.height)+1. Ich bin aber gerade erst dabei nachzuvollziehen, wie der Algorithmus funktioniert. Hier ist er aber in den Bilder wahrscheinlich falsch angewandt. --2003:C7:173C:46FE:7285:C2FF:FE02:C289 18:16, 3. Mai 2019 (CEST)

Das Zitat ist bis auf den Schreibfehler "binäerer" korrekt.
Auch Deine Formel $\mathrm {Height} (t)=1+\max(\mathrm {Height} (t_{r}),\mathrm {Height} (t_{l}))$ ist korrekt.
Jetzt wäre es schön, wenn Du das Bild und den Knoten darin mit nicht-AVL-Eigenschaft benennen könntest. --Nomen4Omen (Diskussion) 19:40, 3. Mai 2019 (CEST)

Abbildung 1: Der Knoten "J" müsste Balance "+2" haben, und somit beim Einfügen/Löschen rotiert worden sein. --2003:C7:173C:46FE:7285:C2FF:FE02:C289 17:44, 4. Mai 2019 (CEST)

Sorry, ich stimme nicht zu:
Die Knoten haben nach meiner Ansicht die absoluten Höhen:
C=1, D=2, F=3, G=1, J=5, L=2, N=1, P=4, Q=1,S=2, U=1, V=3, X=1.
Somit ist der BF(J) = +1, da H(P)−H(F) = +1. Gruß, --Nomen4Omen (Diskussion) 18:11, 4. Mai 2019 (CEST)

Guten Morgen, ja du könntest Recht haben. Ich habe mich da von dem unausgeglichenen Eindruck des Bildes täuschen lassen, glaube ich. Ich schaue mir den Beweis in dem Buch nochmal an. --84.182.198.130 05:06, 5. Mai 2019 (CEST)

Ich habe mir nochmal den Beweis angeschaut. Da ist die minimale Knotenzahl für die Höhe h N(h) = 1 - N(h-1) + N(h-2). Damit ist das verständlich, dass der Beweis für den genannten Baum gilt. Danke für die Mühe! Gehört der Titel dieses Abschnitts jetzt geändert? Die Frage ist ja beantwortet. --2003:C7:173C:46FE:7285:C2FF:FE02:C289 08:38, 5. Mai 2019 (CEST)

Wie unterscheidet man, ob man bei der Propagation der neuen maximalen Tiefen / Balancefaktoren ...

... aufhören kann? Ich komme zu dem Schluss: Ohne Nachmessen geht es nicht. Ich bin gerade daran, einen AVL-Baum mit Balancefaktoren selbst zu implementieren. Beim Entfernen von Elementen ist mir aufgefallen, dass ich beim Propagieren der Balancefaktoren einen Fehler mache. Die genutzten Werte sind die hier:

std::list<int> input_values{ 9, 8, 1, 2, 7, 6, 3, 4, 5, 14, 11, 13, 12, 10 };

std::list<int> to_remove_values{ 7, 12, 13, 14, 8, 9, 2, 1, 5, 3, 4, 11, 6, 10 };

Ich denke, ich müsste die maximale Tiefe beider Teilbäume jedes Mal nachmessen, um entscheiden zu können, welcher Balance-Faktor grade gebraucht wird. Ich finde keine bessere Abbruchbedingung. --2003:C7:1720:5CD3:7285:C2FF:FE6D:6D5B 07:30, 16. Aug. 2022 (CEST)

Ich glaube, ich bin selbst drauf gekommen. Ich denke, man muss bei Rebalancieren unterscheiden, ob man grade löscht oder einfügt:

• Beim Hinzufügen aufhören, wenn die neue Balance 0 wird,
• beim Löschen aufhören, wenn man
  • von Links kommt und die Balance +1 wird (Sie war vorher 0; Max() ändert sich nicht),
  • von Rechts kommt und die Balance -1 wird (Sie war vorher 0, Max() ändert sich nicht).

Ich bin aber noch am Grübeln, ob ich da wirklich Recht habe. Ich scheue mich wieder vorm Blatt Papier zum Ausprobieren... --2003:C7:1704:B91D:7285:C2FF:FE6D:6D5B 09:30, 19. Aug. 2022 (CEST)

Edit: Die Fälle beim Löschen hatte ich genau falsch rum. --2003:C7:1704:B91D:7285:C2FF:FE6D:6D5B 10:31, 19. Aug. 2022 (CEST)

verzögerter AVL-Baum

@Ostersegler: Auch bei einem nicht so neuen Thema wie deinem wäre es m.E. angebracht gewesen, dass du mit ein bisschen mehr Sorgfalt vorgehst und deinen Text vielleicht sogar selber nochmal durchliest. Mit Formulierungen, Rechtschreibfehlern wie "Das wesentlichen Probleme bei", "AVL-Bäume die völlig ohne Stack oder Rekursion auskommen" oder "Rebalancieren von Knoten erfolg dan" signalisierst du, dass dir das alles (wie auch eine potentielle Leserschaft) sonstwo vorbeigeht, mit der Folge, dass man deinen Beitrag recht gerne ganz einfach wieder rausschmeißen würde. --Nomen4Omen (Diskussion) 10:57, 24. Nov. 2022 (CET)

@Ostersegler: Du hast zwar ein bisschen was korrigiert, aber es sind immer noch lieblos viele Schreibfehler drin. Es kann doch nicht die Welt sein, ein Buch leidlich sauber zu extrahieren – oder? --Nomen4Omen (Diskussion) 21:21, 27. Nov. 2022 (CET)

Meine Oma

hat gerade die Einleitung gelesen und sagt, sie versteht nicht alles zu hundert Prozent. Sonst find ich den Artikel gut. —2A02:8071:52D0:3820:62:4B74:8BA7:FAF6 21:03, 8. Feb. 2023 (CET) 2A02:8071:52D0:3820:62:4B74:8BA7:FAF6 21:03, 8. Feb. 2023 (CET)