Algorytmy drzewa oparte na łączeniach

W informatyce algorytmy drzewa oparte na łączeniach są klasą algorytmów samobalansujących drzew wyszukiwania binarnego . Ramy te mają na celu zaprojektowanie wysoce równoległych algorytmów dla różnych zrównoważonych drzew wyszukiwania binarnego. Ramy algorytmiczne opierają się na pojedynczej operacji łączenia . W tych ramach łączenia obejmuje wszystkie kryteria równoważenia różnych schematów równoważenia, a wszystkie inne łączenie funkcji ma ogólną implementację w różnych schematach równoważenia. Algorytmy oparte na łączeniach można zastosować do co najmniej czterech schematów równoważenia: drzew AVL , drzew czerwono-czarnych , drzew zbalansowanych wagowo i treapów .

( $, R)}$ Displaystyle ( $k$$klucz$ przyjmuje jako dane wejściowe dwa zrównoważone drzewa binarne samego schematu równoważenia i ${\ displaystyle k}$$i$ wyprowadza nowe zrównoważone drzewo binarne, przechodzenie w kolejności jest przechodzeniem w kolejności ${\ displaystyle L}$ , a następnie ${\ displaystyle k},$ a następnie przechodzenie w kolejności ${\ displaystyle R}$ . W szczególności, jeśli drzewa są drzewami wyszukiwania , co oznacza, że ​​kolejność drzew zachowuje całkowite uporządkowanie kluczy, musi spełniać warunek, że wszystkie klucze w ${\ displaystyle L}$ są mniejsze niż ${\ displaystyle k }$ i wszystkie klucze w $}$ większe niż ${\ displaystyle k$ .

Historia

Operacja łączenia została po raz pierwszy zdefiniowana przez Tarjana na czerwono-czarnych drzewach , która przebiega w czasie logarytmicznym najgorszego przypadku. Później Sleator i Tarjan opisali łączenia dla drzew splay , który działa w amortyzowanym czasie logarytmicznym. Później Adams rozszerzył łączenie na drzewa z wyważoną wagą i użył go do szybkich funkcji zestawu-ustawienia, w tym sumy , przecięcia i różnicy zestawów . W 1998 r. Blelloch i Reid-Miller przedłużyli współpracę na treaps i udowodnił, że granica ustawionych funkcji wynosi ${\ Displaystyle O (m \ log (1 + {\ tfrac {n} {m}})}}$ dla dwóch drzew o rozmiarze $)$ n $\ Displaystyle n (\ geq m)}$ , co jest optymalne w modelu porównawczym Podnieśli również równoległość w algorytmie Adamsa, stosując schemat dziel i zwyciężaj . W 2016 roku Blelloch i in. formalnie zaproponował algorytmy łączenia i sformalizował łączenia dla czterech różnych schematów równoważenia: drzewa AVL , drzewa czerwono-czarne , drzewa o zrównoważonej wadze i treaps . W tej samej pracy udowodnili, że algorytmy Adamsa dotyczące sumy, przecięcia i różnicy są optymalne pod względem pracy we wszystkich czterech schematach równoważenia.

Dołącz do algorytmów

Funkcja join $rozważa ponowne zrównoważenie$ schematu Jeśli oba drzewa są zrównoważone, polecenie join po prostu tworzy nowy węzeł z lewym poddrzewem t ₁ , korzeniem k i prawym poddrzewem t ₂ . Załóżmy, że t ₁ jest cięższy (ten „cięższy” zależy od schematu równoważenia) niż t ₂ (drugi przypadek jest symetryczny). Join podąża za prawym grzbietem t ₁ aż do węzła c , który jest zrównoważony z t ₂ . W tym momencie tworzony jest nowy węzeł z lewym dzieckiem c , korzeniem k i prawym dzieckiem t _{2 w celu zastąpienia c.} Nowy węzeł może unieważnić niezmiennik bilansujący. Można to naprawić za pomocą obrotów.

Poniżej przedstawiono algorytmy łączenia w różnych schematach równoważenia.

