Linker Baum - Wikipedia

In der Informatik ist ein linker Haufen oder eine Prioritätswarteschlange, die mit einer Variante eines binären Heaps implementiert ist. Jeder Knoten hat einen s-Wert der die Entfernung zum nächstgelegenen Blatt ist. Im Gegensatz zu einem Binärhaufen versucht ein linker Baum sehr unausgewogen zu sein. Neben der Heap-Eigenschaft werden linke Strukturen beibehalten, sodass der rechte Nachkomme jedes Knotens den niedrigeren s-Wert hat.

Der höhenabhängige linke Baum wurde von Clark Allan Crane erfunden. ^[1] Der Name stammt von der Tatsache, dass der linke Teilbaum normalerweise höher ist als der rechte Teilbaum.

Ein linker Baum ist ein zusammenlegbarer Haufen. Wenn Sie einen neuen Knoten in eine Baumstruktur einfügen, wird eine neue Baumstruktur mit einem Knoten erstellt und in die vorhandene Baumstruktur eingefügt. Um ein Element zu löschen, wird es durch die Zusammenführung der linken und rechten Unterbäume ersetzt. Beide Operationen benötigen O (log und ) Zeit. Bei Insertionen ist dies langsamer als bei Fibonacci-Heaps, die die Insertion in O (1) (konstanter) Amortisationszeit und O (log n ) im schlechtesten Fall unterstützen.

Linke Bäume sind vorteilhaft, weil sie sich schnell verbinden können, im Vergleich zu binären Haufen, die ( n ) benötigen. In fast allen Fällen ist das Zusammenführen von Skew-Heaps besser. Das Zusammenführen linker Haufen hat jedoch die ungünstigste Komplexität von O (log n ), während das Zusammenführen von Skew-Heaps nur die Komplexität von O (log n [19459006) amortisiert hat.

Der übliche linke Baum ist ein ^{[1] [1] [1]} Es können jedoch auch andere Vorurteile vorhanden sein, wie zum Beispiel der linksgerichtete . S-Wert [ edit ]

S-Werte eines linken Baums

Der S-Wert (oder Rang ) von a Knoten ist die Entfernung von diesem Knoten zum nächsten fehlenden Blatt. Anders ausgedrückt ist der s-Wert eines null Kindes implizit null. Andere Knoten haben einen s-Wert, der um das Minimum der s-Werte ihrer Kinder gleich ist. Somit haben im Beispiel rechts alle Knoten mit mindestens einem fehlenden Kind einen s-Wert von 1, während Knoten 4 einen s-Wert von 2 hat, da sein rechtes Kind (8) einen s-Wert von 1 hat.

Zusammenführende höhenabhängige linke Bäume [ edit ]

Wenn ein Min-Heap angenommen wird, wählen Sie den Knoten mit dem niedrigeren Wert als Wurzel aus, und fügen Sie den Knoten mit dem höheren Stamm zusammen rechter Teilbaum.

Vergleichen Sie nach dem Zusammenführen die s-Werte (Höhen) der resultierenden Kinder. Tauschen Sie sie gegebenenfalls aus, damit der s-Wert des linken Kindes mindestens so groß ist wie der des rechten Kindes. (Wenn ein Kind fehlt, sollte es das richtige sein.) Aktualisieren Sie dann den S-Wert der Wurzel, um einen mehr als den des rechten Kindes.

Java-Code zum Zusammenfügen eines linken, minimalen Höhenbaums [ edit ]

 public   Node   merge  Node   x [19659021]  Node   y )   {    if   ( x   ==   null ) ; ] y ];     if   ( y   ==   null )        return   x  // wenn dies der Fall ist wäre ein Max-Heap, dann wäre die nächste Zeile    : if (x.element <y.element)     if   ( x .  element   vergleichenTo  ( y .  element )  >   0 )   {x 19659065] // x.element > y.element       Knoten   temp   =   x ;       x   =   y  y   y   =   =   ] temp ;    }      x .  rightChild [19659028] =   mischen  ( x .  rightChild   y  wenn   ].  leftChild   ==   null )   {      // linkes Kind ist nicht vorhanden. Bewegen Sie das rechte Kind nach links.       x        leftChild   =   x .  rightChild ;       x .  right   null  ; 19659101] // xs war und bleibt 1    }   else   {      // Das linke Kind ist vorhanden. Vergleichen Sie also die S-Werte   (19659028] x .  leftChild .      x .  RightChild       ]   temp   =   x .  leftChild ]         x .  leftChild      .  RightChild ;         x [19659021].  rightChild   =   temp ;      }       // Da wir wissen, dass das rechte Kind den niedrigeren s-Wert hat, können wir nur       // hinzufügen Eins zu seinem s-Wert       x .  s   =   x .  rightChild .   s   +   1 ;    }     return   x ;  }  

