Range Sum of BST

Q: Apa kompleksitas waktu dari Range Sum of BST?

Traversal yang dipangkas mengunjungi k node dalam rentang serta node pada paling banyak dua jalur dari root: waktu O(h + k) untuk tree dengan kedalaman h , dan O(n) saat setiap nilai berada dalam rentang. Stack atau rekursi menggunakan ruang O(h) .

Q: Bisakah Range Sum of BST diselesaikan dengan traversal in-order?

Ya. Penelusuran secara berurutan mencantumkan nilai dalam urutan menaik, jadi tambahkan nilai saat mencapai low dan berhenti pada nilai pertama yang lebih besar dari high . Berhenti lebih awal menghemat pekerjaan di sisi kanan pohon, sedangkan pemangkasan menghemat pekerjaan di kedua sisi.

Q: Haruskah kamu menggunakan rekursi atau stack untuk Range Sum of BST?

Keduanya berfungsi. Di sini kedalamannya paling banyak 14, jadi rekursi tetap dangkal. Stack eksplisit menghindari batas rekursi pada tree tinggi dengan ribuan tingkat.

MudahBinary search tree Tree traversal

+10

Binary search tree disimpan dalam array tree dengan urutan level: akar berada pada indeks 0, anak dari simpul pada indeks i berada di 2*i+1 (kiri) dan 2*i+2 (kanan), dan -1 menandai posisi kosong. Dalam binary search tree, setiap nilai pada subtree kiri sebuah simpul lebih kecil daripada nilai simpul tersebut, dan setiap nilai pada subtree kanannya lebih besar.

Kembalikan jumlah semua nilai simpul v dengan low ≤ v ≤ high, atau 0 jika tidak ada.

Fungsi

rangeSumBST(tree: integer-array, low: integer, high: integer) → integer

treeinteger-array: pohon pencarian biner dalam urutan level, dengan -1 untuk posisi kosong
lowinteger: nilai terkecil untuk dihitung
highinteger: nilai terbesar yang akan dihitung
Mengembalikaninteger: jumlah nilai node dari low hingga high, termasuk keduanya

Batasan

1 ≤ tree.length ≤ 32767
Setiap tree[i] bernilai -1 atau nilai dengan 0 ≤ tree[i] ≤ 10⁵.
tree[0] tidak pernah -1, jadi tree memiliki setidaknya satu node.
array mungkin diakhiri dengan entri -1 tambahan setelah node terakhir.
Kedua child dari tempat kosong juga kosong, dan kedalamannya paling banyak 14.
Pohon tersebut adalah binary search tree yang valid, jadi semua nilainya berbeda.
0 ≤ low ≤ high ≤ 10⁵
Jawabannya muat dalam bilangan bulat bertanda 32-bit.

Contoh

Input: tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
Output: 88
Penjelasan: Nilai dari 9 hingga 31 adalah 10, 12, 15, 20, dan 31, yang jumlahnya 88. 3, 8, dan 40 berada di luar rentang tersebut.

Input: tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
Output: 0
Penjelasan: Pohon tersebut menyimpan 25, 50, dan 75, dan tidak satu pun berada di antara 60 dan 70, jadi jumlahnya adalah 0. Empat entri -1 adalah posisi anak kosong dari 25 dan 75.

Input: tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
Output: 4
Penjelasan: Dengan low dan high yang keduanya bernilai 4, hanya node dengan nilai 4 yang dihitung. 4 pada indeks 4 adalah anak kanan dari 2, jadi jawabannya adalah 4.

Pertanyaan lanjutan

Jika kamu harus menjawab ribuan kueri (low, high) yang berbeda pada pohon yang sama, bagaimana kamu bisa menjawab setiap kueri dalam waktu O(log n)?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Mengunjungi setiap node dan menjumlahkan nilai dalam rentang sudah benar. Urutan pada pohon pencarian memungkinkan kamu melakukan lebih sedikit pekerjaan: nilai sebuah node menunjukkan sisi mana yang berisi nilai lebih kecil dan lebih besar, sehingga subtree yang tidak mungkin mencapai rentang tersebut tidak pernah dibuka.

Kunjungi setiap simpul

Intuisi

Sebuah anak nyata hanya jika indeksnya berada di dalam array dan nilai di sana bukan -1. Pada contoh pertama, 12 di indeks 4 memiliki 10 dan 15 di indeks 9 dan 10, dan 31 di indeks 2 memiliki posisi kiri kosong di indeks 5.

