Validate Binary Search Tree
Pohon biner disimpan dalam array tree dengan urutan heap: akar berada di indeks 0, anak-anak dari indeks i berada di 2*i+1 (kiri) dan 2*i+2 (kanan), -1 menandai tempat kosong, dan array dapat diakhiri dengan entri -1 tambahan.
Tulis isValidBST, yang mengembalikan true jika pohon tersebut adalah pohon pencarian biner dan false jika tidak. Dalam pohon pencarian biner, nilai setiap node harus lebih besar secara ketat daripada setiap nilai di subtree kirinya dan lebih kecil secara ketat daripada setiap nilai di subtree kanannya.
Fungsi
- treeinteger-array
- pohon biner dalam urutan level, dengan -1 untuk posisi kosong
- Mengembalikanboolean
- true jika pohon tersebut adalah pohon pencarian biner, false jika tidak
Batasan
1 ≤ tree.length ≤ 32767- Setiap
tree[i]bernilai-1atau nilai dengan0 ≤ tree[i] ≤ 105. tree[0]tidak pernah-1, jadi pohon memiliki setidaknya satu node.- array tersebut mungkin diakhiri dengan entri
-1tambahan setelah node terakhir. - Kedua anak dari posisi kosong juga kosong, dan kedalamannya paling banyak
14. - Nilai dapat berulang.
Contoh
- Input
- tree = [8, 3, 12, 1, 6, 10, 15]
- Output
- true
- Penjelasan
- Jika dibaca secara berurutan (subtree kiri, node, subtree kanan), nilainya adalah
1, 3, 6, 8, 10, 12, 15. Nilai-nilai tersebut meningkat secara ketat, jadi setiap node berada di sisi yang benar dari setiap leluhur.
- Input
- tree = [10, 5, 15, -1, -1, 6, 20]
- Output
- false
- Penjelasan
- Setiap node lebih besar daripada child kirinya dan lebih kecil daripada child kanannya, tetapi
6pada indeks5berada di subtree kanan root, jadi nilainya harus lebih besar daripada10.
- Input
- tree = [12, 7, 12]
- Output
- false
- Penjelasan
- Anak kanan root menyimpan
12, sama dengan root. Subtree kanan harus lebih besar secara ketat, jadi tree ini tidak valid.
Pertanyaan lanjutan
Simpul induk sebuah node berada pada indeks (i-1)/2, dibulatkan ke bawah. Bisakah kamu menelusuri tree secara berurutan dengan ruang tambahan O(1), berpindah melalui simpul induk alih-alih menggunakan stack atau rekursi?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Dalam
[10, 5, 15, -1, -1, 6, 20], setiap simpul lebih besar daripada anak kirinya dan lebih kecil daripada anak kanannya. Mengapa ini tetap bukan pohon pencarian?Setiap leluhur menetapkan batas untuk sebuah node: di bawahnya jika node berada di sebelah kiri, di atasnya jika node berada di sebelah kanan. Batas-batas itu bersama-sama membentuk satu rentang terbuka. Bergerak ke kiri dari nilai
vmenurunkan batas atas menjadiv; bergerak ke kanan menaikkan batas bawah menjadiv.Simpan stack berisi
(index, low, high), dimulai dari akar dengan rentang yang lebih lebar daripada setiap nilai yang diizinkan. Keluarkan satu entri, nyatakan gagal jika nilainya tidak berada di dalam rentang secara ketat, lalu masukkan setiap anak yang nyata dengan rentang yang sudah dipersempit.
Solusi
Aturan ini berlaku untuk seluruh subtree, jadi membandingkan setiap node dengan kedua anaknya saja tidak cukup: node yang berada jauh di dalam pohon bisa melanggar batas yang ditetapkan oleh leluhur beberapa tingkat di atasnya. Kamu bisa membaca pohon secara berurutan dan memeriksa bahwa nilainya terus meningkat, atau memberikan setiap node rentang nilai yang diizinkan oleh leluhurnya.
Bandingkan setiap node dengan seluruh subtree-nya
Intuisi
Setiap nilai pada sisi kiri node berada di bawah nilainya v tepat ketika nilai terbesar di sisi itu berada di bawah v, dan setiap nilai pada sisi kanannya berada di atas v tepat ketika nilai terkecil di sisi itu berada di atas v. Dua fungsi pembantu rekursif menemukannya. Sisi yang kosong menghasilkan -1 atau 100001, yang berada di luar rentang nilai, sehingga tidak pernah menyebabkan kegagalan.
Setiap node dipindai sekali untuk setiap leluhurnya, sekitar n × h kunjungan untuk pohon dengan kedalaman h. Dengan kedalaman paling banyak 14, cara ini cukup efisien, tetapi pada jalur yang terdiri dari n node, kompleksitasnya meningkat menjadi O(n²).
Algoritma
- Periksa setiap indeks
iyang nilainya bukan-1. - Cari nilai terbesar di subtree kiri pada
2*i+1(-1jika kosong) dan nilai terkecil di subtree kanan pada2*i+2(100001jika kosong). - Jika nilai terbesar setidaknya sama dengan
tree[i], atau nilai terkecil paling banyak sama dengantree[i], kembalikanfalse. - Kembalikan
true.
def isValidBST(tree):
n = len(tree)
def largest(i):
# Largest value in the subtree at index i, or -1 when that spot is empty.
if i >= n or tree[i] == -1:
return -1
return max(tree[i], largest(2 * i + 1), largest(2 * i + 2))
def smallest(i):
# Smallest value in the subtree at index i, or 100001 when that spot is empty.
if i >= n or tree[i] == -1:
return 100001
return min(tree[i], smallest(2 * i + 1), smallest(2 * i + 2))
for i in range(n):
if tree[i] == -1:
continue
# Everything on the left must be smaller, everything on the right larger.
if largest(2 * i + 1) >= tree[i] or smallest(2 * i + 2) <= tree[i]:
return False
return TrueNilai in-order harus meningkat secara ketat
Intuisi
Penelusuran in-order mengunjungi subtree kiri, lalu node, kemudian subtree kanan, sehingga pada binary search tree, nilai-nilainya terbaca dalam urutan terurut.
Hal sebaliknya juga berlaku. Untuk node v mana pun, seluruh subtree kirinya muncul tepat sebelumnya dalam urutan, dan seluruh subtree kanannya muncul tepat sesudahnya. Jika urutannya meningkat secara ketat, setiap nilai sebelum v lebih kecil dan setiap nilai sesudahnya lebih besar, sehingga aturan ini berlaku pada v, dan juga pada setiap node.
Contoh kedua menghasilkan 5, 10, 6, 15, 20: penurunan dari 10 ke 6 menunjukkan node yang salah tempat. Setiap node dikunjungi satu kali: waktu O(n), dan ruang O(n) untuk list.
Algoritma
- Tulis
walk(i): jika posisi tersebut kosong, berhenti; jika tidak, telusuri2*i+1, tambahkantree[i], lalu telusuri2*i+2. - Panggil
walk(0)untuk mengumpulkan nilai secara berurutan. - Untuk setiap posisi
kmulai dari1, jikavalues[k-1] ≥ values[k], kembalikanfalse. - Kembalikan
true.
def isValidBST(tree):
n = len(tree)
values = []
def walk(i):
# Left subtree, then the node, then the right subtree.
if i >= n or tree[i] == -1:
return
walk(2 * i + 1)
values.append(tree[i])
walk(2 * i + 2)
walk(0)
# A search tree read in order gives strictly increasing values.
for k in range(1, len(values)):
if values[k - 1] >= values[k]:
return False
return TrueBawa rentang yang diizinkan ke bawah pohon
Intuisi
Setiap leluhur memberi satu batas pada sebuah node: di bawah a jika node berada di subtree kiri leluhur yang menyimpan a, di atas a jika node berada di subtree kanan. Jika digabungkan, batas-batas ini membentuk satu rentang terbuka (low, high), dan node berada di tempat yang tepat hanya jika nilainya terletak di dalam rentang tersebut.
Bangun rentang saat menelusuri ke bawah. Anak kiri mempertahankan low dan mendapat high = v; anak kanan mempertahankan high dan mendapat low = v. Pada contoh kedua, 15 meneruskan (10, 15) kepada anak kirinya, dan 6 langsung gagal. Nilai berada di antara 0 dan 10^5, jadi -1 dan 100001 berfungsi sebagai batas tak terhingga. Setiap node diperiksa satu kali, dengan waktu O(n) dan O(h) node di stack.
Algoritma
- Masukkan
(0, -1, 100001): akar, tanpa batas sebenarnya. - Keluarkan
(i, low, high). Jikatree[i]tidak berada di antaralowdanhighsecara ketat, kembalikanfalse. - Masukkan setiap anak yang ada: anak kiri pada
2*i+1dengan(low, tree[i]), anak kanan pada2*i+2dengan(tree[i], high). - Jika stack kosong, kembalikan
true.
def isValidBST(tree):
n = len(tree)
# Each entry: a node index and the open range (low, high) its value must fall in.
# -1 and 100001 lie outside every allowed value, so they mean "no limit".
stack = [(0, -1, 100001)]
while stack:
i, low, high = stack.pop()
value = tree[i]
if not (low < value < high):
return False
left, right = 2 * i + 1, 2 * i + 2
if left < n and tree[left] != -1:
stack.append((left, low, value)) # the left side must stay below value
if right < n and tree[right] != -1:
stack.append((right, value, high)) # the right side must stay above value
return True
Jebakan dan kasus tepi
- Membandingkan sebuah node hanya dengan anak-anaknya. Dalam
[10, 5, 15, -1, -1, 6, 20], setiap pasangan parent dan anak tampak benar, tetapi6melanggar batas root. - Membolehkan nilai yang sama.
[12, 7, 12]tidak valid: gunakan perbandingan dengan<, jangan pernah≤. - Menggunakan
0sebagai batas bawah yang berarti "tanpa batas". Ini menolak tree valid[0]. - Membaca anak tanpa memeriksa
2*i+1 < tree.length. Dalam[12, 7, 12], indeks3berada di luar batas. - Di Lua dan R, array dimulai dari 1. Pertahankan indeks node berbasis 0 untuk
2*i+1dan bacatree[i + 1].
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu untuk memvalidasi binary search tree?
Pemeriksaan in-order dan pemeriksaan rentang mengunjungi setiap node satu kali: waktu O(n), dengan ruang tambahan O(h) untuk stack pemeriksaan rentang pada tree dengan kedalaman h. Membandingkan setiap node dengan seluruh subtree-nya membutuhkan biaya O(n × h), yang mencapai O(n²) pada tree yang berbentuk seperti jalur.
Bisakah kamu memvalidasi BST dengan penelusuran inorder tanpa menyimpan setiap nilai?
Ya. Pemeriksaan hanya membandingkan setiap nilai dengan nilai sebelumnya, jadi simpan nilai sebelumnya dalam variabel, bukan dalam list, lalu kembalikan false saat suatu nilai tidak lebih besar. Ruang tambahan berkurang menjadi O(h) untuk rekursi atau stack.
Apakah binary search tree dapat berisi nilai duplikat?
Tidak menurut definisi ketat yang digunakan di sini: nilai yang sama tidak cocok di kedua sisi. Beberapa buku teks mengizinkan nilai yang sama di satu sisi, misalnya sisi kanan. Menurut aturan itu, salah satu perbandingan ketat menjadi ≤.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def isValidBST(tree):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
tree = [8, 3, 12, 1, 6, 10, 15]
Output yang diharapkan
true