Pohon pencarian biner seimbang sangat penting untuk menjamin pencarian O (log n) (atau operasi serupa). Dalam lingkungan yang dinamis di mana banyak kunci dimasukkan secara acak dan / atau dihapus, pohon mungkin berubah menjadi daftar yang ditautkan yang mengerikan untuk pencarian. Jadi ada berbagai jenis pohon biner yang dapat menyeimbangkan diri sendiri yang menetralkan efek ini (seperti pohon AVL atau pohon tebar ). Pohon-pohon ini didasarkan pada berbagai jenis rotasi yang menyeimbangkan kembali pohon.
Rotasi
Dalam tantangan ini kita hanya akan melihat rotasi kanan tunggal, rotasi seperti itu (rotasi kiri simetris) terlihat seperti ini:
5 3
/ \ / \
3 6 => 1 5
/ \ / \
1 4 4 6
Jika ada dedaunan 1
, 4
atau 6
memiliki sub-pohon kiri atau kanan rotasi hanya akan membuat mereka tetap di sana. Jika ini adalah subtree dari pohon yang lebih besar, kita cukup "memotongnya" pada node 5
dan "melampirkan kembali" pohon yang diputar (sekarang node 3
) ke node itu.
Tantangan
Diberikan pohon pencarian biner 1 dan tombol kanan-putar pohon pada simpul itu seperti yang dijelaskan di atas. Kunci yang disediakan dalam contoh di atas adalah 5
.
Aturan dan I / O
- Anda dapat menggunakan jenis apa saja untuk kunci selama ada penipisan antara kunci pilihan Anda dan orang-orang dari kasus uji
- Anda dapat memilih representasi untuk pohon biner selama tidak ada ambiguitas (mis.
[3,[]]
ambigu kecuali dinyatakan lain) dan itu wajar untuk bahasa pilihan Anda - karena input akan selalu menjadi pohon pencarian biner tidak ada kunci duplikat
- Anda dapat mengasumsikan bahwa kunci tersebut terkandung dalam pohon
- Anda dapat mengasumsikan bahwa simpul yang berisi kunci memiliki anak kiri
- Anda mungkin tidak menganggap subtree kanan di bawah kunci yang disediakan
- Anda mungkin tidak berasumsi bahwa pohon tidak seimbang sebelum rotasi
- Anda mungkin tidak menganggap bahwa pohon seimbang setelah rotasi
- Anda dapat menggunakan metode I / O standar apa pun
- kiriman Anda mungkin merupakan fungsi mengembalikan pohon atau program lengkap mencetak solusi
Uji kasus
Contoh-contoh ini mewakili pohon sebagai berikut
- jika daun:
[]
- Jika itu pohon dengan kunci
x
dan kedua subtree adalah daun:[x]
- jika itu pohon dengan kunci
x
dan subtreeleft
right
:[x,left,right]
Contoh pertama adalah yang disediakan di Rotasi bagian . Jika karena alasan tertentu Anda memerlukan representasi grafis dari mereka, di sini 2 Anda pergi.
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: artinya untuk setiap simpul semua kunci di subtree kiri akan lebih kecil dari kunci itu dan semua kunci di subtree kanan lebih besar dari itu
2: untuk mencegah pembusukan tautan, saya menyematkannya sebagai komentar
data B=B[B]Int
akan menghemat lebih banyak byte.k<n=B[k!l,r]n
dank>n=B[l,k!r]n
menjadi satu:,k/=n=B[k!l,k!r]n
dan kemudian menambahkank!x=x
untuk membuat pencocokan pola yang lengkap.Vim , 25 byte
Mengambil input dalam buffer - spasi kunci dan pohon terpisah. Pohon itu diharapkan diwakili sebagai berikut:
[]
k
, anak kiri<left>
dan anak kanan<right>
:[ k <left><right>]
Bukan ruang di sekitar kunci
k
yang penting, sehingga solusinya bekerja untuk pohon yang sewenang-wenang.Cobalah online!
Penjelasan
Pratinjau
Berikut ini preview dari test case pertama, yang dibuat dengan skrip ini oleh Lynn :
sumber
Bahasa Wolfram (Mathematica) , 30 byte
Cobalah online!
Sebuah pohon diwakili sebagai berikut:
$
(Anda dapat menggantinya dengan nilai apa pun yang bukan kunci)x
dan subtreeleft
right
:x[left,right]
Misalnya, pohon dalam kasus uji pertama diwakili oleh
5[3[1[$,$],4[$,$]],6[$,$]]
.Penjelasan:
sumber
Gangguan Umum, 146 byte
Cobalah online atau verifikasi semua testcases!
Sebuah pohon direpresentasikan sebagai berikut:
nil
(atau setara dalam Common Lisp sebagai daftar kosong()
)(node left-subtree right-subtree)
(sehingga daunL
direpresentasikan sebagai(L nil nil)
).sumber
JavaScript (Node.js) , 70 byte
Cobalah online! Tautan termasuk kasus uji. Semua node harus memiliki entri kiri dan kanan tetapi mereka dapat
[]
menunjukkan tidak ada subtree di sisi itu. Sebagai singkatan, test suite digunakanl(N)
untuk menunjukkan bahwa ituN
adalah daun danl(N,L)
untuk menunjukkan yangN
memiliki subtree kiriL
tetapi tidak subtree kanan baik pada input dan output.sumber
Python 2 , 85 byte
Cobalah online!
Masukkan format:
[KEY, LEFT_SUBTREE, RIGHT_SUBTREE]
[]
sumber
Jelly , 24 byte
Cobalah online!
Peringatan: Biasanya, garis paling atas seharusnya tidak ada, dan garis bawah seharusnya memiliki
ß
, bukan aç
. Namun, trik rantai pintar danß
tidak berjalan bersama dengan baik, karenaß
variabel arity. Secara teknis, saya masih bisa menghilangkan baris teratas, tetapi hasilnya akan menjadi program penuh, karena jika tidak maka harus dapat dimasukkan sebagai baris sendiri di dalam program apa pun, yang tidak mungkin kecuali Anda beruntung Ini berarti bahwa, sayangnya, output akan memiliki representasi yang ambigu, karena, ketika Anda mengirimkan program lengkap, apa yang benar-benar menghasilkan jumlah output, dan bukan apa hasilnya secara teknis sebelum program ditutup. Jadi, agar tidak membuat kekacauan dengan rekursi dan representasi string yang tepat, saya telah memutuskan untuk menyerahkan fungsi 2-baris, di mana pekerjaan baris atas adalah memanggil yang bawah. Konsekuensinya? Buang besar 2 byte berharga dan berharga. Dalam pertahanan Jelly (dan Dennis, serta setiap kontributor lainnya),sumber