⬑ Liste aller flipped lectures.  —  Algorithmen und Datenstrukturen

Lektion 6: Binäre Suchbäume

In dieser Lektion behandeln wir Datenstrukturen um eine dynamische Zuordnung von Werten zu Schlüsseln zu speichern.

Dynamische Abbildungen, auch (dynamic) maps (z.B. java.util.Map), dictionaries (Wörterbücher), symbol tables (ST), associative array (assoziatives Feld) oder key-value stores genannt, sind die vielseitigste und wohl meistverwendete Waffe eines (guten) Programmierers. Einige Programmiersprachen (z.B. Python) verwenden assoziative Arrays sogar als eingebauten Datentyp.

In dieser Lektion lernt ihr die erste von zwei Möglichkeiten kennen, wie man eine solche Abbildungen realisieren kann: binäre Suchbäume (binary search trees (BSTs)). (Die zweite, Hashing, ist Thema von Lektion 7.)

Aufgrund ihrer weiten Verbreitung sind ungeschickt eingesetzte maps ein typisches Einfallstor für performance bugs. Mit einem Grundverständnis von BSTs könnt ihr diese Fallstricke umgehen.

Lernziele

  • Abstrakten Datentyp Map / Symbol Table kennen
  • Operationen und ihre Performancecharakteristika auf binären Suchbäumen kennen
  • Mindestens eine Möglichkeit kennen, die Höhe von Suchbäumen durch Balancierungsmechanismen logarithmisch zu beschränken.

Fragensammlung für die Q&A Session

Tragt hier Fragen ein, die während der Vorbereitung aufkamen, und die ihr gerne klären möchtet. Bewertet außerdem die existierenden Fragen.

Hausordnung
  • Es ist explizit erlaubt/erwünscht, Fragen aus den Aufgaben zur Vorbereitung unter den Videos zu übernehmen, wenn ihr diese der Q&A Session besprechen wollt.
  • Auch wenn ihr gerade keine eigene Frage stellen möchtet, sind die Fragen der anderen oft hilfreiche Denkanstöße auch für euch. Deshalb, und um Fragen für die Q&A Sessions zu priorisieren, könnt ihr Fragen bewerten.
    Tragt dazu bei einer Frage entweder ein (zusätzliches) »+« ein, wenn ihr diese Frage interessant findet, oder ein (zusätzliches) »-«, wenn ihr sie nicht hilfreich findet (z.B. weil die Antwort direkt im Video gegeben wird). Listet zur besseren Übersicht zuerst alle »+«, dann alle »-«, jeweils in 5er Gruppen.
  • Bevor ihr eine neue Frage eintragt, schaut ob eine existierende Frage eurer sehr nahe kommt; wenn ja, schreibt eure Frage als alternative Formulierung zu dieser Frage dazu.
  • Wenn ihr der Meinung seid, ihr könnt eine Frage in wenigen Worten beantworten, so ergänzt eure Antwort unterhalb der Frage. Auch diese Antworten könnt ihr bewerten, wenn ihr sie hilfreich findet, oder Erwiderungen ergänzen, wenn ihr sie für falsch haltet.
  • Seid konstruktiv.

Material

Teil 1, Teil 2, Teil 3, optionale Themen.

Die Videos entstammen dem Coursera MOOC Algorithms Part I von Robert Sedgewick und Kevin Wayne.

Teil 1 – Symbol Table API und elementare Implementierungen

Die ersten Videos beschreiben den abstrakten Datentyp Symbol Table.

1.1 – Symbol Tables: Introduction

Dieses Video beschreibt die Operationen einer Symbol Table (ST), Anforderungen an den fürs keys verwendeten Datentyp sowie einige Anwendungen von STs. Außerdem werden zwei Test Clients vorgestellt, die als elementarer Baustein vieler Anwendungen vorkommen.

Aufgaben zur Vorbereitung:

  1. Welche Operationen hat jede ST?
  2. Was ist der Zusammenhang zwischen dem Begriff einer mathematischen Funktion und einer ST? Was sind die Unterschiede?
  3. Wie sieht eine typische Implementierung von equals auf einem Datentyp mit mehreren Feldern aus? Welche Anforderungen sind dabei zu erfüllen?
  4. Wie verwendet der frequency counter test client eine ST?

