In Bezug auf Spreizbäume

Question

Ich lese über Spreizbäume in Datenstrukturen und Algorithmen durch Mark Allen Weses

Die Spreizstrategie ähnelt der Rotationsidee, außer dass wir etwas selektiver darüber sind, wie Rotationen durchgeführt werden. Wir werden immer noch den Boden entlang des Zugangspfades drehen. Sei X ein (Nicht -Root) Knoten auf dem Zugangspfad, auf dem wir drehen. Wenn das Elternteil X die Wurzel des Baumes ist, drehen wir nur x und die Wurzel. Dies ist die letzte Rotation entlang des Zugangspfads. Andernfalls hat X sowohl ein Elternteil (P) als auch einen Großelternteil (G), und es gibt zwei Fälle plus Symmetrien zu berücksichtigen. Der erste Fall ist der Zick-Zack-Fall, hier ist x ein rechtes Kind und P ist ein linkes Kind (oder umgekehrt). Wenn dies der Fall ist, führen wir eine doppelte Rotation durch, genau wie eine AVL -Doppelrotation. Andernfalls haben wir einen Zick-Zig-Fall: X und P sind entweder linke Kinder oder beide rechten Kinder.

Was bedeutet der Autor im obigen Text mit der folgenden Aussage "Es gibt zwei Fälle plus Symmetrien"? Zwei Fälle sind gegeben, aber was sind Symmetire hier?

Vielen Dank!

Answer 1

Ich denke, es ist nur eine ziemlich grundlegende axiale Symse:

Beispiel für einen Zick -Zag -Fall, hier sind 2 symetriale Bäume:

     g
    / \ 
    p  d
   /\
  c  x
    / \
   a   b

     g
    / \ 
   d   p
      /\
     x  c
    / \
   a   b

Answer 2

Angenommen, ein Fall lautet: "Wenn der Knoten in Fragen das rechte Kind seines Elternteils ist und der Elternteil das linke Kind des Großelternteils ist", führen Sie in diesem Fall eine linke Rotation und dann eine rechte Rotation durch. Der Knoten wird also zum großen Elternteil kommen.

Der symmetrische Teil dieses Falls lautet: "Wenn der Knoten in Fragen das linke Kind seines Elternteils und das Elternteil das rechte Kind des Großelternteils ist", führen Sie in diesem Fall eine rechte Rotation und dann eine linke Rotation durch. Der Knoten wird also zum großen Elternteil kommen.

Ersetzen Sie links durch rechts und rechts. Links erhalten Sie den symmetrischen Gehäuse.

Es gibt nur 3 Fälle zur Rotation in einem Spreizbaum. Listete es auf hierSie können den Laufzeitunterschied bei der Suche mit und ohne Spreiz sehen.