Co to jest drzewo lewostronne, prawe-rodzeństwo reprezentujące drzewo? Dlaczego miałbyś go używać?

Question

Wiele struktur danych przechowuje drzewa wielodrożne jako drzewa binarne za pomocą reprezentacji o nazwie reprezentacji. Co to znaczy? Dlaczego miałbyś go używać?

Answer 1

Lewa-dziecko, reprezentacja prawym rodzeństwo (LCR) jest sposobem kodowania multi-way tree (strukturę drzewa, w którym każdy węzeł może mieć dowolną liczbę dzieci) za pomocą binary tree (strukturę drzewa w w którym każdy węzeł może mieć co najwyżej dwoje dzieci).

Motywacja

Aby zmotywować jak działa ta reprezentacja, zacznijmy rozważając prosty multi-drogi drzewa, jak ten tutaj: (! Przepraszamy za niskiej jakości ASCII grafika)

    A 
       //|\ \ 
      // | \ \ 
       B C D E F 
       | /|\ /\ 
       G H I J K L 

W tej strukturze drzewa możemy nawigować w dół od dowolnego węzła drzewa do dowolnego jego elementu podrzędnego. Na przykład możemy migrować z A do B, A do C, A do D, itd.

Jeśli chcemy reprezentować węzeł w drzewie takim jak ten, zwykle używamy jakiegoś rodzaju struktury węzła/węzła klasa jak ten tutaj (napisany w C++):

struct Node { 
    DataType value; 
    std::vector<Node*> children; 
}; 

w reprezentacji Lcrs, reprezentujemy multi-drogi drzewa w taki sposób, gdzie każdy węzeł wymaga co najwyżej dwa wskaźniki. Aby to zrobić, nieco zmieniamy kształt drzewa. Zamiast posiadania każdego węzła we wskaźnikach składnicy drzewka dla wszystkich jego elementów potomnych, będziemy układać drzewo w nieco inny sposób, ponieważ każdy węzeł będzie przechowywać wskaźnik do jednego z jego elementów potomnych (w LCRS, po lewej stronie dziecka). Następnie każdy magazyn węzła będzie miał wskaźnik do swojego prawego rodzeństwa, następny węzeł w drzewie, który jest dzieckiem tego samego węzła nadrzędnego. W przypadku powyższego drzewa, możemy reprezentować drzewo w następujący sposób:

  A 
     /
     /
     /
     B -> C -> D -> E -> F 
    /  /  /
     G   H->I->J K->L 

zauważyć, że w tej nowej struktury jest nadal możliwe, aby poruszać się z węzła nadrzędnego do jego k-dziecko (zero-indeksowane) . Procedura ta jest następująca:

• Zejście do lewego podrzędnego bieżącego węzła. (To jest pierwszy węzeł na liście jego dzieci).
• Podążaj za wskazówkami prawej siostry dziecka k razy. (To przeniesie cię do kth dziecka węzła).
• Zwróć ten węzeł.

Na przykład, aby znaleźć trzecie (zerowane indeksowane dziecko) węzła głównego A, zejdziemy do najbardziej wysuniętego na lewo dziecka (B), a następnie podążymy trzema prawymi linkami (odwiedzając B, C, D i wreszcie E). Następnie docieramy do węzła E, w którym znajduje się trzecie dziecko węzła A.

Głównym powodem przedstawienia drzewa w ten sposób jest to, że nawet jeśli dowolny węzeł może mieć dowolną liczbę dzieci, reprezentacja wymaga co najwyżej dwóch wskaźniki dla każdego węzła: jeden węzeł do przechowywania skrajnego lewego dziecka i jeden wskaźnik do przechowywania prawego rodzeństwa.W rezultacie, możemy przechowywać wielostronne drzewa przy użyciu znacznie prostszej struktury węzła:

struct Node { 
    DataType data; 
    Node* leftChild; 
    Node* rightSibling; 
}; 

struktura Ten węzeł ma dokładnie taki sam kształt węzła w drzewie binarnym (dane plus dwa wskaźniki). W rezultacie reprezentacja LCRS umożliwia reprezentowanie dowolnego drzewa wieloetapowego za pomocą zaledwie dwóch wskaźników na węzeł.

Analiza

Spójrzmy teraz na czasie i przestrzeni złożoności dwóch różnych przedstawień wieloosobowej drzewa i kilka podstawowych operacji na nim.

Zacznijmy od spojrzenia na całkowite wykorzystanie przestrzeni wymaganej dla początkowej reprezentacji "dynamicznej tablicy dzieci". Ile będzie całkowite wykorzystanie pamięci dla drzewa n-węzłów? Wiemy, co następuje:

1. Każdy węzeł, niezależnie od liczby dzieci, przyczynia się przestrzeń dla surowych danych przechowywanych (sizeof (dane)) i narzutu przestrzeni dynamicznej tablicy. Tablica dynamiczna (zazwyczaj) ma jeden wskaźnik zapisany (który wskazuje na przydzieloną tablicę), jedno słowo maszynowe dla całkowitej liczby elementów w tablicy dynamicznej i (opcjonalnie) jedno słowo maszynowe dla przydzielonej pojemności tablicy. Oznacza to, że każdy węzeł zajmuje przestrzeń size (dane) + sizeof (Node *) + 2 * sizeof (słowo maszynowe).

