[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki32\/2021\/09\/01\/linker-baum-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki32\/2021\/09\/01\/linker-baum-wikipedia\/","headline":"Linker Baum \u2013 Wikipedia","name":"Linker Baum \u2013 Wikipedia","description":"Priorit\u00e4tswarteschlange implementiert mit einer Variante eines bin\u00e4ren Heaps In der Informatik, u linker Baum oder linker Haufen ist eine Priorit\u00e4tswarteschlange,","datePublished":"2021-09-01","dateModified":"2021-09-01","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki32\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki32\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/c\/ce\/Leftist-trees-S-value.svg\/220px-Leftist-trees-S-value.svg.png","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/c\/ce\/Leftist-trees-S-value.svg\/220px-Leftist-trees-S-value.svg.png","height":"137","width":"220"},"url":"https:\/\/wiki.edu.vn\/wiki32\/2021\/09\/01\/linker-baum-wikipedia\/","wordCount":5170,"articleBody":"Priorit\u00e4tswarteschlange implementiert mit einer Variante eines bin\u00e4ren Heaps In der Informatik, u linker Baum oder linker Haufen ist eine Priorit\u00e4tswarteschlange, die mit einer Variante eines bin\u00e4ren Heaps implementiert ist. Jeder Knoten x hat ein s-Wert das ist der Abstand zum n\u00e4chsten Blatt im Teilbaum mit Wurzel x.[1] Im Gegensatz zu a bin\u00e4rer Haufen, versucht ein linker Baum, sehr unausgeglichen zu sein. Zus\u00e4tzlich zur Heap-Eigenschaft werden linke B\u00e4ume beibehalten, sodass der rechte Nachkomme jedes Knotens den niedrigeren s-Wert hat.Der h\u00f6henorientierte linke Baum wurde von Clark Allan Crane erfunden.[2] Der Name kommt daher, dass der linke Teilbaum normalerweise h\u00f6her ist als der rechte Teilbaum.Ein linker Baum ist ein zusammenf\u00fcgbarer Haufen. Beim Einf\u00fcgen eines neuen Knotens in einen Baum wird ein neuer Ein-Knoten-Baum erstellt und mit dem bestehenden Baum zusammengef\u00fchrt. Um ein Element zu l\u00f6schen, wird es durch die Zusammenf\u00fchrung seiner linken und rechten Unterb\u00e4ume ersetzt. Beide Operationen ben\u00f6tigen O(log n) Zeit. Bei Einf\u00fcgungen ist dies langsamer als bei Fibonacci-Heaps, die das Einf\u00fcgen in O(1) (konstante) amortisierte Zeit unterst\u00fctzen, und O(log n) schlimmsten Fall. Linke B\u00e4ume sind aufgrund ihrer F\u00e4higkeit zur schnellen Zusammenf\u00fchrung von Vorteil, im Vergleich zu bin\u00e4ren Heaps, die \u0398(n). In fast allen F\u00e4llen hat das Zusammenf\u00fchren von Schr\u00e4gstapeln eine bessere Leistung. Das Zusammenf\u00fchren von linken Haufen hat jedoch den schlimmsten Fall O(log n) Komplexit\u00e4t beim Zusammenf\u00fchren von schr\u00e4gen Haufen hat sich nur O(log n) Komplexit\u00e4t.Der \u00fcbliche linke Baum ist a h\u00f6henabh\u00e4ngig linker Baum.[2] Es k\u00f6nnen jedoch auch andere Verzerrungen bestehen, wie z gewichtsabh\u00e4ngig linker Baum.[3]Table of ContentsS-Wert[edit]Operationen an einem h\u00f6henverzerrten linken Baum[1][edit]Zusammenf\u00fchren von zwei Min HBLTs[edit]Pseudocode zum Zusammenf\u00fchren von zwei min-H\u00f6he voreingenommenen linken B\u00e4umen[edit]Java-Code zum Zusammenf\u00fchren von zwei min-H\u00f6hen voreingenommenen linken B\u00e4umen[edit]Beispiel[edit]Einf\u00fcgen in ein Min HBLT[edit]L\u00f6schen des Min-Elements aus Min HBLT[edit]Initialisieren eines h\u00f6henverzerrten linken Baums[edit]L\u00f6schen eines beliebigen Elements aus einem Min HBLT[edit]Gewichtungsverzerrter linker Baum[5][edit]Zusammenf\u00fchren von zwei Min WBLTs[edit]Andere Operationen auf WBLT[edit]Varianten[edit]Verweise[edit]Weiterlesen[edit]Externe Links[edit]S-Wert[edit] S-Werte eines linken BaumesDie s-Wert (oder Rang) eines Knotens ist die Entfernung von diesem Knoten zum n\u00e4chsten Blatt im Teilbaum, der an diesem Knoten verwurzelt ist. Anders ausgedr\u00fcckt, der s-Wert von a null Kind ist implizit null. Andere Knoten haben einen s-Wert gleich eins mehr als das Minimum der s-Werte ihrer Kinder. Im rechten Beispiel haben also alle Knoten mit mindestens einem fehlenden Kind einen s-Wert von 1, w\u00e4hrend Knoten 4 einen s-Wert von 2 hat, da sein rechtes Kind (8) einen s-Wert von 1 hat. (In einigen Beschreibungen wird der s-Wert von Null-Kindern mit \u20131 angenommen.[4])Den k\u00fcrzesten Weg zum n\u00e4chsten fehlenden Blatt im Unterbaum kennen, der bei verwurzelt ist x ist genau von S(x), jeder Knoten in der Tiefe S(x)\u22121 oder weniger hat genau 2 Kinder, da S(x) w\u00e4re weniger gewesen, wenn nicht. Das bedeutet, dass die Gr\u00f6\u00dfe des Baums mit Wurzeln bei x ist mindestens 2S(x)\u22121{displaystyle 2^{s(x)}-1}. Daher, S(x) ist h\u00f6chstens Protokoll\u2061(m+1){displaystyle log {(m+1)}}, m die Anzahl der Knoten des Teilbaums mit Wurzel bei x.[1]Operationen an einem h\u00f6henverzerrten linken Baum[1][edit]Die meisten Operationen an einem h\u00f6henverzerrten linken Baum werden mit der Zusammenf\u00fchrungsoperation ausgef\u00fchrt.Zusammenf\u00fchren von zwei Min HBLTs[edit]Der Zusammenf\u00fchrungsvorgang nimmt zwei Min-HBLTs als Eingabe und gibt einen Min-HBLT zur\u00fcck, der alle Knoten in den urspr\u00fcnglichen Min-HBLTs zusammengenommen enth\u00e4lt.Wenn entweder A oder B leer ist, gibt die Zusammenf\u00fchrung das andere zur\u00fcck.Im Fall von Min HBLTs nehmen wir an, dass wir zwei B\u00e4ume haben, die bei A und B verwurzelt sind, wobei A.key \u2264{displaystyle leq} B.Taste. Andernfalls k\u00f6nnen wir A und B vertauschen, sodass die obige Bedingung gilt.Die Zusammenf\u00fchrung erfolgt rekursiv durch Zusammenf\u00fchren von B mit dem rechten Unterbaum von A. Dies k\u00f6nnte den S-Wert des rechten Unterbaums von A \u00e4ndern. Um die Eigenschaft des linken Baums beizubehalten, pr\u00fcfen wir nach jeder Zusammenf\u00fchrung, ob der S-Wert des rechten Teilbaums w\u00e4hrend der rekursiven Zusammenf\u00fchrungsaufrufe gr\u00f6\u00dfer wurde als der S-Wert des linken Teilbaums. Wenn ja, vertauschen wir den rechten und linken Teilbaum (wenn ein Kind fehlt, sollte es das rechte sein).Da wir davon ausgegangen sind, dass die Wurzel von A gr\u00f6\u00dfer ist als die von B, wird auch die Heap-Eigenschaft beibehalten.Pseudocode zum Zusammenf\u00fchren von zwei min-H\u00f6he voreingenommenen linken B\u00e4umen[edit]MERGE(A, B) if A = null return B if B = null return A if A.key > B.key then SWAP (A, B) A.right\u00a0:= MERGE (A.right, B) \/\/ the result cannot be null since B is non-null if A.left = null then SWAP(A.left, A.right) A.s_value\u00a0:= 1 \/\/ since the right subtree is null, the shortest path to a descendant leaf from node A is 1 return A if A.right.s_value > A.left.s_value then SWAP (A.right, A.left) A.s_value\u00a0:= A.right.s_value + 1 return AJava-Code zum Zusammenf\u00fchren von zwei min-H\u00f6hen voreingenommenen linken B\u00e4umen[edit]public Node merge(Node x, Node y) { if (x == null) return y; if (y == null) return x; \/\/ if this were a max-heap, then the \/\/ next line would be: if (x.element < y.element) if (x.element.compareTo(y.element) > 0) { \/\/ x.element > y.element Node temp = x; x = y; y = temp; } x.rightChild = merge(x.rightChild, y); if (x.leftChild == null) { \/\/ left child doesn't exist, so move right child to the left side x.leftChild = x.rightChild; x.rightChild = null; \/\/ x.s was, and remains, 1 } else { \/\/ left child does exist, so compare s-values if (x.leftChild.s x.left.s_value f\u00fcr jeden Knoten x. In diesem Fall haben wir die an Knoten wurzelnden Teilb\u00e4ume mit den Schl\u00fcsseln 7 und 10 vertauscht.Einf\u00fcgen in ein Min HBLT[edit]Das Einf\u00fcgen erfolgt \u00fcber den Zusammenf\u00fchrungsvorgang. Ein Einf\u00fcgen eines Knotens in ein bereits bestehendesMin HBLT, erstellt mit diesem Knoten einen HBLT-Baum der Gr\u00f6\u00dfe eins und f\u00fchrt ihn mit dem vorhandenen Baum zusammen.INSERT (A, x) B\u00a0:= CREATE_TREE(x) return MERGE(A, B)L\u00f6schen des Min-Elements aus Min HBLT[edit]Das Min-Element in einem Min-HBLT ist die Wurzel. Somit wird zum L\u00f6schen des Min die Wurzel gel\u00f6scht und ihre Unterb\u00e4ume werden zusammengef\u00fchrt, um die neue Min HBLT zu bilden.DELETE_MIN(A) x\u00a0:= A.key A\u00a0:= MERGE (A.right, A.left) return xInitialisieren eines h\u00f6henverzerrten linken Baums[edit] Initialisieren eines min HBLT – Teil 1Das Initialisieren eines h\u00f6henverzerrten linken Baums erfolgt haupts\u00e4chlich auf eine von zwei Arten. Die erste besteht darin, jeden Knoten einzeln zu einem HBLT zusammenzuf\u00fchren. Dieser Prozess ist ineffizient und dauert O(nlogn) Zeit. Der andere Ansatz besteht darin, eine Warteschlange zu verwenden, um jeden Knoten und den resultierenden Baum zu speichern. Die ersten beiden Elemente in der Warteschlange werden entfernt, zusammengef\u00fchrt und wieder in die Warteschlange gestellt. Dies kann ein HBLT in O(n) Zeit. Dieser Ansatz wird in den drei mitgelieferten Diagrammen detailliert beschrieben. Ein linksgerichteter Baum mit minimaler H\u00f6he wird angezeigt.Um eine min HBLT zu initialisieren, stellen Sie jedes Element, das dem Baum hinzugef\u00fcgt werden soll, in eine Warteschlange. Im Beispiel (siehe Teil 1 links) ist die Zahlenmenge [4, 8, 10, 9, 1, 3, 5, 6, 11] werden initialisiert. Jede Zeile des Diagramms stellt einen anderen Zyklus des Algorithmus dar, der den Inhalt der Warteschlange darstellt. Die ersten f\u00fcnf Schritte sind einfach zu befolgen. Beachten Sie, dass das neu erstellte HBLT am Ende der Warteschlange hinzugef\u00fcgt wird. Im f\u00fcnften Schritt tritt das erste Auftreten eines s-Wertes gr\u00f6\u00dfer als 1 auf. Der sechste Schritt zeigt zwei miteinander verschmolzene B\u00e4ume mit vorhersehbaren Ergebnissen. Initialisieren eines min HBLT – Teil 2In Teil 2 findet eine etwas komplexere Zusammenf\u00fchrung statt. Der Baum mit dem niedrigeren Wert (Baum x) hat ein rechtes Kind, daher muss merge erneut f\u00fcr den Teilbaum aufgerufen werden, der vom rechten Kind von Baum x und dem anderen Baum verwurzelt ist. Nach der Zusammenf\u00fchrung mit dem Teilbaum wird der resultierende Baum wieder in Baum x gestellt. Der s-Wert des rechten Kindes (s=2) ist jetzt gr\u00f6\u00dfer als der s-Wert des linken Kindes (s=1), also m\u00fcssen sie getauscht werden. Der s-Wert des Wurzelknotens 4 betr\u00e4gt nun auch 2. Initialisieren eines min HBLT – Teil 3Teil 3 ist der komplexeste. Hier rufen wir merge zweimal rekursiv auf (jedes Mal mit dem nicht ausgegrauten Unterbaum des rechten untergeordneten Elements). Dies verwendet den gleichen Prozess, der f\u00fcr Teil 2 beschrieben wurde.L\u00f6schen eines beliebigen Elements aus einem Min HBLT[edit] Wenn wir einen Zeiger auf einen Knoten x in einem Min HBLT haben, k\u00f6nnen wir ihn wie folgt l\u00f6schen: Ersetzen Sie den Knoten x durch das Ergebnis der Zusammenf\u00fchrung seiner beiden Teilb\u00e4ume und aktualisieren Sie die s-Werte der Knoten auf dem Pfad von x zur Wurzel , Vertauschen des rechten und linken Teilbaums, falls erforderlich, um die Eigenschaft des linken Baums beizubehalten.Die Aufw\u00e4rtstraversierung wird fortgesetzt, bis entweder wir die Wurzel treffen oder sich die s-Werte nicht \u00e4ndern. Da wir ein Element l\u00f6schen, k\u00f6nnen die S-Werte auf dem zur\u00fcckgelegten Weg nicht erh\u00f6ht werden. Jeder Knoten, der bereits das rechte Kind seines Elternteils ist und bewirkt, dass der s-Wert seines Elternteils verringert wird, bleibt auf der rechten Seite. Jeder Knoten, der das linke Kind seines Elternteils ist und bewirkt, dass der s-Wert des Elternteils verringert wird, muss mit seinem rechten Geschwister vertauscht werden, wenn der s-Wert kleiner wird als der aktuelle s-Wert des rechten Kindes.Jeder Knoten muss einen Zeiger auf seinen Elternknoten haben, damit wir den Pfad zur Wurzel durchlaufen k\u00f6nnen, um die S-Werte zu aktualisieren.Wenn die Durchquerung an einem Knoten y endet, liegen die durchlaufenen Knoten alle auf dem am weitesten rechts liegenden Pfad, der bei Knoten y verwurzelt ist. Ein Beispiel ist unten gezeigt. Daraus folgt, dass die Anzahl der durchlaufenen Knoten h\u00f6chstens log(m) betr\u00e4gt, wobei m die Gr\u00f6\u00dfe des bei y wurzelnden Teilbaums ist. Somit ben\u00f6tigt diese Operation auch O(lg m) zur Durchf\u00fchrung.Gewichtungsverzerrter linker Baum[5][edit]Linke B\u00e4ume k\u00f6nnen auch gewichtsverzerrt sein. Anstatt s-Werte in Knoten x zu speichern, speichern wir in diesem Fall ein Attribut w(x) bezeichnet die Anzahl der Knoten im Unterbaum mit Wurzel bei x:w(x) = w(x.rechts) + w(x.links) + 1WBLTs stellen w(x.left) \u2265 w(x.right) f\u00fcr alle internen Knoten x sicher. WBLT-Operationen stellen diese Invariante sicher, indem sie die Kinder eines Knotens vertauschen, wenn der rechte Teilbaum aus dem linken herausw\u00e4chst, genau wie bei HBLT-Operationen.Zusammenf\u00fchren von zwei Min WBLTs[edit]Die Zusammenf\u00fchrungsoperation in WBLTs kann unter Verwendung einer einzigen Durchquerung von oben nach unten durchgef\u00fchrt werden, da die Anzahl der Knoten in den Unterb\u00e4umen vor dem rekursiven Aufruf zum Zusammenf\u00fchren bekannt ist. Somit k\u00f6nnen wir linke und rechte Teilb\u00e4ume vertauschen, wenn die Gesamtzahl der Knoten im rechten Teilbaum und dem zu verschmelzenden Baum gr\u00f6\u00dfer ist als die Anzahl der Knoten im linken Teilbaum. Dies erm\u00f6glicht die Durchf\u00fchrung der Operationen in einem einzigen Pfad und verbessert so die Zeitkomplexit\u00e4t der Operationen um einen konstanten Faktor.Der Zusammenf\u00fchrungsvorgang ist in der folgenden Grafik dargestellt.Andere Operationen auf WBLT[edit] Das Einf\u00fcgen und L\u00f6schen des min-Elements kann wie bei HBLTs mit dem Zusammenf\u00fchrungsvorgang erfolgen.Obwohl WBLTs HBLTs beim Zusammenf\u00fchren, Einf\u00fcgen und L\u00f6schen des Min-Schl\u00fcssels um einen konstanten Faktor \u00fcbertreffen, \u00d6(Protokoll n) ist beim L\u00f6schen eines beliebigen Elements aus WBLTs nicht garantiert, da \u03b8(n) Knoten m\u00fcssen durchlaufen werden.Wenn dies ein HBLT w\u00e4re, w\u00fcrde das L\u00f6schen des Blattknotens mit Schl\u00fcssel 60 dauern \u00d6(1) Zeit und Aktualisierung der s-Werte werden nicht ben\u00f6tigt, da sich die L\u00e4nge des ganz rechten Pfads f\u00fcr alle Knoten nicht \u00e4ndert.Aber in einem WBLT-Baum m\u00fcssen wir die Gewichtung jedes Knotens zur\u00fcck auf die Wurzel aktualisieren, was \u00d6(n) schlimmsten Fall.Varianten[edit]Es gibt mehrere Variationen des grundlegenden linken Baums, die nur geringf\u00fcgige \u00c4nderungen am grundlegenden Algorithmus vornehmen:Die Wahl des linken Kindes als das gr\u00f6\u00dfere ist willk\u00fcrlich; ein “rechter Baum” w\u00fcrde genauso gut funktionieren.Es ist m\u00f6glich, den Austausch von Kindern zu vermeiden, sondern stattdessen aufzunehmen welcher child ist der h\u00f6chste Wert (z. B. das niedrigstwertige Bit des s-Werts) und verwenden Sie diesen in der Zusammenf\u00fchrungsoperation.Der s-Wert, der verwendet wird, um zu entscheiden, mit welcher Seite zusammengef\u00fchrt werden soll, k\u00f6nnte eine andere Metrik als die H\u00f6he verwenden. Zum Beispiel k\u00f6nnte das Gewicht (Anzahl der Knoten) verwendet werden.Verweise[edit]^ ein B C “Linke B\u00e4ume” (PDF). www.google.com. Abgerufen 2019-05-31.^ ein B Kran, Clark A. (1972), Lineare Listen und Priorit\u00e4tswarteschlangen als ausgeglichene Bin\u00e4rb\u00e4ume (Doktorarbeit), Department of Computer Science, Stanford University, ISBN 0-8240-4407-X, STAN-CS-72-259^ Seonghun-Cho; Sartaj Sahni (1996), “Gewichtsverzerrte linke B\u00e4ume und modifizierte Skip-Listen” (PDF), Zeitschrift f\u00fcr experimentelle Algorithmik, 3, CiteSeerX 10.1.1.13.2962, doi:10.1145\/297096.297111^ Stewart, James (25. September 1988). “LINKE B\u00c4UME”. Dynamisches Grafikprojekt der Universit\u00e4t Toronto. Abgerufen 2019-05-31.^ Cho, Seonghun; Sahni, Sartaj (September 1998). “Gewichtsabh\u00e4ngige linke B\u00e4ume und modifizierte Skip-Listen”. J. Erw. Algorithmen. 3. mach:10.1145\/297096.297111. ISSN 1084-6654.Weiterlesen[edit]Externe Links[edit]"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki32\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki32\/2021\/09\/01\/linker-baum-wikipedia\/#breadcrumbitem","name":"Linker Baum \u2013 Wikipedia"}}]}]