Treap: Der Zufall macht den binären Suchbaum schnell
Treap (Cartesian Tree)
Ein Treap kombiniert binären Suchbaum und Heap: Jeder Knoten speichert einen Schlüssel und eine zufällig gewählte Priorität. Die Prioritäten legen die Baumform eindeutig fest und verhindern im Durchschnitt entartete Listen. Split und Merge genügen, um Einfügen, Suchen, Löschen, Vereinigen und Schneiden in logarithmischer Zeit umzusetzen. Der Artikel erklärt die Operationen und zeigt eine kompakte C++-Implementierung.
Offensichtlich erhält man, wenn man die Prioritäten zufällig wählt, im Durchschnitt nicht entartete Bäume, was die Komplexität für die Hauptoperationen sicherstellt.