łączenia dla drzew AVL :

             funkcja  joinRightAVL(T  L  , k, T  R  ) (l, k', c) := ujawnij(T  L  )  jeśli  h(c) ≤ h(T  R  ) + 1 T' := Węzeł(c, k, T  R  )  if  h(T') ≤ h(l) + 1  return  Node(l, k', T')  else  return  obróćw lewo(węzeł(l, k', obróćw prawo(T')))  else  T' := joinRightAVL (c, k, T  R  ) T :  =  Węzeł(l, k', T') 
             if  h(T') ≤ h(l) + 1  return  T  else  return  funkcji  joinLeft(T)  joinLeftAVL(T  L  , k, T  R  ) /* symetrycznie do joinRightAVL */  function  join(T  L  , k, T  R  )  if  h(T  L  ) > h(T  R  ) + 1  return  joinRightAVL(T  L  , k, T  R  )  inaczej if  h(T  R  ) > h(T  L 
         ) + 1  return  joinLeftAVL(TL  ,  k, T  R  )  inaczej  return  Node(TL  ,  k,  TR  ) 

Gdzie:

• ${\ Displaystyle h (v)}$ to wysokość węzła ${\ displaystyle v}$ .
• ${\ Displaystyle {\ tekst {eksponować}} (v)}$ wyodrębnia lewe dziecko ${\ displaystyle l}$ , klucz ${\ displaystyle k}$ i prawe dziecko ${\ displaystyle r}$ węzła ${ \ displaystyle v}$ w krotkę ${\ Displaystyle (l, k, r)}$ .
• ${\ Displaystyle {\ tekst {węzeł}} (l, k, r)}$ tworzy węzeł z lewym dzieckiem i prawym dzieckiem ${\ displaystyle l}$ , klucz ${\ displaystyle k}$${\ displaystyle r}$ .

Algorytm łączenia drzew czerwono-czarnych dla :

 funkcja  joinRightRB(T  L  , k, T  R  )  if  r(T  L  ) = ⌊r(T  R  )/2⌋ × 2  powrót  Node(T  L  , ⟨k, red⟩, T  R  )  else  (L', ⟨ k', c'⟩, R') := odsłonić(T  L  ) T' := Węzeł(L', ⟨k', c'⟩, joinRightRB(R', k, T  R  ))  if  c' = czarny  I 
             T'.right.color = T'.right.right.color = red T'.right.right.color := czarny  return  obróćw lewo(T')  else  return  T'  funkcja  joinLeftRB(T  L  , k, T  R  ) / * symetrycznie do joinRightRB */  funkcja  join(T  L  , k, T  R  )  jeśli  ⌊r(T  L  )/2⌋ > ⌊r(T  R  )/2⌋ × 2 T' := joinRightRB(T  L  , k, T  R  )  jeśli 
         (T'.kolor = czerwony)  i  (T'.prawy.kolor = czerwony) T'.kolor := czarny  zwróć  T'  inaczej, jeśli  ⌊r(T  R  )/2⌋ > ⌊r(T  L  )/2⌋ × 2 /* symetryczny */  inaczej jeśli  T  L  .color = czarny  i  T  R  = czarny  powrót  Node(T  L  , ⟨k, red⟩, T  R  )  inaczej  powrót  Node(T  L  , ⟨k, czarny⟩, T  R  ) 

Gdzie:

• ${\ Displaystyle r (v)}$$oznacza$ dwukrotność czarnej wysokości czarnego węzła i dwukrotność czarnej wysokości czerwonego węzła.
• ${\ Displaystyle {\ tekst {eksponować}} (v)}$ wyodrębnia lewe dziecko ${\ displaystyle l}$ , klucz ${\ displaystyle k}$ , kolor ${\ displaystyle c}$ i prawe dziecko ${ \ displaystyle r}$ węzła ${\ displaystyle v}$ w krotkę ${\ Displaystyle (l, \ langle k, c \ rangle, r)}$ .
• ${\ Displaystyle {\ tekst {węzeł}} (l, \ langle k, c \ rangle, r)}$ tworzy węzeł z lewym dzieckiem ${\ displaystyle l}$ , klucz ${\ displaystyle k}$ , kolor ${\ displaystyle c}$ i prawe dziecko ${\ displaystyle r}$ .

Algorytm łączenia dla drzew o zrównoważonej wadze :

 funkcja  joinRightWB(T  L  , k, T  R  ) (l, k', c) := odsłonić(T  L  )  if  w(T  L  ) =  α  w(T  R  )  powrót  Węzeł(T  L  , k, T  R  )  else  T' := joinRightWB(c, k, T  R  ) (l  1  , k  1  , r  1  ) := odsłonić(T')  if  w(l) =  α  w(T') 
             zwróć  Węzeł(l, k', T')  inaczej jeśli  w(l) =  α  w(l  1  )  i  w(l)+w(l  1  ) =  α  w(r  1  )  zwróć  obróćw lewo(węzeł(l, k ', T'))  else  return  obróćw lewo(węzeł(l, k', obróćw prawo(T'))  funkcja  joinLeftWB(T  L  , k, T  R  ) /* symetrycznie do joinRightWB */  funkcja  join(T  L  , k, T  R 
         )  if  w(T  L  ) >  α  w(T  R  )  return  joinRightWB(TL  ,  k,  TR  )  else if  w(T  R  ) >  α  w(T  L  )  return  joinLeftWB(TL  ,  k,  TR  )  w przeciwnym razie  zwróć  Węzeł(T  L  , k, T  R  ) 

Gdzie:

• ${\ Displaystyle w (v)}$ to waga węzła ${\ displaystyle v}$ .
• ${\ Displaystyle w_ {1} = _ {\ alfa} w_ {2}}$ oznacza wagi ${\ Displaystyle w_ {1}}$ i ${\ Displaystyle w_ {2}}$ są α- zrównoważony wagowo.
• ${\ Displaystyle w_ {1}> _ {\ alfa} w_ {2}}$ oznacza wagę ${\ Displaystyle w_ {1}}$ jest cięższa niż waga ${\ Displaystyle w_ {2}}$ w odniesieniu do bilansu wagowego α.
• ${\ Displaystyle {\ tekst {eksponować}} (v)}$ wyodrębnia lewe dziecko ${\ displaystyle l}$ , klucz ${\ displaystyle k}$ i prawe dziecko ${\ displaystyle r}$ węzła ${ \ displaystyle v}$ w krotkę ${\ Displaystyle (l, k, r)}$ .
• ${\ Displaystyle {\ tekst {węzeł}} (l, k, r)}$ tworzy węzeł z lewym dzieckiem $displaystyle$ kluczem $k}$ i prawym dzieckiem ${\ displaystyle r}$ .

Algorytmy oparte na łączeniach

Poniżej $\$$\ displaystyle$ dziecko , klucz $k}$ prawe dziecko $displaystyle r}$ węzła $($ krotkę ${\ Displaystyle (l, k, r)$ . $k$$, r)}$ tworzy węzeł z lewym dzieckiem kluczem $r$ prawym dzieckiem $\ displaystyle r}$ . „ $}$${2}$$\$ " oznacza, że ​​dwie instrukcje działać w równoległy.

