Range Sum of BST

Q: Độ phức tạp thời gian của bài toán tính tổng trong một phạm vi của cây BST là bao nhiêu?

Phép duyệt đã cắt tỉa đi qua k nút trong phạm vi cùng các nút trên tối đa hai đường đi từ nút gốc: thời gian O(h + k) cho cây có độ sâu h , và O(n) khi mọi giá trị đều nằm trong phạm vi. Ngăn xếp hoặc đệ quy cần O(h) không gian.

Q: Liệu có thể giải bài toán tính tổng phạm vi của cây BST bằng cách duyệt theo thứ tự giữa không?

Đúng vậy. Duyệt theo thứ tự sẽ liệt kê các giá trị theo thứ tự tăng dần, vì vậy bạn thêm các giá trị khi chúng đạt đến low và dừng ở giá trị đầu tiên lớn hơn high . Việc dừng sớm giúp tiết kiệm công sức ở phía bên phải của cây, còn cắt tỉa giúp tiết kiệm công sức ở cả hai phía.

Q: Bạn nên dùng đệ quy hay ngăn xếp để tính tổng phạm vi của cây BST?

Cả hai cách đều dùng được. Ở đây, độ sâu tối đa là 14, nên đệ quy vẫn nông. Dùng ngăn xếp tường minh giúp tránh giới hạn đệ quy khi cây cao với hàng nghìn cấp.

DễCây nhị phân tìm kiếm Duyệt cây

+10

Cây tìm kiếm nhị phân được lưu trong mảng tree theo thứ tự từng mức: nút gốc nằm ở chỉ số 0, các nút con của nút ở chỉ số i nằm tại 2*i+1 (bên trái) và 2*i+2 (bên phải), còn -1 đánh dấu vị trí trống. Trong cây tìm kiếm nhị phân, mọi giá trị trong cây con bên trái của một nút đều nhỏ hơn giá trị của nút đó, còn mọi giá trị trong cây con bên phải đều lớn hơn.

Trả về tổng giá trị của tất cả các nút v thỏa mãn low ≤ v ≤ high, hoặc 0 nếu không có nút nào như vậy.

Hàm

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

treeinteger-array: cây tìm kiếm nhị phân theo thứ tự từng mức, dùng -1 cho vị trí trống
lowinteger: giá trị nhỏ nhất cần đếm
highinteger: giá trị lớn nhất cần đếm
Trả vềinteger: tổng các giá trị nút từ low đến high, bao gồm cả hai

Ràng buộc

1 ≤ tree.length ≤ 32767
Mỗi tree[i] là -1 hoặc một giá trị thỏa mãn 0 ≤ tree[i] ≤ 10⁵.
tree[0] không bao giờ là -1, vì vậy cây có ít nhất một nút.
Mảng có thể kết thúc bằng các phần tử -1 thừa sau nút cuối cùng.
Cả hai nút con của một vị trí trống cũng đều trống, và độ sâu tối đa là 14.
Cây tìm kiếm nhị phân (binary search tree) này hợp lệ, vì vậy mọi giá trị trong cây đều khác nhau.
0 ≤ low ≤ high ≤ 10⁵
Câu trả lời nằm trong phạm vi số nguyên có dấu 32 bit.

Ví dụ

Đầu vào: tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
Đầu ra: 88
Giải thích: Các giá trị từ 9 đến 31 là 10, 12, 15, 20 và 31, cộng lại bằng 88. Các giá trị 3, 8 và 40 nằm ngoài phạm vi.

Đầu vào: tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
Đầu ra: 0
Giải thích: Cây chứa 25, 50 và 75, không giá trị nào nằm trong khoảng từ 60 đến 70, nên tổng là 0. Bốn giá trị -1 là các vị trí con trống của 25 và 75.

Đầu vào: tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
Đầu ra: 4
Giải thích: Khi cả low và high đều bằng 4, chỉ nút có giá trị 4 mới được tính. 4 ở chỉ số 4 là con phải của 2, nên đáp án là 4.

Câu hỏi mở rộng

Nếu phải trả lời hàng nghìn truy vấn (query) (low, high) khác nhau trên cùng một cây, bạn có thể trả lời mỗi truy vấn trong thời gian O(log n) như thế nào?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Duyệt qua mọi nút và cộng các giá trị nằm trong phạm vi là đúng. Thứ tự trong cây tìm kiếm giúp bạn làm ít hơn: giá trị của một nút cho biết phía nào chứa các giá trị nhỏ hơn và phía nào chứa các giá trị lớn hơn, vì vậy bạn không bao giờ mở một cây con không thể có giá trị nằm trong phạm vi.

Ghé thăm mọi nút

Ý tưởng

Một nút con chỉ tồn tại nếu chỉ số của nó nằm trong mảng và giá trị ở đó không phải là -1. Trong ví dụ đầu tiên, 12 ở chỉ số 4 có 10 và 15 ở các chỉ số 9 và 10, còn 31 ở chỉ số 2 có vị trí bên trái trống tại chỉ số 5.

