Reprezentacja lewe-dziecko, prawe-rodzeństwo (LCR) jest sposobem kodowania drzewo wielodrożne (struktura drzewa, w której każdy węzeł może mieć dowolną liczbę dzieci) za pomocą drzewo binarne (struktura drzewa, w której każdy węzeł może mieć co najwyżej dwoje dzieci).

Motywacja

Aby zmotywować działanie tej reprezentacji, zacznijmy od rozważenia prostego drzewa wielokierunkowego, takiego jak to tutaj: {]}

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

(Przepraszam za niska jakość grafiki ASCII!)

W tej strukturze drzewa możemy poruszać się w dół z dowolnego węzła w drzewie do dowolnego z jego dzieci. Na przykład możemy migrować z A do B, A do C, a do D, itp.

Gdybyśmy chcieli reprezentować węzeł w drzewie takim jak ten, normalnie użylibyśmy jakiejś struktury węzła / klasy węzła, takiej jak ta tutaj (napisana w C++): {]}

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

W reprezentacji LCRS reprezentujemy drzewo wielodrożne w sposób, w którym każdy węzeł wymaga co najwyżej dwóch pointers. Aby to zrobić, lekko zmienimy kształt drzewa. Zamiast mieć każdy węzeł w drzewie wskaźników do wszystkich jego dzieci, będziemy układać drzewo w nieco inny sposób, ponieważ każdy węzeł przechowuje wskaźnik do tylko jednego z jego dzieci (w LCR, najbardziej po lewej stronie dziecka). Następnie każdy węzeł będzie przechowywał wskaźnik do swojego prawego rodzeństwa, następnego węzła w drzewie, który jest potomkiem tego samego węzła nadrzędnego. W przypadku powyższego drzewa możemy przedstawić drzewo w następujący sposób:

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

Zauważ, że w tej nowej strukturze nadal można poruszać się od węzła nadrzędnego do jego potomka kth (indeksowanego zero). Procedura ta jest następująca:

• zejść do lewego potomka bieżącego węzła. (Jest to pierwszy węzeł na liście jego dzieci).
• podążaj za prawym wskaźnikiem rodzeństwa tego dziecka k razy. (Prowadzi to do dziecka kth węzła).
• zwróć ten węzeł.

Na przykład, aby znajdujemy trzecie (indeksowane dziecko) głównego węzła A, schodzimy do lewego dziecka (B) , a następnie podążamy za trzema prawymi linkami (odwiedzając B, C, D i wreszcie E). Następnie docieramy do węzła dla E, który posiada trzecie dziecko węzła A.

Głównym powodem reprezentacji drzewa w ten sposób jest to, że chociaż każdy węzeł może mieć dowolną liczbę Potomków, reprezentacja wymaga co najwyżej dwóch wskaźników dla każdego węzła: jednego węzła do przechowywania potomka po lewej stronie i jednego wskaźnika do przechowywania potomka po lewej stronie. prawe rodzeństwo. W rezultacie możemy przechowywać drzewo wielowejściowe za pomocą znacznie prostszej struktury węzła:

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

Ta struktura węzła 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 wielokierunkowego za pomocą tylko dwóch wskaźników na węzeł.

Analiza

Przyjrzyjmy się teraz złożoności czasu i przestrzeni dwóch różnych reprezentacji drzewa wielowejściowego i kilku podstawowe operacje na nim.

Zacznijmy od całkowitego wykorzystania przestrzeni wymaganej dla początkowej reprezentacji "dynamicznej tablicy dzieci". Ile będzie całkowitego zużycia pamięci dla drzewa n-węzłów? Wiemy co następuje:

1. Każdy węzeł, niezależnie od jego liczby Potomków, zapewnia miejsce dla przechowywanych danych surowych(sizeof (data)) i narzutu przestrzeni tablicy dynamicznej. Tablica dynamiczna (zazwyczaj) ma zapisany jeden wskaźnik (który wskazuje na przydzielona tablica), jedno słowo maszynowe dla całkowitej liczby elementów w tablicy dynamicznej oraz (opcjonalnie) jedno słowo maszynowe dla przydzielonej pojemności tablicy. Oznacza to, że każdy węzeł zajmuje przestrzeń sizeof (Data) + sizeof (Node*) + 2 * sizeof (machine word).

