Intrees

Next: Gewichtete Union (erste Verbesserung) Up: Union-Find-Datenstruktur Previous: Union-Find-Datenstruktur

1.: Initialisierung: $x\rightarrow \bullet x$ : Mache x zur Wurzel eines neuen (einelementigen) Baumes.
2.: $\textstyle\parbox{30mm}{ \textsl{\textsf{Union($T_1,T_2$)}} :}$
$\begin{picture} (116,20) \put(10,13){\circle*{2}} \put(10,13){\line(1,-1){10}}... ...put(105,11){\makebox(0,0){$T_{1}$}} \put(80,10){\vector(3,1){23}}\end{picture}$
3.: Find : Suche Wurzel des Baumes, in dem sich x befindet.

Bemerkung: Naive Implementation: worst-case-Tiefe = n

Abbas-Bardia Kabiri-Jarghouyeh
3/3/1999