Linksbaum

Ein Linksbaum oder Linksheap ist eine Vorrangwarteschlange, die durch eine Variante eines Binärbaumes verwirklicht ist. Diese Datenstruktur ist eine Erfindung von Clark Allan Crane und nutzt eine Heapstruktur. Linksbäume sollen, im Gegensatz zu binären Heaps, sehr unbalanciert sein. Die Kindknoten sind so sortiert, dass der rechte Pfad der kürzere von der Wurzel zu einem Blatt ist. Wenn ein neuer Knoten in einen Baum eingefügt wird, wird ein neuer einknotiger Baum erstellt und mit dem alten Baum verschmolzen. Beim Löschen eines Knotens wird dieser entfernt, und die beiden Unterknoten werden mit dem alten Baum verschmolzen. Beide Operationen benötigen logarithmische Zeit: O(log n). Einfügungen sind langsamer als bei binären Heaps, die in amortisierten Laufzeitanalysen eine konstante Zeit benötigen: O(1).

Der Vorteil von Linksbäumen besteht in ihrer Fähigkeit, schnell verschmolzen zu werden, verglichen mit binären Heaps, die dafür eine Komplexität von Θ(n) haben. Jedoch benötigen Skew Heaps meist weniger Rechenzeit.

Siehe auch

• Leftist Tree at Dr. Sartaj Sahni's website (Department Chair in CISE at University of Florida; PDF-Datei; 37 kB)