1.2 – Elementary Implementations

In diesem Video stellt Sedgewick Listen-basierte Implementierungen der ST API vor, die aber den Laufzeitanforderungen nicht gerecht werden.

Aufgaben zur Vorbereitung:

  1. Welche beiden elementaren Implementierungen werden vorgestellt?
  2. Wie funktioniert für diese get und put?
  3. Welche Laufzeit (order of growth) haben get und put?

1.3 – Ordered Operations

Neben den in Video 1.1 vorgestellten Operationen sind für STs, deren Schlüssel eine Ordnung haben, eine Reihe weiterer Operationen sinnvoll. Diese werden in diesem Video vorgestellt.

Aufgaben zur Vorbereitung:

  1. Welche weiteren Operationen enthält eine Ordered ST?

Teil 2 – Binäre Suchbäume

Dieser Teil behandelt plain-vanilla binary search trees (binäre Suchbäume).

2.1 – Binary Search Trees

In diesem Video wird die Mutter aller effizienten Implementierungen von (ordered) STs und vielleicht bedeutendste Datenstruktur überhaupt vorgestellt: binäre Suchbäume (binary search tree, kurz BST). Der Einsatz von Suchbäumen (BSTs und ihre zahlreichen Varianten) macht in unzähligen Anwendungen den Unterschied zwischen einer einer inpraktikabel langsamen und einer effektiven Methode.

Im Video wird zuerst definiert was ein solcher Baum ist. Dann wird gezeigt, wie man darin suchen und einfügen kann, und schließlich wird die Laufzeit dieser Operationen betrachtet.

Aufgaben zur Vorbereitung:

  1. (Wiederholung:) Was ist ein binary tree (Binärbaum) nach der Definition aus dem Video?
  2. Wann ist ein binary tree ein search tree (Suchbaum)? Malt einen BST mit den Schlüsseln 10,20,30,40,50.
  3. Wie wird ein BST in Java repräsentiert? Malt die Objektrepräsentation als Box-und-Pfeile Diagramm für euren Beispielbaum von oben.
  4. Wie funktioniert die Suche in BSTs? Beschreibt den Vorgang an einem Beispiel.
  5. Wie funktioniert das Einfügen eines neuen Schlüssels? Beschreibt den Vorgang an einem Beispiel.
  6. Wie sieht der best-case Baum für die Suchkosten aus? (Gemeint ist damit typischerweise gemittelt über alle möglichen Schlüssel, die man suchen kann.)
  7. Was sind die maximal möglichen Suchkosten, und wie sieht ein Baum aus, in dem diese Suchkosten auftreten können?
  8. Welche Aussage trifft Sedgewick über die typischen / average-case Suchkosten für BSTs?

2.2 – Ordered Operations

BSTs erlauben auch alle Zusatzoperationen von geordneten STs effizient zu implementieren; dieses Video zeigt wie. Insbesondere wird gezeigt, wie man subtree-size fields aktuell hält und Operationen damit beschleunigt.

Aufgaben zur Vorbereitung:

  1. Wie geht min/max in BSTs?
  2. Wie geht floor/ceiling in BSTs?
  3. Wie hält man die Zähler der Teilbaumgrößen in den Knoten aktuell?
  4. Wie funktioniert rank in BSTs?

Teil 3 – Balancierte Suchbäume

Die BSTs aus Teil 2 sind oft schnell genug, aber nicht immer: unter unglücklichen Einfügereihenfolgen kann ihre Performanz zu der von verketteten Listen degenerieren. Balancierte Suchbäume erzwingen bei jedem Einfügen die Aufrechterhaltung gewisser »Mindeststandards« bzgl. der Baumform und garantieren dadurch logarithmische Suchzeiten auch im worst case. Damit dabei das Einfügen nicht zu aufwendig wird, müssen diese Mindeststandards aber noch ein bisschen »Spiel« lassen. Wie man dies widersprüchlichen Anforderungen erfüllt, ist das Thema dieses Teils.