Setiap nilai dalam rentang berada di suatu node, jadi traversal stack yang mengunjungi setiap node dan menjumlahkan nilai dengan low ≤ v ≤ high akan menghasilkan jumlah yang tepat. Traversal ini mengabaikan urutan pohon pencarian, jadi traversal ini menyentuh semua n node meskipun rentang tersebut hanya mencakup beberapa nilai.

Algoritma

Masukkan indeks akar 0 ke stack dan atur total = 0.
Keluarkan indeks i. Jika low ≤ tree[i] ≤ high, tambahkan tree[i] ke total.
Masukkan 2*i+1 dan 2*i+2 jika keduanya berada di dalam array dan bukan -1.
Saat stack kosong, kembalikan total.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and tree[left] != -1:
            stack.append(left)
        if right < n and tree[right] != -1:
            stack.append(right)
    return total

Pangkas sesuai urutan pohon pencarian

Intuisi

Subtree kiri dari node yang menyimpan v hanya memiliki nilai yang lebih kecil dari v. Jika v ≤ low, tidak ada satu pun nilai di dalam rentang, jadi lewati subtree tersebut. Jika v ≥ high, subtree kanan hanya memiliki nilai yang lebih besar dari high, jadi lewati subtree itu. Pada contoh pertama, 31 sama dengan high, jadi anak kanannya, 40, tidak pernah dimasukkan ke stack. 8 lebih kecil dari low, jadi anak kirinya, 3, dilewati, tetapi anak kanannya, 12, dikunjungi karena nilai di antara 8 dan 20 bisa berada dalam rentang.

Kamu mengunjungi k nilai dalam rentang ditambah node-node pada paling banyak dua jalur dari root: waktu O(h + k) untuk kedalaman h. Saat rentang mencakup seluruh pohon, kompleksitasnya tetap O(n).

Algoritma

Masukkan indeks akar 0 ke dalam tumpukan dan tetapkan total = 0.
Keluarkan indeks i dari tumpukan dan baca v = tree[i]. Jika low ≤ v ≤ high, tambahkan v ke total.
Jika v > low, masukkan anak kiri 2*i+1 ke dalam tumpukan jika anak tersebut ada.
Jika v < high, masukkan anak kanan 2*i+2 ke dalam tumpukan jika anak tersebut ada.
Saat tumpukan kosong, kembalikan total.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        # Smaller values sit on the left, larger on the right: skip a side the range cannot reach.
        if value > low and left < n and tree[left] != -1:
            stack.append(left)
        if value < high and right < n and tree[right] != -1:
            stack.append(right)
    return total

Jebakan dan kasus tepi

Menggunakan perbandingan ketat. Kedua ujungnya dihitung, jadi contoh ketiga, dengan low = high = 4, harus menghitung 4.
Memangkas satu langkah terlalu awal. Pada v = low, subtree kiri dapat diabaikan, tetapi pada v = low + 1, subtree tersebut mungkin memuat low itu sendiri.
Membuang kedua sisi node yang berada di luar rentang. 8 pada contoh pertama lebih kecil dari low, tetapi subtree kanannya memuat 10, 12, dan 15.
Membaca child melewati akhir array. Periksa 2*i+1 < tree.length sebelum membaca, dan anggap -1 berarti tidak ada child.
Di Lua dan R, array dimulai dari 1: pertahankan indeks node berbasis 0 untuk perhitungan 2*i+1 dan baca tree[i + 1].

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Range Sum of BST?

Traversal yang dipangkas mengunjungi k node dalam rentang serta node pada paling banyak dua jalur dari root: waktu O(h + k) untuk tree dengan kedalaman h, dan O(n) saat setiap nilai berada dalam rentang. Stack atau rekursi menggunakan ruang O(h).

Bisakah Range Sum of BST diselesaikan dengan traversal in-order?

Ya. Penelusuran secara berurutan mencantumkan nilai dalam urutan menaik, jadi tambahkan nilai saat mencapai low dan berhenti pada nilai pertama yang lebih besar dari high. Berhenti lebih awal menghemat pekerjaan di sisi kanan pohon, sedangkan pemangkasan menghemat pekerjaan di kedua sisi.

Haruskah kamu menggunakan rekursi atau stack untuk Range Sum of BST?

Keduanya berfungsi. Di sini kedalamannya paling banyak 14, jadi rekursi tetap dangkal. Stack eksplisit menghindari batas rekursi pada tree tinggi dengan ribuan tingkat.

def rangeSumBST(tree, low, high):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]
low = 9
high = 31

Output yang diharapkan