Mọi giá trị trong phạm vi đều nằm trong một nút, vì vậy phép duyệt bằng ngăn xếp đi qua mọi nút và cộng các giá trị thỏa mãn low ≤ v ≤ high sẽ cho tổng chính xác. Cách này bỏ qua thứ tự của cây tìm kiếm, nên chạm đến cả n nút ngay cả khi phạm vi chỉ chứa một vài giá trị.

Thuật toán

Đẩy chỉ số gốc 0 vào ngăn xếp và đặt total = 0.
Lấy chỉ số i ra khỏi ngăn xếp. Nếu low ≤ tree[i] ≤ high, cộng tree[i] vào total.
Đẩy 2*i+1 và 2*i+2 vào ngăn xếp nếu chúng nằm trong mảng và không phải -1.
Khi ngăn xếp trống, trả về 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

Cắt tỉa theo thứ tự của cây tìm kiếm

Ý tưởng

Cây con bên trái của một nút chứa v chỉ có các giá trị nhỏ hơn v. Nếu v ≤ low, không có giá trị nào trong số đó nằm trong phạm vi, vì vậy hãy bỏ qua cây con này. Nếu v ≥ high, cây con bên phải chỉ có các giá trị lớn hơn high, vì vậy hãy bỏ qua cây con đó. Trong ví dụ đầu tiên, 31 bằng high, nên nút con bên phải 40 không bao giờ được đưa vào ngăn xếp. 8 nhỏ hơn low, nên bỏ qua nút con bên trái 3, nhưng vẫn duyệt nút con bên phải 12, vì các giá trị nằm giữa 8 và 20 có thể thuộc phạm vi.

Bạn duyệt k giá trị trong phạm vi cùng các nút trên tối đa hai đường đi từ gốc: thời gian O(h + k) với độ sâu h. Khi phạm vi bao phủ toàn bộ cây, độ phức tạp vẫn là O(n).

Thuật toán

Đẩy chỉ số gốc 0 vào ngăn xếp và đặt total = 0.
Lấy chỉ số i ra và đọc v = tree[i]. Nếu low ≤ v ≤ high, cộng v vào total.
Nếu v > low, đẩy nút con bên trái 2*i+1 vào ngăn xếp nếu nút đó tồn tại.
Nếu v < high, đẩy nút con bên phải 2*i+2 vào ngăn xếp nếu nút đó tồn tại.
Khi ngăn xếp trống, trả về 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

Lỗi thường gặp và trường hợp biên

Dùng phép so sánh nghiêm ngặt. Tính cả hai đầu mút, nên ví dụ thứ ba, với low = high = 4, phải tính cả 4.
Cắt tỉa sớm hơn một bước. Khi v = low, có thể bỏ cây con bên trái, nhưng khi v = low + 1, cây con đó có thể chứa chính low.
Bỏ cả hai phía của một nút nằm ngoài phạm vi. Giá trị 8 trong ví dụ đầu tiên nhỏ hơn low, nhưng cây con bên phải của nó chứa 10, 12 và 15.
Đọc nút con vượt quá cuối mảng. Kiểm tra 2*i+1 < tree.length trước khi đọc, và xem -1 là không có nút con.
Trong Lua và R, mảng bắt đầu từ 1: giữ chỉ số nút ở dạng bắt đầu từ 0 để dùng phép tính 2*i+1, và đọc tree[i + 1].

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán tính tổng trong một phạm vi của cây BST là bao nhiêu?

Phép duyệt đã cắt tỉa đi qua k nút trong phạm vi cùng các nút trên tối đa hai đường đi từ nút gốc: thời gian O(h + k) cho cây có độ sâu h, và O(n) khi mọi giá trị đều nằm trong phạm vi. Ngăn xếp hoặc đệ quy cần O(h) không gian.

Liệu có thể giải bài toán tính tổng phạm vi của cây BST bằng cách duyệt theo thứ tự giữa không?

Đúng vậy. Duyệt theo thứ tự sẽ liệt kê các giá trị theo thứ tự tăng dần, vì vậy bạn thêm các giá trị khi chúng đạt đến low và dừng ở giá trị đầu tiên lớn hơn high. Việc dừng sớm giúp tiết kiệm công sức ở phía bên phải của cây, còn cắt tỉa giúp tiết kiệm công sức ở cả hai phía.

Bạn nên dùng đệ quy hay ngăn xếp để tính tổng phạm vi của cây BST?

Cả hai cách đều dùng được. Ở đây, độ sâu tối đa là 14, nên đệ quy vẫn nông. Dùng ngăn xếp tường minh giúp tránh giới hạn đệ quy khi cây cao với hàng nghìn cấp.

def rangeSumBST(tree, low, high):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

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

Đầu ra mong đợi