Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Vereinigung von Bäumen
Hallo!!!
Wir betrachten eine Implementierung von disjunkten Mengen mit Union, wobei es maximal M disjunkte Mengen geben kann.
Die Implementierung benutzt eine Hashtabelle T[0… max-1] in der Schlüssel gespeichert werden, basierend auf der Methode ordered double hashing.
Sei h1 die Primäre und h2 die Sekundäre Hash-Funktion.
T enhält die Schlüssel von den Knoten von allen “up trees”, als auch einen Pointer zu dem entsprechenden Knoten für jedem von diesen.
Ich will ein Algorithmus schreiben der die Schlüssel von zwei Knoten als Argumente nimmt und die “up trees” zu dene die Knoten gehören vereinigt
( Die Knoten können zu egal welchen “up tree” gehören, auch zum gleichen, in diesem Fall muss eine entsprechende Mitteilung erscheinen).
Während der Vereinigung, sollen die Techniken der Pfadkompression und der Höhenreduzierung angewendet werden.
Wir nehmen an dass wir bestimmte Hash-Funktionen haben.
Der Algorithmus für die Vereinigung von “up trees” ist der folgende:
pointer Union(S,T){
if (S==NULL or T==NULL) return;
if (S->count>=T->count){
S->count=S->count+T->count;
T->parent=S;
return S;
}
else {
T->count=T->count+S->count;
S->parent=T;
return T;
}
}Wie könnten wir aber in diesem Fall, wo wir eine Hashtabelle haben die “up trees” vereinigen?