Zrównoważone drzewa wyszukiwania binarnego są niezbędne do zagwarantowania wyszukiwania O (log n) (lub podobnych operacji). W dynamicznym środowisku, w którym wiele kluczy jest losowo wstawianych i / lub usuwanych, drzewa mogą zdegenerować się do połączonych list, które są straszne przy wyszukiwaniu. Tak więc istnieją różne rodzaje równoważących się drzew binarnych, które przeciwdziałają temu efektowi (takie jak drzewa AVL lub drzewa rozrośnięte ). Drzewa te są oparte na różnych rodzajach rotacji, które ponownie równoważą drzewo.

Rotacje

W tym wyzwaniu przyjrzymy się tylko pojedynczym obrotom w prawo, taki obrót (obrót w lewo byłby symetryczny) wygląda następująco:

    5            3
   / \          / \
  3   6   =>   1   5
 / \              / \
1   4            4   6

Jeżeli którykolwiek z liści 1, 4lub 6miał prawo sub-trees lewo lub obrót po prostu trzymać je tam. Jeśli jest to poddrzewo większego drzewa, po prostu „odetniemy” go w węźle 5i „ponownie dołączymy” obrócone drzewo (teraz węzeł 3) do tego węzła.

Wyzwanie

Biorąc pod uwagę drzewo wyszukiwania binarnego ¹ i klucz, obróć drzewo w tym węźle, jak opisano powyżej. Kluczem podanym w powyższym przykładzie byłoby 5.

Reguły i I / O

• możesz użyć dowolnego typu dla kluczy, o ile istnieje sprzeczność między kluczami wybranymi przez ciebie a kluczami przypadków testowych
• możesz wybrać dowolną reprezentację dla drzew binarnych, o ile nie ma dwuznaczności (np. [3,[]]jest niejednoznaczna, chyba że określono inaczej) i jest to naturalne dla wybranego języka
• ponieważ dane wejściowe będą zawsze drzewem wyszukiwania binarnego, nie ma duplikatów kluczy
• możesz założyć, że klucz jest zawarty w drzewie
• możesz założyć, że węzeł zawierający klucz ma lewe dziecko
• możesz nie przyjąć właściwą poddrzewo pod warunkiem kluczem
• możesz nie przyjąć, że drzewo jest niezrównoważony przed obrotem
• możesz nie przyjąć, że drzewo jest równoważony po obrocie
• możesz użyć dowolnej domyślnej metody We / Wy
• Twoje zgłoszenie może być funkcją zwracającą drzewo lub pełny program drukujący rozwiązanie

Przypadki testowe

Te przykłady przedstawiają drzewo w następujący sposób

• jeśli to liść: []
• jeśli jest to drzewo z kluczem, xa oba poddrzewa są liśćmi:[x]
• jeśli jest to drzewo z kluczem xi poddrzewami left right:[x,left,right]

Pierwszym przykładem jest ten przedstawiony w sekcji Obroty . Jeśli z jakiegoś powodu potrzebujesz ich graficznej reprezentacji, oto ² .

5 [5,[3,[1],[4]],[6]]  ->  [3,[1],[5,[4],[6]]]
5 [5,[3,[1],[4]],[]]  ->  [3,[1],[5,[4],[]]]
5 [5,[3,[],[4]],[6]]  ->  [3,[],[5,[4],[6]]]
5 [5,[3,[1],[]],[]]  ->  [3,[1],[5]]
4 [8,[4,[2,[1],[3]],[6,[5],[7]]],[12,[10,[9],[11]],[14,[13],[15]]]]  ->  [8,[2,[1],[4,[3],[6,[5],[7]]]],[12,[10,[9],[11]],[14,[13],[15]]]]
8 [10,[8,[6,[4,[2,[],[3]],[5]],[7]],[9]],[11]]  ->  [10,[6,[4,[2,[],[3]],[5]],[8,[7],[9]]],[11]]
10 [10,[8,[6,[4,[2,[],[3]],[5]],[7]],[9]],[11]]  ->  [8,[6,[4,[2,[],[3]],[5]],[7]],[10,[9],[11]]]
9 [6,[3,[2],[5]],[9,[8],[12,[11],[15,[14],[]]]]]  ->  [6,[3,[2],[5]],[8,[],[9,[],[12,[11],[15,[14],[]]]]]]
7 [7,[5,[3,[1],[4]],[6]],[8]]  ->  [5,[3,[1],[4]],[7,[6],[8]]]
15 [17,[9,[5,[2,[0],[4]],[8]],[15,[13,[11,[10],[12]],[14]],[16]]],[40,[27,[21,[19,[18],[20]],[24,[22],[25]]],[28]],[44,[42,[41],[]],[51,[47],[59,[55],[61]]]]]]  ->  [17,[9,[5,[2,[0],[4]],[8]],[13,[11,[10],[12]],[15,[14],[16]]]],[40,[27,[21,[19,[18],[20]],[24,[22],[25]]],[28]],[44,[42,[41],[]],[51,[47],[59,[55],[61]]]]]]
21 [17,[9,[5,[2,[0],[4]],[8]],[15,[13,[11,[10],[12]],[14]],[16]]],[40,[27,[21,[19,[18],[20]],[24,[22],[25]]],[28]],[44,[42,[41],[]],[51,[47],[59,[55],[61]]]]]]  ->  [17,[9,[5,[2,[0],[4]],[8]],[15,[13,[11,[10],[12]],[14]],[16]]],[40,[27,[19,[18],[21,[20],[24,[22],[25]]]],[28]],[44,[42,[41],[]],[51,[47],[59,[55],[61]]]]]]