2. We wszystkich tablicach dynamicznych w drzewie będzie N-1 wskaźników do dzieci, ponieważ z n węzłów w drzewie N-1 z nich ma rodziców. Który dodaje dodatkowo (n-1) * sizeof(węzeł *) factor.

Zatem całkowite wykorzystanie przestrzeni wynosi

N · (sizeof (Data) + sizeof (Node*) + 2 * sizeof (słowo maszynowe)) + (n - 1) * sizeof (Node *)

= n * sizeof (dane) + (2n - 1) * sizeof (węzeł*) + 2n * sizeof (słowo maszynowe)

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

I tutaj widzimy win: zauważ, że jesteśmy , a nie przechowujemy 2n * sizeof (słowo maszynowe) dodatkowej pamięci do śledzenia przydzielonych rozmiarów tablic. Oznacza to, że reprezentacja LCRS zużywa znacznie mniej pamięci niż zwykłe drzewo wielokierunkowe.

Jednak podstawowe operacje na strukturze drzewa LCRS zwykle trwają dłużej niż odpowiadające im operacje na normalnym drzewie wielokierunkowym. Konkretnie, w wielodrożnym drzewie reprezentowanym w standardzie form (każdy węzeł przechowuje tablicę wskaźników potomnych), czas potrzebny do przejścia od jednego węzła do jego kth potomka jest podany przez czas wymagany do podążania za pojedynczym 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 potomny, a następnie K prawy wskaźnik potomny). W rezultacie, jeśli drzewo ma duży współczynnik rozgałęzienia, może być znacznie wolniej szukać w strukturze drzewa LCRS niż w odpowiadająca wielowejściowa struktura drzewa.

Możemy więc myśleć o reprezentacji LCRS jako oferującej czasoprzestrzeń pomiędzy przestrzenią przechowywania struktury danych a czasem dostępu. Reprezentacja LCRS ma mniej pamięci narzutu niż oryginalne drzewo wielowejściowe, podczas gdy drzewo wielowejściowe daje stałe przeglądanie w czasie każdego ze swoich dzieci.

Przypadki Użycia

Ze względu na czasoprzestrzeń związaną z reprezentacją LCRS, reprezentacja LCRS jest zazwyczaj nie stosuje się, chyba że jedno z dwóch kryteriów spełnia:

1. pamięć jest niezwykle rzadka, lub
2. losowy dostęp dzieci węzła nie jest wymagany.

Przypadek (1) może się pojawić, jeśli trzeba będzie przechowywać zdumiewająco ogromne drzewo wielowejściowe w pamięci głównej. Na przykład, jeśli trzeba przechowywać drzewo filogenetyczne zawierające wiele różnych gatunków podlegających częstym aktualizacjom, wtedy reprezentacja LCRS może być odpowiednia.

Przypadek (2) powstaje w wyspecjalizowane struktury danych, w których struktura drzewa jest używana w bardzo specyficzny sposób. Na przykład wiele typów struktur danych sterty, które używają drzew wielowejściowych, można zoptymalizować za pomocą reprezentacji LCRS. Głównym powodem tego jest to, że w strukturach danych sterty, najczęstsze operacje wydają się być

W 1996 roku, w wyniku połączenia się z nim, w 1999 roku, doszło do połączenia się z nim.]}
1. połącz dwa drzewa razem, czyniąc jedno drzewo dzieckiem inne.

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

Operacja (2) może być wykonana bardzo również sprawnie. Przypomnij sobie z góry, że w reprezentacji LCRS korzeń drzewa nigdy nie ma odpowiedniego dziecka. Dlatego bardzo łatwo jest połączyć ze sobą dwa drzewa w reprezentacji LCRS w następujący sposób. Zaczynając od dwóch takich drzew:

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

Możemy połączyć drzewa w ten sposób:

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

Można to zrobić w czasie O(1) i jest dość proste. Fakt, że reprezentacja LCRS ma tę właściwość oznacza, że wiele typów kolejek pierwszeństwa, takich jak stosy dwumianowe lub stosy parujące rangi są zazwyczaj reprezentowane jako drzewa LCRS.