Varianten [ [19599014]

existieren, die nur geringfügige Änderungen am grundlegenden Algorithmus vornehmen:

• Die Wahl des linken Kindes als das größere ist willkürlich; ein "rechter Baum" würde genauso gut funktionieren.
• Es ist möglich, das Tauschen von Kindern zu vermeiden, stattdessen zu notieren, welches Kind das höchste ist (in zum Beispiel das niedrigstwertige Bit des value) und verwenden Sie das in der Zusammenführungsoperation.
• Der s-Wert, der verwendet wird, um zu entscheiden, auf welcher Seite mit der Zusammenführung eine andere Metrik als die Höhe verwendet werden soll. Zum Beispiel könnte die Gewichtung (Anzahl der Knoten) verwendet werden.

Initialisierung eines linksabhängigen Baums mit Höhenverschiebung [ edit ]

Initialisierung einer minimalen HBLT - Teil 1

Initialisierung einer Höhe Der voreingenommene linke Baum wird auf zwei Arten ausgeführt. Die erste besteht darin, jeden Knoten einzeln zu einer HBLT zusammenzuführen. Dieser Prozess ist ineffizient und dauert O ( nlogn ). Der andere Ansatz ist die Verwendung einer Warteschlange zum Speichern jedes Knotens und der sich daraus ergebenden Baumstruktur. Die ersten beiden Elemente in der Warteschlange werden entfernt, zusammengeführt und wieder in die Warteschlange gestellt. Dies kann eine HBLT in der Zeit O ( und ) initialisieren. Dieser Ansatz wird in den drei mitgelieferten Diagrammen detailliert beschrieben. Ein linker Baum mit Mindesthöhe wird angezeigt.

Um eine minimale HBLT zu initialisieren, platzieren Sie jedes Element, das der Baumstruktur hinzugefügt werden soll, in einer Warteschlange. Im Beispiel (siehe Teil 1 links) wird die Menge der Zahlen [4, 8, 10, 9, 1, 3, 5, 6, 11] initialisiert. Jede Zeile des Diagramms stellt einen anderen Zyklus des Algorithmus dar und zeigt den Inhalt der Warteschlange. Die ersten fünf Schritte sind leicht zu befolgen. Beachten Sie, dass die neu erstellte HBLT am Ende der Warteschlange hinzugefügt wird. Im fünften Schritt tritt das erste Auftreten eines s-Werts größer als 1 auf. Der sechste Schritt zeigt zwei miteinander verschmolzene Bäume mit vorhersagbaren Ergebnissen.

Initialisieren einer min HBLT - Teil 2

In Teil 2 wird eine etwas komplexere Verschmelzung durchgeführt. Der Baum mit dem niedrigeren Wert (Baum x) hat ein rechtes untergeordnetes Element. Daher muss die Zusammenführung erneut in dem Teilbaum aufgerufen werden, der vom rechten untergeordneten Element von Baum x und dem anderen Baum verwurzelt ist. Nach dem Zusammenführen mit dem Teilbaum wird der resultierende Baum wieder in Baum x eingefügt. Der s-Wert des rechten Kindes (s = 2) ist jetzt größer als der s-Wert des linken Kindes (s = 1), daher müssen sie ausgetauscht werden. Der s-Wert des Wurzelknotens 4 beträgt jetzt ebenfalls 2.

Initialisieren einer min HBLT - Teil 3

Teil 3 ist der komplexeste. Hier rufen wir rekursiv zweimal die Zusammenführung auf (jedes Mal mit dem Teilbaum des rechten Kindes, der nicht ausgegraut ist). Hierbei wird derselbe Prozess wie für Teil 2 beschrieben verwendet.

Referenzen [ edit ]

1. ^ ^{a b} Crane, Clark A. (1972), Lineare Listen und Prioritätswarteschlangen als ausgeglichene binäre Bäume (Dissertation), Institut für Informatik, Stanford University, ISBN 0-8240-4407-X, STAN-CS-72-259
2. ^ Seonghun Cho; Sartaj Sahni (1996), "Weight Voreingenommene Leftist Trees und Modified Skip Lists" (PDF) Journal of Experimental Algorithmics 3 CiteSeerX 10.1 .1.13.2962 doi: 10.1145 / 297096.297111

Externe Links [ edit