next up previous contents
Next: Suchbäume, balancierte Bäume Up: Höhere Datenstrukturen Previous: Höhere Datenstrukturen

Grundlegende Operationen

Es sei U das Universum von Schlüsseln mit der Ordnung $\leq$. Menge $S\subset U$. Gegeben seien eine Menge von Datensätzen $x_1,\cdots,x_n$, wobei jeder Datensatz x durch einen Schlüssel Key($x)=K\subset S$ gekennzeichnet ist. x=(K,Val(K)).


IsElement(K,S) : ist $K\in S$, wenn ja, return Val(K)
Insert(K,S : $S:=S\cup\{K\}$
Delete(K;S) : $S:=S \setminus \{K\}$
FindMin(S) : return $\min{S}$
FindMax(S) : return $\max{S}$
DeleteMin(S) : $S:=S \setminus \min{S}$
DecreaseKey($K,\Delta ,S$) : Ersetze K durch $K-\Delta$
Union(S1,S2) : $S_1=S_1 \cup S_2$
Find(K) : Falls $K\in S$, so finde (K,Val(K))
Merge(S1,S2) : $S_1=S_1 \cup S_2$ , falls $S_1 \cap S_2 = \emptyset$
Split(S1,K,S2) : $S_2 = \{ K' \in S_2 \vert K' \ge K \}$
  $S_1 = \{ K' \in S_1 \vert K' < K \} $
Concatenate(S1,S2) : $S_1 := S_1 \cup S_2$; Voraussetzung: FindMax(S1) $\le$ FindMax(S2)


Datenstrukturklasse mindestens angebotene Funktionen realisiert in
Wörterbuch (Dictionary) IsElement() , Insert() , Delete() Hashtable, balancierte Bäume
Vorrangwarteschlange (Priority Queue) FindMin() , Insert() , Delete() , [IsElement()] balancierte, Leftist-, Binomialbäume
Mergeable heaps FindMin() , Insert() , Delete() , Merge() 2-3-Bäume, Binomialwälder, Leftist-Bäume
Concatenable queues FindMin() , Insert() , Delete() , Concatenate() 2-3-Bäume
next up previous contents
Next: Suchbäume, balancierte Bäume Up: Höhere Datenstrukturen Previous: Höhere Datenstrukturen
Abbas-Bardia Kabiri-Jarghouyeh
3/3/1999