3.1 – 2-3 Trees

2-3-Bäume erzwingen einerseits perfekte Balancierung des Suchbaums bzgl. der Höhe der Blätter, lassen aber Spiel, indem sie in jedem Knoten einen oder zwei Schlüssel speichern.

Auch wenn direkte Implementierungen von 2-3-Bäumen in der Praxis keine Rolle spielen, stellen sie die konzeptionell einfachsten balancierten Suchbäume dar.

Aufgaben zur Vorbereitung:

  1. Welche Eigenschaften muss ein 2-3-Baum erfüllen? Seid präzise!
  2. Wie funktioniert die Suche in einem 2-3-Baum?
  3. Wie funktioniert das Einfügen in einen 2-3-Baum? Welche Fälle sind zu unterscheiden, und wie werden sie behandelt?
  4. Was garantiert die Balancebedingung von 2-3-Bäumen bzgl. ihrer Höhe?
  5. Welche Gründe nennt Sedgewick, warum 2-3-Bäume selten direkt implementiert werden?

3.2 – Red-Black BSTs

Wichtig: Wir verwenden von diesem Video nur die ersten 7:12 Minuten. Die nachfolgenden Details zu Insert in Rot-Schwarz-Bäumen sind optional.

Rot-Schwarz-Bäume (red-black trees, kurz RB trees) umgehen die Nachteile von 2-3-Bäume bzgl. der Implementierung im Computer, indem sie jeden 3-node durch zwei normale BST nodes (2-nodes) ersetzen, die durch eine rote Kante verbunden sind. Damit lässt sie die Balanceregel von 2-3-Bäumen indirekt auch in BSTs aufrechterhalten. In der Praxis sind Rot-Schwarz-Bäume die erfolgreichse BST-Variante; so sind sowohl Javas TreeMap, als auch std::map aus der C++ Standard Template Library Implementierungen von Rot-Schwarz-Bäumen.

Durch diese zwei Levels (die Regeln von 2-3-Bäumen und deren Abbildung auf normale Suchbäume) sind Rot-Schwarz-Bäume die wohl komplexeste Datenstruktur, die wir in A&DS behandeln. Wir beschränken uns in dieser Vorlesung deshalb darauf, festzustellen, dass man konzeptionell lediglich die Operationen auf 2-3-Bäumen im Rot-Schwarz-Baum simulieren muss.

Aufgaben zur Vorbereitung:

  1. Was ist ein left-leaning red-black tree? Seid präzise!
  2. Was ist der genaue Zusammenhang zwischen 2-3-Bäumen und diesen? Seid präzise!

Optionale Themen

Hier sind einige Videos mit weiterführenden Inhalten und hübschen Anwendungen gesammelt. Diese sind nicht Teil (des Klausur-relevanten Stoffes von) von A&DS. Sie sind hier gesammelt, weil in den Videos oben teilweise Bezug auf diese Themen genommen wird, und ich Interessierten die Videos nicht vorenthalten möchte.

Deletion in BSTs

Bisher haben wir nur Elemente in BSTs eingefügt, und sie (auf vielfältige Weise) durchsucht. Dieses Video demonstriert, wie man einen Schlüssel/Knoten wieder löschen kann. Anders als beim Einfügen gibt es für das Löschen Wahlmöglichkeiten, die sich auf die mittlere Form der Bäume auswirken.

B-Trees

B-Bäume (B-trees) sind Verallgemeinerungen von 2-3-Bäumen, bei denen noch mehr Schlüssel pro Knoten erlaubt sind. Dadurch lässt sich die Höhe des Baumes nochmals deutlich reduzieren. B-Bäume sind das Mittel der Wahl für große Datenmengen, die auf nicht mehr in den Hauptspeicher passen, sondern auf langsameren Sekundärspeichern wie Festplatten ausgelagert werden müssen. So sind Varianten von B-Bäumen für Indizes in Datenbanken das Mittel der Wahl.