2. We wszystkich dynamicznych tablicach w drzewie będzie n - 1 wskaźników dla dzieci, ponieważ z n węzłów w drzewie n - 1 z nich ma rodziców. To dodaje dodatkowy współczynnik (n - 1) * sizeof (Node *).

Dlatego całkowite wykorzystanie przestrzeni jest

n Middot; (sizeof (Dane) + sizeof (Węzeł *) + 2 * sizeof (słowo maszyny)) + (n - 1) * sizeof (Węzeł *)

= n * sizeof (Dane) + (2n - 1) * sizeof (Węzeł *) + 2n * sizeof (słowo maszyny)

Porównajmy teraz to z drzewem LCRS. Każdy węzeł w LCR sklepy Tree dwa wskaźniki (2 * sizeof (Node *)), a jeden element danych (sizeof (dane)), tak więc jej całkowita powierzchnia jest

n * sizeof (dane) + 2n * sizeof (Node *)

I tu widzimy zwycięstwo: zauważ, że jesteśmy nie przechowywania 2n * sizeof (maszyna słowo) dodatkowej pamięci śledzić przydzielonych wielkości tablicy. Oznacza to, że reprezentacja LCRS zużywa znacznie mniej pamięci niż zwykłe drzewo wieloetapowe.

Jednak podstawowe operacje na strukturze drzewka LCRS zwykle trwają dłużej niż odpowiadające im operacje na normalnym drzewie wielodrożnym. W szczególności w drzewie wielowierszowym reprezentowanym w standardowej postaci (każdy węzeł przechowuje tablicę wskaźników potomnych), czas wymagany do nawigacji z jednego węzła do jego kodu dziecka jest określony przez czas wymagany do podążania za jednym wskaźnikiem. Z drugiej strony, w reprezentacji LCRS, czas wymagany do tego jest określony przez czas wymagany do podążania za wskaźnikami k + 1 (jeden lewy wskaźnik podrzędny, a następnie k prawe wskaźniki potomne). W rezultacie, jeśli drzewo ma duży współczynnik rozgałęzienia, może być o wiele wolniejsze wykonywanie wyszukiwań w strukturze drzewa LCRS niż w odpowiedniej strukturze drzewa wieloarkuszowego.

Możemy zatem myśleć o reprezentacji LCRS jako oferującej time-space tradeoff między przestrzenią przechowywania danych a czasem dostępu. Reprezentacja LCRS ma mniejszy zapas pamięci niż oryginalne drzewo wielowierszowe, podczas gdy drzewo wielowierszowe zapewnia stałe wyszukiwanie każdemu z jego potomków.

przypadki użycia

Ze względu na kompromis czasoprzestrzeni zaangażowanych w reprezentacji Lcrs reprezentacja Lcrs nie jest zwykle używany, chyba że jedno z dwóch kryteriów przytrzymanie:

1. pamięci jest niezwykle rzadkie, albo
2. Dostęp losowy dzieci węzła nie jest wymagany.

Przypadek (1) może powstać, jeśli trzeba przechowywać olbrzymie drzewo wielowarstwowe w pamięci głównej. Na przykład, jeśli konieczne było przechowywanie phylogenetic tree zawierającego wiele różnych gatunków podlegających częstym aktualizacjom, może być odpowiednia reprezentacja LCRS.

Przypadek (2) powstaje w wyspecjalizowanych strukturach danych, w których struktura drzewa jest używana w bardzo specyficzny sposób. Na przykład wiele typów modeli heap data structures, które używają drzew wielopasmowych, można zoptymalizować w przestrzeni za pomocą reprezentacji LCRS. Głównym powodem jest to, że w strukturach danych sterty, najczęstsze operacje bywają

1. Usuń korzeń drzewa i przetwarza każdy z jej dzieci, lub
2. Dołącz dwa drzewa razem poprzez jedno drzewo dziecko drugiego.

Operacja (1) może być wykonana bardzo sprawnie w reprezentacji LCRS. W reprezentacji LCRS, korzeń drzewa nigdy nie ma właściwego dziecka (ponieważ nie ma rodzeństwa), a zatem usunięcie korzenia oznacza po prostu oderwanie węzła głównego i zejście do jego lewego poddrzewa. Stamtąd przetwarzanie każdego dziecka można wykonać, po prostu idąc prawym kręgosłupem pozostałego drzewa i przetwarzając każdy węzeł po kolei.

Operacja (2) może być wykonana bardzo sprawnie. Przypomnijmy z góry, że w reprezentacji LCRS, korzeń drzewa nigdy nie ma właściwego dziecka. Dlatego bardzo łatwo połączyć dwa drzewa w reprezentacji LCRS w następujący sposób. Począwszy od dwóch drzew, takich jak ten:

R1    R2 
/   /
(children 1) (children 2) 

Możemy bezpiecznik drzew razem w ten sposób:

   R1 
      /
      R2 
     /\ 
(children 2) (children 1) 

Można to zrobić w czasie O (1) czasu i jest dość prosta. Fakt, że reprezentacja LCRS ma tę właściwość, oznacza, że ​​wiele typów kolejek priorytetu sterty, takich jak binomial heap lub rank-pairing heap, jest zwykle przedstawianych jako drzewa LCRS.

Mam nadzieję, że to pomoże!