^{1: co oznacza, że ​​dla dowolnego węzła wszystkie klucze w lewym poddrzewie będą mniejsze niż ten klucz, a wszystkie klucze w prawym poddrzewie będą większe niż ten}

^{2: aby zapobiec gniciu linków, umieściłem je jako komentarz}

Haskell , 93 92 84 83 82 bajtów

data B=B[B]Int|L
k!B[l@(B[x,y]a),r]n|k<n=B[k!l,r]n|k>n=B[l,k!r]n|1>0=B[x,B[y,r]k]a

Dzięki @BMO, @alephalpha i @Laikoni za bajt każdy i @nimi za osiem bajtów!

Wypróbuj online!

Vim , 25 bajtów

Pobiera dane wejściowe do bufora - klawisz i drzewo oddzielone spacjami. Oczekuje się, że drzewo będzie reprezentowane w następujący sposób:

• liść: []
• węzeł z kluczem k, lewym dzieckiem <left>i prawym dzieckiem <right>:[ k <left><right>]

Nie kważne są spacje wokół klucza , takie rozwiązanie działa w przypadku dowolnych drzew.

"adw/ <C-r>a⏎3dw%l"apr[%xl%i]

Wypróbuj online!

Wyjaśnienie

"adw                           " delete the key and trailing space, keep in register a
    / <C-r>a⏎                  " move cursor to the key surrounded with spaces
             3dw               " remove key and [ (move left node to top)
                %l             " move cursor to the right subtree
                  "ap          " insert key there
                     r[        " insert a [ (appending subtree to key)
                       %       " move to the end of new left subtree
                        x      " remove ] (fix parentheses)
                         l%    " move to the end of new right subtree
                           i]  " insert ] (fix parentheses)

Zapowiedź

Oto podgląd pierwszego przypadku testowego wygenerowanego przez ten skrypt przez Lynn :

Wolfram Language (Mathematica) , 30 bajtów

#2/.a_~b_~c_~#~d_:>b[a,c~#~d]&

Wypróbuj online!

Drzewo reprezentowane w następujący sposób:

• jeśli to liść: $(możesz go zastąpić dowolną wartością, która nie jest kluczem)
• jeśli jest to drzewo z kluczem xi poddrzewami left right:x[left,right]

Na przykład drzewo w pierwszym przypadku testowym jest reprezentowane przez 5[3[1[$,$],4[$,$]],6[$,$]].

Wyjaśnienie:

#2                                the second input
  /.                              replace
    a_~b_~c_~#~d_                 #[b[a,c],d], where # is the first input
                 :>               by
                   b[a,c~#~d]     b[a,#[c,d]]
                             &    define a function

Common Lisp, 146 bajtów

(defun r(k a)(cond((not a)a)((=(car a)k)`(,(caadr a),(cadadr a)(,(car a),(car(cddadr a)),(caddr a))))(t`(,(car a),(r k(cadr a)),(r k(caddr a))))))

Wypróbuj online lub sprawdź wszystkie przypadki testowe!

Drzewo jest reprezentowane w następujący sposób:

• puste drzewo jest reprezentowane jako nil(lub równoważnie w Common Lisp jako pusta lista ())
• niepuste drzewo jest reprezentowane jako lista trzech elementów (node left-subtree right-subtree) (więc liść Ljest reprezentowany jako (L nil nil)).

JavaScript (Node.js) , 70 bajtów

n=>f=a=>n-a[0]?(a[i=n<a[0]?1:2]=f(a[i]),a):(i=a[1],a[1]=i[2],i[2]=a,i)

Wypróbuj online! Link zawiera przypadki testowe. Wszystkie węzły muszą mieć lewy i prawy wpis, ale mogą []wskazywać brak poddrzewa po tej stronie. Jako skrót zestaw testów używa l(N)do wskazania, że Njest liściem i l(N,L)do wskazania, że Nma lewe poddrzewo, Lale nie ma prawego poddrzewo zarówno na wejściu, jak i na wyjściu.

Python 2 , 85 bajtów

R=lambda T,k:k in T and T[1][:2]+[[T[0],T[1][2],T[2]]]or T[:1]+[R(i,k)for i in T[1:]]

Wypróbuj online!

Format wejściowy:

• Drzewo: [KEY, LEFT_SUBTREE, RIGHT_SUBTREE]
• Liść: []

Galaretka , 24 bajty

ñ
Ḣ,1ịṪƊṭ@ṪṭḢð{Ḣ;ç€ɗ¹¡i?

Wypróbuj online!

Ostrzeżenie: zwykle górna linia nie powinna istnieć, a dolna linia powinna mieć a ß, a nieç . Jednak sprytne sztuczki łańcuchowe i ßnie pasują do siebie z powodußzmienna aria. Technicznie rzecz biorąc, mógłbym nadal pominąć górną linię, ale wtedy wynik musiałby być pełnym programem, ponieważ w przeciwnym razie musiałby być włączony jako osobna linia w dowolnym programie, co nie jest możliwe, chyba że mają szczęście. Oznacza to, że niestety dane wyjściowe miałyby dwuznaczną reprezentację, ponieważ po przesłaniu pełnego programu liczy się to, co faktycznie otrzymuje, a nie wynik techniczny przed zamknięciem programu. Aby nie robić bałaganu zarówno z rekurencją, jak i odpowiednią reprezentacją ciągu, postanowiłem przesłać funkcję 2-liniową, w której zadaniem górnej linii jest wywołanie dolnej. Konsekwencja? Ogromna strata 2 cennych i cennych bajtów. W obronie Jelly (i Dennisa, a także każdego innego uczestnika),