Podział

Aby podzielić drzewo na dwa drzewa, mniejsze niż klucz x i większe niż klucz x , najpierw rysujemy ścieżkę od korzenia, wstawiając x do drzewa. Po tym wstawieniu wszystkie wartości mniejsze niż x zostaną znalezione po lewej stronie ścieżki, a wszystkie wartości większe niż x zostaną znalezione po prawej stronie. Stosując Join , wszystkie poddrzewa po lewej stronie są scalane od dołu do góry za pomocą kluczy na ścieżce jako węzłów pośrednich od dołu do góry, tworząc lewe drzewo, a prawa część jest asymetryczna. W przypadku niektórych aplikacji Split zwraca również wartość logiczną oznaczającą, czy x występuje w drzewie. Koszt podziału to ${\ Displaystyle O (\ log n)}$ , kolejność wysokości drzewa.

Algorytm podziału jest następujący:

             funkcja  split(T, k)  if  (T = nil)  return  (nil, false, nil)  else  (L, m, R) := ujawnij(T)  if  k < m (L', b, R') := split(L, k)  return  (L', b, join(R', m, R))  else if  k > m (L', b, R') := split(R, k)  return  (join(L , m, L'), b, R'))  else  return  (L, true, R) 

Dołącz2

Ta funkcja jest zdefiniowana podobnie jak join , ale bez środkowego klawisza. Najpierw rozdziela ostatni klucz $następnie$ łączy pozostałą część lewego drzewa z prawym drzewem za pomocą ${\ displaystyle k}$ . Algorytm jest następujący:

 funkcja  splitLast(T) (L, k, R) := wyeksponuj(T)  if  R = zero  return  (L, k)  else  (T', k') := splitLast(R)  return  (join(L, k, T'), k')  funkcja  join2(L, R)  if  L = zero  return  R  else  (L', k) := splitLast(L)  return  join(L', k, R) 

Koszt wynosi ${\ Displaystyle O (\ log n)}$ dla drzewa o rozmiarze ${\ displaystyle n}$ .

Wstaw i usuń

Algorytmy wstawiania i usuwania przy użyciu łączenia mogą być niezależne od schematów równoważenia. W celu wstawienia algorytm porównuje klucz, który ma zostać wstawiony, z kluczem w korzeniu, wstawia go do lewego/prawego poddrzewa, jeśli klucz jest mniejszy/większy niż klucz w korzeniu, i ponownie łączy dwa poddrzewa z korzeniem . Usunięcie porównuje klucz do usunięcia z kluczem w katalogu głównym. Jeśli są równe, zwróć join2 na dwóch poddrzewach. W przeciwnym razie usuń klucz z odpowiedniego poddrzewa i połącz oba poddrzewa z korzeniem. Algorytmy są następujące:

             funkcja  insert(T, k)  if  T = nil  return  Node(nil, k, nil)  else  (L, k', R) := wyeksponuj(T)  if  k < k'  return  join(insert(L,k), k', R)  else if  k > k'  return  join(L, k', insert(R, k))  else  return  T  funkcja  delete(T, k)  if  T = zero  return  zero  else 
             (L, k', R) := ujawnij(T)  if  k < k'  return  join(delete(L, k), k', R)  else if  k > k'  return  join(L, k', delete( R, k))  w przeciwnym razie  zwróć  sprzężenie2(L, R) 

$Zarówno$ i usuwanie ${\ Displaystyle | T | = n}$ jeśli .

Funkcje zestaw-ustaw

Na drzewach o zrównoważonych wagach zdefiniowano kilka operacji na zbiorach: suma , przecięcie i różnica zbiorów . Suma dwóch zrównoważonych wagowo drzew t ₁ i t ₂ reprezentujących zbiory A i B , jest drzewem t reprezentującym A ∪ B . Poniższa funkcja rekurencyjna oblicza tę sumę:

    
     funkcja  suma(t  1  , t  2  )  jeśli  t  1  = zero  zwróć  t  2  w przeciwnym razie jeśli  t  2  = zero  zwróć  t  1  w przeciwnym razie  (l  1  , k  1  , r  1  ) := ujawnij (t  1  ) (t  <  , b, t  >  ) := podział(t  2  , k  1  ) l' := suma (l  1  , t  <  ) || r' := suma(r   1  , t  >  )  return  join(l', k  1  , r') 

Podobnie algorytmy przecięcia i różnicy zbiorów są następujące:

 funkcji  (t  1  , t  2  )  jeśli  t  1  = zero  lub  t  2  = zero  zwróć  zero  w przeciwnym razie  (l  1  , k  1  , r  1  ) := ujawnij (t  1  ) (t  <  , b, t  >  ) = podziel (t  2  , k  1  ) l' := punkt przecięcia (l  1  , t  <  ) || r' := przecięcie(r  
            
     1  , t  >  )  jeśli  b  zwróć  sprzężenie(l', k  1  , r')  w przeciwnym razie  zwróć  sprzężenie2(l', r')  funkcja  różnica(t  1  , t  2  )  jeśli  t  1  = zero  zwróć  zero  w przeciwnym razie jeśli  t  2  = nil  return  t  1  else  (l  1  , k  1  , r 
             1  ) := wyeksponuj(t  1  ) (t  <  , b, t  >  ) := podziel(t  2  , k  1  ) l' = różnica (l  1  , t  <  ) || r' = różnica(r   1  , t  >  )  jeśli  b  return  join2(l', r')  w przeciwnym razie  return  join(l', k  1  , r') 

Złożoność każdego związku, przecięcia i różnicy wynosi ${\ Displaystyle O \ lewo (m \ log \ lewo ({\ tfrac {n} {m}} + 1 \ prawo ) \ prawej)}$$\ Displaystyle n (\ geq m)}$ dwóch zrównoważonych wagowo drzew o rozmiarach $)$ n . Ta złożoność jest optymalna pod względem liczby porównań. Co ważniejsze, ponieważ rekurencyjne wywołania sumy, przecięcia lub różnicy są od siebie niezależne, można je wykonywać równolegle z równoległą głębokością ${\ Displaystyle O (\ log m \ log n) }$ . m $\ displaystyle m = 1}$ , implementacja oparta na łączeniu stosuje te same obliczenia, co w przypadku wstawiania lub usuwania pojedynczego elementu, jeśli korzeń większego drzewa jest używany do podziału mniejszego drzewa.

Zbudować

Algorytm budowania drzewa może wykorzystywać algorytm łączenia i schemat dziel i zwyciężaj:

 funkcja  build(A[], n)  if  n = 0  return  nil  else if  n = 1  return  Node(nil, A[0], nil)  else  l' := build(A, n/2) || r' := (A+n/2, nn/2)   powrót  suma(L, R) 

$^ {3} n$ kosztuje pracę i ma głębokość $n )$ Bardziej wydajny algorytm wykorzystuje algorytm sortowania równoległego.

 funkcja  buildSorted(A[], n)  if  n = 0  return  nil  else if  n = 1  return  Node(nil, A[0], nil)  else  l' := build(A, n/2) || r' := (A+n/2+1, nn/2-1)   return  join(l', A[n/2], r') budowanie   funkcji  (A[], n) A' := sort( A, n)  return  buildSorted(A, n) 

Ten $O$$że$ ma ${\ Displaystyle O (n \ log n)}$ _ praca i ${\ Displaystyle O (\ log n)}$ głębokość.

Filtr

$funkcja$ wybiera wszystkie wpisy w drzewie spełniające predykat zwraca drzewo zawierające wszystkie wybrane wpisy. Rekurencyjnie filtruje dwa poddrzewa i łączy je z korzeniem, jeśli korzeń spełnia $w$ przeciwnym razie łączy dwa poddrzewa.

             funkcja  filter(T, p)  if  T = nil  return  nil  else  (l, k, r) := wyeksponuj(T) l' := filter(l, p) || r' := filter(r, p)   if  p(k)  return  join(l', k, r')  w przeciwnym razie  return  join2(l', R) 

Ten algorytm kosztuje pracę i głębokość $) {\ Displaystyle$$(\ log ^ {2} n)}$ o rozmiarze $}$ , zakładając, $że$ stały koszt.

Stosowany w bibliotekach

Algorytmy oparte na łączeniach są stosowane do obsługi interfejsu dla zbiorów , map i rozszerzonych map w bibliotekach takich jak Hackage , SML/NJ i PAM .

Linki zewnętrzne

• PAM , równoległa rozszerzona biblioteka map
• Hackage , Kontenery w Hackage