K-ty element w drzewie sterty

Question

Mam stertę (zaimplementowaną jak drzewo binarne: każdy węzeł ma dwa wskaźniki dla dzieci i jeden wskaźnik dla rodzica).

Jak mogę znaleźć element k-ty (w kolejności BFS), biorąc pod uwagę liczbę elementów w nim? Myślę, że można to zrobić w czasie O (logn) ..

Answer 1

(Zakładam, że przez element "kth (w kolejności BFS)" masz na myśli element kh z perspektywy góry do dołu , skanowanie tekstu od lewej do prawej.)

Ponieważ wiesz, że binarna sterty jest kompletnym drzewem binarnym (z wyjątkiem prawdopodobnie na ostatnim poziomie), wiesz, że kształt drzewa jest idealnym drzewem binarnym o pewnej wysokości (zawierającej 2 węzły dla niektórych k) z pewną liczbą węzłów wypełnianych od lewej do prawej. Naprawdę ładne własność tych drzew występuje podczas wypisać liczbę węzłów w obrazie, jedna indeksowania wartości:

     1 
      2    3 
     4  5  6  7 
     8 9 10 11 12 13 14 15 

Zauważ, że każda warstwa zaczyna się od węzła, który jest potęgą dwójki. Więc załóżmy hipotetycznie, że chciałeś wyszukać numer 13. największą moc dwóch nie większej niż 13 jest 8, więc wiemy, że 13 muszą pojawiać się w wierszu

8 9 10 11 12 13 14 15 

Możemy teraz wykorzystać tę wiedzę do odwrotnej inżynierii ścieżki od 13 z powrotem do katalogu głównego drzewa. Wiemy na przykład, że 13 znajduje się w drugiej połowie liczb w tym wierszu, co oznacza, że ​​13 należy do prawego poddrzewa głównego (jeśli należało do lewego poddrzewa, to znaleźlibyśmy się w poddrzewie zawierającym 8, 9, 10 i 11.) oznacza to, że możemy iść w prawo od korzenia i wyrzucić połowę numerów dostać

12 13 14 15 

Jesteśmy teraz w węźle 3 w drzewie. Czy idziemy w lewo czy w prawo? Cóż, 13 jest w pierwszej połowie tych liczb, więc wiemy, że musimy zejść do lewego podtree węzła 3. To prowadzi nas do węzła 6, a teraz pozostajemy z pierwszą połową numery:

12 13 

13 znajduje się w prawej połowie tych węzłów, więc powinniśmy zejść w prawo, zabierając nas do węzła 13. I voila! Byli tam!

Jak ten proces zadziałał? Cóż, istnieje naprawdę, naprawdę urocza sztuczka, której możemy użyć. Załóżmy pisać tego samego drzewa mieliśmy powyżej, ale w formacie binarnym:

     0001 
      0010     0011 
     0100  0101  0110  0111 
    1000 1001 1010 1011 1100 1101 1110 1111 
           ^^^^ 

Mam wskazał lokalizację węzła 13. Nasz algorytm działał w następujący sposób:

1. Znajdź warstwę zawierającą węzeł.
2. Podczas gdy nie w danym węźle:
   1. Jeśli węzeł znajduje się w pierwszej połowie warstwy, jest w środku, przesuń w lewo i odrzuć prawą połowę zakresu.
   2. Jeśli węzeł znajduje się w drugiej połowie warstwy, jest w środku, przesuń w prawo i wyrzuć lewą połowę zakresu.

Pomyślmy o tym, co to oznacza w systemie binarnym.Znalezienie warstwy zawierającej węzeł to , równoważne znalezieniu najbardziej znaczącego zestawu bitów w numerze. W 13, który ma binarną reprezentację 1101, MSB jest 8-bitowym. Oznacza to, że jesteśmy w warstwie zaczynając od ośmiu.

Jak zatem ustalić, czy jesteśmy w lewym poddrzewie, czy w prawym poddrzewie? Cóż, aby to zrobić, musimy sprawdzić, czy jesteśmy w pierwszej połowie tej warstwy lub w drugiej połowie. A teraz dla uroczej sztuczki - spójrz na następny bit po MSB. Jeśli ten bit jest ustawiony na 0, jesteśmy w pierwszej połowie zakresu, a poza tym jesteśmy w drugiej połowie zakresu. W ten sposób możemy określić, z której połowy zakresu jesteśmy, patrząc na kolejny fragment liczby! Oznacza to, że możemy określić, do którego subtree się zejdzie, patrząc tylko na kolejny fragment liczby.

Kiedy już to zrobimy, możemy powtórzyć ten proces. Co robimy na kolejnym poziomie? Cóż, jeśli następny bit to zero, idziemy w lewo, a jeśli następny jest jeden, idziemy w prawo. Spójrz na to, co to oznacza dla 13:

1101 
    ^^^ 
    ||| 
    ||+--- Go right at the third node. 
    || 
    |+---- Go left at the second node. 
    | 
    +----- Go right at the first node. 

Innymi słowy, możemy sformułować ścieżkę z korzenia drzewa do naszego węzła w pytaniu po prostu patrząc na bitach liczby po MSB !

Czy to zawsze działa! Obstawiasz! Spróbujmy liczby 7. To ma binarną reprezentację 0111. MSB jest na miejscu 4. Korzystając z naszego algorytmu, możemy to zrobić:

0111 
    ^^ 
    || 
    |+--- Go right at the second node. 
    | 
    +---- Go right at the first node. 

Patrząc w nasze oryginalne zdjęcie, jest to właściwa droga do podjęcia!

Oto niektóre szorstki C/C++ pseudokod dla tego algorytmu:

Node* NthNode(Node* root, int n) { 
    /* Find the largest power of two no greater than n. */ 
    int bitIndex = 0; 
    while (true) { 
     /* See if the next power of two is greater than n. */ 
     if (1 << (bitIndex + 1) > n) break; 
     bitIndex++; 
    } 

    /* Back off the bit index by one. We're going to use this to find the 
    * path down. 
    */ 
    bitIndex--; 

    /* Read off the directions to take from the bits of n. */ 
    for (; bitIndex >= 0; bitIndex--) { 
     int mask = (1 << bitIndex); 
     if (n & mask) 
      root = root->right; 
     else 
      root = root->left; 
    } 
    return root; 
} 

nie testowałem ten kod! Parafrazując Don Knuth, właśnie pokazałem, że koncepcyjnie robi to dobrze. Możliwe, że mam tu jeden błąd "z osobna".

Jak szybki jest ten kod? Cóż, pierwsza pętla działa, dopóki nie znajdzie pierwszej mocy dwóch większych niż n, co zabiera czas O (log n). Kolejna część pętli odlicza wstecz przez bity po jednym na raz, wykonując O (1) na każdym kroku. Ogólny algorytm zajmuje w sumie czas O (log n).

Mam nadzieję, że to pomoże!