Einfügen mit Rebalance

Intermediate Algorithmen und Datenstrukturen Deutsch

Also available: English

Created by Best · 16.08.2026 at 09:13 UTC

Einfügen folgt dem Suchpfad wie im BST, hängt den Knoten als Blatt ein und steigt zurück. An jedem Vorfahren prüft man den Balancefaktor und rotiert bei Bedarf.

Aufgabe: berechne die Höhe eines Knotens aus den Kindhöhen.

Wo gebraucht

Online-Indizes: jede Mutation muss die Invariante reparieren. Gleiches Denkmuster in anderen selbstorganisierenden Strukturen.

Vertiefung

Zunächst wird nach der normalen Suchbaumregel ein Blatt eingefügt. Danach läuft die Reparatur den Suchpfad rückwärts, aktualisiert Höhen und prüft die lokale Balancebedingung.

Der Fall ergibt sich aus der Richtung zum schweren Kind und der Richtung innerhalb dieses Kindes. Stimmen beide Richtungen überein, genügt eine Rotation; andernfalls wird eine Doppelrotation ausgeführt.

Nach der Rotation muss der reparierte Teilbaum wieder korrekt in seinen Elternkontext eingesetzt werden. Bei rekursiven Implementierungen ist es deshalb hilfreich, aus jeder Methode die möglicherweise neue Teilbaumwurzel zurückzugeben.

Schwierigkeitsstufen

Suchpfad und neue Blattposition bestimmen.
Rotationsfall aus zwei Richtungsentscheidungen ableiten.
Eine rekursive Methode mit Rückgabe der Teilbaumwurzel entwerfen.

Fallstricke

Wer Höhen vor der strukturellen Änderung berechnet, verwendet veraltete Werte. Gleichheitsschlüssel brauchen zudem eine feste Regel, sonst kann die Suchinvariante uneindeutig werden.

University approvals: 0

Tasks

Question 1

Implementiere height(Node): null -> -1, sonst 1 + max(left, right).

Hint

Prüfe zuerst n == null. Für den grösseren zweier Werte stellt Java Math.max(int, int) bereit.

public class AvlHeight {
  static class Node {
    int value; Node left; Node right;
    Node(int value) { this.value = value; }
  }
  public static int height(Node n) {
    // TODO
    return 0;
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Question 2

Warum gibt eine rekursive AVL-Einfügemethode oft die Teilbaumwurzel zurück?

Weil Rotationen die Wurzel dieses Teilbaums ändern können.

Weil jeder Schlüssel an die Gesamtwurzel gehört.

Weil Höhen nicht gespeichert werden dürfen.

Weil Rekursion keine Parameter verändern kann.

Card Info

Topic: Algorithmen und Datenstrukturen
Difficulty: Intermediate
Completed: 0 users

Creator

Best

BestBuddy