Kth Smallest Element in a BST
Kamu mendapat binary search tree sebagai array root dalam urutan heap: root berada di indeks 0, anak-anak dari indeks i berada di 2*i+1 (kiri) dan 2*i+2 (kanan), dan -1 menandai posisi kosong. Array dapat diakhiri dengan entri -1 tambahan. Pada setiap node, subtree kiri hanya berisi nilai yang lebih kecil dan subtree kanan hanya berisi nilai yang lebih besar.
Kembalikan nilai terkecil ke-k di dalam tree, dihitung mulai dari 1.
Fungsi
- rootinteger-array
- pohon pencarian biner dalam urutan level, dengan -1 untuk posisi kosong
- kinteger
- posisi yang dicari dalam urutan menaik, dimulai dari 1
- Mengembalikaninteger
- nilai terkecil ke-k dalam pohon
Batasan
1 ≤ root.length ≤ 32767- Setiap
root[i]adalah-1atau nilai dengan0 ≤ root[i] ≤ 105. root[0]tidak pernah-1, jadi pohon memiliki setidaknya satu simpul.- array tersebut mungkin diakhiri dengan entri
-1tambahan setelah node terakhir. - Kedua child dari spot kosong juga kosong, dan kedalamannya paling banyak
14. - Aturan pengurutan berlaku di setiap node, jadi tidak ada nilai yang muncul dua kali.
1 ≤ k ≤jumlah node dalam pohon.
Contoh
- Input
- root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22]k = 4
- Output
- 29
- Penjelasan
- Dalam urutan menaik, nilainya adalah
6, 17, 22, 29, 41, 65, 90, dan nilai keempat adalah29. Nilai ini adalah yang terbesar dari empat nilai di subtree kiri root.
- Input
- root = [12, 5, -1, 2, 9, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1]k = 1
- Output
- 2
- Penjelasan
- Nilai terkecil mengakhiri jalur yang terus bergerak ke kiri:
12,5,2.7di bawah9dan padding-1tidak mengubahnya.
Pertanyaan lanjutan
Jika tree sering berubah dan kamu diminta mencari nilai terkecil ke-k berkali-kali, apa yang dapat disimpan setiap node agar setiap kueri membutuhkan waktu O(h)?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Penelusuran binary search tree dengan cara apa yang mencantumkan nilainya dari yang terkecil hingga terbesar?
Mengunjungi subpohon kiri, lalu simpul, lalu subpohon kanan menghasilkan urutan terurut. Nilai ke-
kyang dihasilkan penelusuran itu adalah jawabannya, jadi kamu bisa berhenti di sana.Gunakan stack. Dari node saat ini, push node sambil bergerak ke child kiri. Pop bagian teratas dan hitung; berhenti pada pop ke-
k. Jika tidak, pindah ke child kanan node yang di-pop pada2*i+2dan ulangi.
Solusi
Penelusuran inorder (subpohon kiri, node, subpohon kanan) membaca nilai-nilai binary search tree dalam urutan menaik, jadi nilai ke-k yang dicapainya adalah jawabannya. Jalankan penelusuran menggunakan stack buatanmu sendiri dan berhenti saat itu, tidak perlu melakukan pengurutan.
Kumpulkan setiap nilai dan urutkan
Intuisi
Abaikan bentuknya: pertahankan setiap entri yang bukan -1, urutkan, lalu kembalikan posisi k-1. Untuk contoh pertama, list yang sudah diurutkan adalah 6, 17, 22, 29, 41, 65, 90, dan posisi 3 berisi 29.
Ini benar untuk tree apa pun, baik yang terurut maupun tidak. Itulah juga biayanya: cara ini mengabaikan urutan yang sudah dimiliki tree, serta membutuhkan O(n log n) untuk pengurutan dan memori O(n) untuk salinannya.
Algoritma
- Kumpulkan setiap entri
rootyang bukan-1. - Urutkan nilai yang dikumpulkan dari yang terkecil ke yang terbesar.
- Kembalikan nilai pada posisi
k-1.
def kthSmallest(root, k):
values = [v for v in root if v != -1] # every node, in any order
values.sort()
return values[k - 1]Penelusuran inorder ke dalam list
Intuisi
Di bawah setiap node, subtree kiri hanya menyimpan nilai yang lebih kecil dan subtree kanan hanya menyimpan nilai yang lebih besar. Kunjungi subtree kiri, lalu node, lalu subtree kanan, dan lakukan hal yang sama di setiap subtree: setiap node berada setelah semua nilai yang lebih kecil dan sebelum semua nilai yang lebih besar, sehingga output terurut. Pada contoh pertama, penelusuran menghasilkan 6, 17, 22, 29, 41, 65, 90.
Satu kali penelusuran menggantikan proses pengurutan: waktu O(n), dan ruang O(n) untuk list. Penelusuran tetap mengunjungi seluruh tree, bahkan untuk k = 1, saat jawabannya berada di ujung jalur paling kiri.
Algoritma
- Tulis
inorder(i): kembalikan nilai saat berada di posisi kosong (melewati akhir atau-1). - Jika tidak, panggil
inorder(2*i+1), tambahkanroot[i]ke list, lalu panggilinorder(2*i+2). - Panggil
inorder(0). - Kembalikan entri list pada posisi
k-1.
def kthSmallest(root, k):
n = len(root)
values = []
def inorder(i):
if i >= n or root[i] == -1:
return
inorder(2 * i + 1) # smaller values first
values.append(root[i])
inorder(2 * i + 2) # then larger ones
inorder(0)
return values[k - 1] # values is sortedIn-order iteratif yang berhenti pada k
Intuisi
Stack eksplisit memungkinkan kamu menghentikan penelusuran di tengah jalan. Telusuri ke kiri sejauh mungkin, sambil memasukkan setiap node ke stack. Node di bagian teratas adalah nilai terkecil yang belum dihitung, karena semua nilai yang lebih kecil berada di subtree kirinya, yang kosong atau sudah dihitung. Keluarkan node itu dari stack dan hitung nilainya, lalu subtree kanannya menjadi urutan berikutnya.
Untuk k = 4 pada contoh pertama: masukkan 41, 17, 6 ke stack. Keluarkan 6, lalu 17, dan pindah ke anak kanannya: masukkan 29 dan 22 ke stack. Keluarkan 22, lalu 29, nilai keempat. Penelusuran tidak pernah mencapai 65 atau 90.
Stack menampung paling banyak satu node per level, jadi penggunaan ruangnya adalah O(h). Penelusuran turun satu kali lalu mengeluarkan node dari stack sebanyak k kali: waktu O(h + k).
Algoritma
- Mulai dengan stack kosong dan
i = 0. - Selama
iadalah simpul nyata, masukkan ke stack dan pindah ke2*i+1. - Keluarkan elemen teratas ke
idan kurangiksebesar1. - Jika sekarang
kbernilai0, kembalikanroot[i]. - Jika tidak, pindah ke
2*i+2dan kembali ke langkah 2.
def kthSmallest(root, k):
n = len(root)
stack = [] # nodes whose left side is being visited, deepest on top
i = 0
while True:
while i < n and root[i] != -1: # go as far left as you can
stack.append(i)
i = 2 * i + 1
i = stack.pop() # the smallest value not counted yet
k -= 1
if k == 0:
return root[i]
i = 2 * i + 2 # then everything in its right subtree
Jebakan dan kasus tepi
- Membaca array berdasarkan urutan indeks. Urutan level tidak diurutkan: contoh pertama dimulai dengan
41, 17, 65. - Kesalahan satu angka pada
k. Penghitungan dimulai dari1: kembalikan posisik-1dalam list, lalu hentikan penelusuran saat hitungan mencapaik. - Melewatkan subtree kanan setelah melakukan pop. Pada contoh kedua,
9dan7berada di subtree kanan dari5, dan penelusuran tidak akan pernah menghitungnya. - Menganggap anak yang tidak ada sebagai anak sungguhan. Anak dianggap kosong jika indeksnya melewati batas akhir atau berisi
-1:22berada pada indeks9, jadi anak-anaknya,19dan20, melewati batas akhir. - Array Lua dan R dimulai dari 1. Pertahankan indeks node berbasis 0 untuk
2*i+1dan bacaroot[i + 1].
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu untuk menemukan elemen terkecil ke-k dalam BST?
Penelusuran in-order iteratif membutuhkan waktu O(h + k) dan ruang tambahan O(h) untuk pohon dengan kedalaman h. Dalam kasus terburuk, yaitu saat k = n atau pohon berbentuk seperti jalur, kompleksitasnya adalah O(n).
Bagaimana cara menemukan elemen terbesar ke-k dalam BST?
Balik urutannya: subtree kanan, lalu node, lalu subtree kiri. Urutan ini mencantumkan nilai dari terbesar ke terkecil. Pergi sejauh mungkin ke kanan sambil melakukan push, lalu lakukan pop dan hitung, kemudian pindah ke child kiri setelah setiap pop. Pop ke-k adalah nilai terbesar ke-k.
Bagaimana cara menghentikan penelusuran in-order rekursif pada nilai ke-k?
Simpan penghitung di luar rekursi, mulai dari k. Kurangi 1 setelah subpohon kiri sebuah node selesai diproses, lalu catat nilai node saat penghitung mencapai 0. Setelah setiap pemanggilan, segera kembalikan hasil jika jawabannya sudah dicatat. Rekursi ini lalu memiliki kompleksitas yang sama dengan versi stack: waktu O(h + k), ruang O(h).
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def kthSmallest(root, k):
# Tulis kodemu di siniTes #1
Tes #2
Argumen
root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22] k = 4
Output yang diharapkan
29