Cytat z książki: "Dla każdego węzła przechowujemy jego rangę stanowiącą przybliżenie logarytmu z rozmiaru poddrzewa, a zarazem górne ograniczenie na wysokość węzła."
Czyli czym konkretnie jest ta ranga? Bardzo proszę o przykład jakiegoś drzewa z wymienionymi rangami dla poszczególnych węzłów.
0
0
Jest na przykład wysokością drzewa, masz przecież wyraźnie napisane. Np. takie drzewo:
1->2->3->4 ma wysokość 4 i tyle operacji musimy wykonać żeby od liścia dość do "głowy zbioru". Implementując zbiory rozłączne chodzi nam o szybkie wykonywanie operacji sprawdzania rozłączności i operacji łączenia zbiorów. Łączenie zbiorów jest zwykle dość proste - bierzemy jedną z "głów" i przypinamy do drugiej. Problem w tym że w ten sposób powstają nam właśnie takie długie ścieżki jak ta którą przedstawiłem powyżej. Stosuje sie więc kompresje ścieżki, czyli przebudowanie drzewa, tak aby wszystkie liście wskazywały bezpośrednio na "głowę". Dzięki temu operacja testowania rozłączności ma O(1).