AVL Bäume + Rotation
HTML-код
- Опубликовано: 4 сен 2016
- Lösung: deprecated.bleeptrack.de/tuto...
-------------------------------------
hat dir eines meiner Videos gefallen?
Über etwas Unterstützung würde ich mich sehr freuen!
www.bleeptrack.de/unterstuetzen/ - Наука
Es ist einfach immer wieder erstaunlich, wie viele gute Erklärungen( und Wissen im Allgemeinen) heute einfach (und kostenlos!) verfügbar sind.
Vielen Dank für deine Arbeit! :)
Ist Wissen nicht grundsätzlich kostenlos?
@@NightcoreAsuna_music Jaein. Für Wissen aus dem Internet brauchst du ein internetfähiges Gerät, Strom, Internet. Kostet alles. Obdachlose haben das nicht und somit keinen Zugriff auf Bildung/Wissen, genau so wie in armen Staaten wie Afrika.
Hat mir in letzter minute vo der klausur das Leben gerettet! kann dir gar nicht genug danken
Du hast mir den Tag gerettet! Super Erklärung :)
Ah AVL-Bäume erinnert mich an das Modul Algorithmen und Datenstrukturen, dass waren noch Zeiten :P
Furchtbare Zeiten sind das...
Aber hallo
dem muss ich mich nun stellen :D Nur der Theorieteil geht...
Genau darin schreib ich morgen eine Klausur.
Hab in der Vorlesung gar nichts verstanden, RUclips hilft mir doch sehr :D
@@timojohn9773 auch hier?
Schaue das Video in 2020 und hab dadurch endlich alles verstanden 👍🏻👍🏻 Danke
Danke Bleepy für das hilfreiche Video! :)
Das hast du echt gut erklärt, vielen Dank!
Wieder mal Absolut spitze vielen vielen Dank :D
klasse video!
einfach und anschaulich erklärt.
mir hat's geholfen
Stimmt
Ich habe mir schon mehrere Videos zu diesem Thema angeschaut, aber keines hat für mich so einen großen Aha-Effekt verursacht wie dieses hier. Vielen Dank.
Vielen lieben Dank für deine tollen Videos! Anschaulich und gut erklärt - Die haben mir die Klausur gerettet :)
Hat mega geholfen! Tausend dank dir! :)
Hat mir echt geholfen im pädagogik master, Vielen Dank.
Wow danke für die mega Erklärung!
Hab jetzt einige Videos von dir gesehen und schreibe mal einfach unter das hier. DANKE!!
Du rettest mir den Arsch in Algorithmen und Datenstrukturen. Sehr gut und anschaulich alle erklärt :)
Hey, deine Videos haben mir sehr gut in Algorithmen und Datenstrukturen geholfen für das Verständnis. Die waren so hilfreich, dass ich in der Klausur eine 1,7 geschrieben habe!
Besten Dank dass du die Themen so gut erklären kannst! Ich werde dich weiterempfehlen! :D #Ehrenfrau
Freut mich sehr! 🎉
Danke für das video! Aber ich hätte da ne frage zu der aufgäbe ganz am ende, undzwar beim löschen eines Knoten mit 2 kinder wird der knoten doch mit dem Inorder Nachfolger ersetzt. Das wäre doch die 12 in dem fall warum hast du bei der Lösung die 9 benutzt?
Was würden wir nur ohne dich machen Bleeptrack?!
Frage zu deiner Aufgabe am Ende des Videos. Müsste im rechten Teilbaum nach deiner Definition nicht auch
17 mit Wert -2 und 13 mit Wert 0 rotiert werden. Du hattest bei den Links & Rechts Rotationen ja geschrieben das es bei 2 und 1/0 der Fall wäre und auch stellvertretend für -2 und 1/0.
Das kann ja eigentlich nicht sein, oder übersehe ich einen Fall wo das eintreten würde?
Super erklärt! :-)
Sehr gutes Video
!
Hey könntest du auch ein Video zum rot schwarz Baum machen? Vielen Dank im Voraus
Moin Moin :) ich hätte eine Bitte an dich . Könntest du noch ein Video zu 2-3-4 Bäumen machen ? In den Videos die man so findet labern die alle zu viel . Ich hab mir deine Videos zu Sortieralgorithmen angeschaut und fand die super . Kein Schnick-Schnack , keine nervige Musik und man kann deine Schrift gut lesen =D Ich finde es besonders gut das du keine Zwischenschritte überspringst, auch wenn in dem Schritt nichts passiert.
Für das Beispiel bei 10:00 - einfache Rotationen funktionieren in beide Richtungen. Also könnte man auf der rechten Seite der Folie ein statt ein -> schreiben. Dann ist das Beispiel auch weniger verwirrend! :)
Sehr gutes Video! Insbesondere die Beispiele!
danke, jetzt kann die AUD prüfung kommen ;)
Finde das video gut wenn man schon sich bisschen mit Bäumen auskennt aber glaube es ist verwirrend für andere weil es gespiegelt ist in der Hilfestellung
Richtig nice!
herrlich erklärt!
Ich habe ne Frage ich hoffe du siehst das: Warum hat der Rote Teil oben rechts den Balance Faktor 2? Weil links davon ist ein Kind und rechts davon geht es um 2 nach unten oder übersehe ich etwas? (Also ich würde den Balance Faktor 1 geben (2 rechts - 1 links)) (6:00)
Edit: Wolltest du vllt das ganze einfach nur übersichtlich gestalten und hast deswegen die Blätter b,c nicht ganz spezifiziert?
Genau: auf der rechten Seite sind Beispiele (oder vllt besser Ausschnitte) aus Bäumen und einer möglichen Faktorbelegung. a,b,c,d sind stellvertretend für die Baumteile darunter.
Bleeptrack danke für die schnelle Antwort und das Video allgemein ohne solche Videos wäre meine Lernmotivation im Keller :p
Habe es in keinem RUclips Video gerallert, nicht ind er Vorlesung, nicht in der Übung... Aber jetzt :D Daumen hoch (Y)
Kannst du mir bitte erklären warum die 9 ganz oben landet, nachdem man die 10 löscht und nicht z.b. die 7 oder 17? LG
Beim löschen der 10 musst du diese durch ihren Nachfolger bzw. Vorgänger ersetzen... das wäre in dem Fall die 9 (Maximum des linken Teilbaums) oder die 12 (Minimum des rechten Teilbaums)
Vielen Dank! Das wird mir hoffentlich in meiner Info-Nebenfach-Klausur helfen. Ist das so gewollt, dass man die Lösung nur über URL-Manipulation auf deiner Homepage findet oder ist das ein Fehler? Oder etwas gar ein Fehler meines Browsers?
+Amon Melchers Hey, das sollte natürlich nicht so sein. Du hast genau die paar Stunden erwischt an dem ich mein Blogtheme umstelle. Im Lauf des nächsten Tages sollte alles wieder passen ;)
Danke dir! Hab sogar extra für dich AdBlock ausgemacht ;)
klasse, du!
Einfach besser erklärt als meine Profs....
hey danke für die Hilfe ! Ich hätte ein weiteres Problem, welches in der Klausur gefragt war: Gegeben ist ein AVL-Baum mit der Tiefe 5. Wie viele Schlüssel sind minimal notwendig und wie viele maximal möglich? Begründen! Wie kann ich das denn mit einer beliebigen gegebenen Tiefe lösen? Finde dazu nichts brauchbares. Danke schonmal ! =)
+oOhaMiOo Hey, wenn du nichts findest, dann am besten Mal englisch googeln ;) Die rekursive Formel für die minimalen Knoten im AVL Baum: S(h) = S(h-1) + S(h-2) + 1 mit S(1)=0 und S(2)=1. Die maximale müsste die normale Formel für den Binärbaum sein.
danke dir =)
Hallo bleeptrack, beim letzten Teil ab Minute 17:49 ist doch ein Fehler unterlaufen? Ist hier 19 nicht unser a und 12 unser d?
Du meinst weil man das Schaubild rechts spiegeln müsste, würde d,c,b,a stehen? Das sind ja nur Bezeichner ;) wichtig ist, dass sie Reihenfolge der Blattknoten nicht geändert wird.
hast du beim letzten beispiel nicht den a und d knoten vertauscht?
Ja, die 12 wäre d die 19 a und die 16 b
Wenn ich einen "Schlüssel" in einen AVL Baum einfüge muss heißt das, dass ich einfach einen weiteren Knotenpunkt einfüge? Hab die Folgende Aufgabe und weiß nicht wirklich was dieses i(4) usw bedeutet.
+Naked Asian Genau: Schlüssel sind beim AVL Baum einfach nur ein Knoten. Was dein i(4) bedeutet, kann ich dir ohne Kontext leider auch nicht sagen. Wahrscheinlich steht das i aber für insert und du sollst eine 4 in den Baum einfügen.
Danke für die Antwort! Hab nur einmal einen Screenshot von der Aufgabe aber denke mal dass das schon so stimmt :) gyazo.com/c2754db683c87d7ffcfc237b2e642d7e
+Naked Asian Jop, einfach einfügen :)
Das vorgestellte Schema ist sehr hilfreich und es ist auch gut erklärt. Allerdings gibt es hier zwei Fehler/Irrtümer zu korrigieren, die im Zusammenhang mit AVL-Bäumen schnell passieren können. Erstens, liegt im Bild 1 ein kleiner Fehler vor (Fall: Einfüge-Operation im rechten Teilbaum des grünen Knotens) . Nach einer Einfüge-Operation und der daraus resultierenden Verletzung der Balance-Bedingung beim roten Knoten können die Werte 2 (für rot) und 0 (grün) nicht auftreten, lediglich die Werte 2 (für rot) und 1 (für grün). Zweitens, wird im Video an der Stelle 12:47 behauptet, dass sich nach einer Einfüge-Operation und einer anschliessenden Ausgleichs-Operation unter Umständen weitere Balancewerte im Baum geändert werden müssten. Wenn die Balance-Bedingung durch eine Einfüge-Operation verletzt wird (hier beim Knoten mit Schlüssel 5) und anschliessend durch eine Rotation oder Doppelrotation wieder hergestellt wird (damit ist der Balancewert des Knotens mit Schlüssel 3 auf 0 gesetzt), müssen garantiert keine weiteren Änderungen von Balancewerten im Baum vorgenommen werden (auch nicht weiter oben im Baum). Die restlichen Werte sind alle korrekt.
Hallo Sabine,
zunächst eine Million Mal dankeschön für die Videos. Sie erklären in 5 Minuten was mein Prof. in einem Semester nicht erklären kann. Welche Software bentzt du für's Zeichnen?
+Rod Trendy Dankeschön :) die Software heißt Krita und ist open source. Kann ich sehr empfehlen.
Was jetzt, du oder Sie? :D
Ich schau mir das gerade an und muss sagen, top video, es gibt allerdings etwas was das ganze noch einfacher macht.
Es gilt ja immer die Bedingung das das rechte Kind größer ist als die Wurzel und das linke Kind kleiner ist, demnach wenn man rotationen macht, kann man sich auch einfach daran orientieren, wie die Bedingungen erfüllt werden, so muss man sich das nicht mit dem Farben merken :)
Hmm, ich bin immer noch zu doof dazu. Muss ich jetzt diese bunten Kringel und a,b,c,d auswendig lernen?
DANKE!
Here is the right formula to calculate the balance factor: Height of the left subtree subtracted by the height of the right subtree. Therefore, your negative integers should be positive.
on wikipedia it is done by doing height(right) minus height(left) too though....
@@RagbagMcShag I am so confused. Our prof said Heigt of left subtree - height of right subtree, but this video and wikipedia saying something else
@@rudstar8254 It doesn't matter, the result is the same. So just do what the prof said. Although you probably already wrote your exam 😅
Mir hat das Video leider gar nicht geholfen. Die Spiegelung hat mich rausgeworfen. Besser wäre ein Bsp. gewesen, das genauso wie die Rotationen aussehen, um es nachzuvollziehen.
Ich finde du solltest mehr die genauen Schritte zeigen. Vor allem zwei Rotationen nacheinander sind somit besser nachvollziehbar.
Ich grüße alle aus dem IntroProg Kurs der TU Berlin
naja. links und Rechtsrotation wurden nicht ausführlich erklärt.
Thx
ich küss dein auge