Kth Smallest Element in a BST
Bạn nhận được một cây tìm kiếm nhị phân dưới dạng mảng root theo thứ tự heap: nút gốc nằm ở chỉ số 0, các nút con của chỉ số i nằm ở 2*i+1 (bên trái) và 2*i+2 (bên phải), còn -1 đánh dấu một vị trí trống. Mảng có thể kết thúc bằng các phần tử -1 thừa. Ở mỗi nút, cây con bên trái chỉ chứa các giá trị nhỏ hơn, còn cây con bên phải chỉ chứa các giá trị lớn hơn.
Trả về giá trị nhỏ thứ k trong cây, với cách đếm bắt đầu từ 1.
Hàm
- rootinteger-array
- Cây tìm kiếm nhị phân theo thứ tự từng mức, với -1 cho vị trí trống
- kinteger
- vị trí cần tìm theo thứ tự tăng dần, bắt đầu từ 1
- Trả vềinteger
- giá trị nhỏ thứ k trong cây
Ràng buộc
1 ≤ root.length ≤ 32767- Mỗi
root[i]là-1hoặc một giá trị thỏa mãn0 ≤ root[i] ≤ 105. root[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ử
-1bổ sung 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. - Quy tắc sắp xếp đúng tại mọi nút, vì vậy không có giá trị nào xuất hiện hai lần.
1 ≤ k ≤số nút trong cây.
Ví dụ
- Đầu vào
- root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22]k = 4
- Đầu ra
- 29
- Giải thích
- Theo thứ tự tăng dần, các giá trị là
6, 17, 22, 29, 41, 65, 90, và giá trị thứ tư là29. Đây là giá trị lớn nhất trong bốn giá trị ở cây con bên trái của nút gốc.
- Đầu vào
- root = [12, 5, -1, 2, 9, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1]k = 1
- Đầu ra
- 2
- Giải thích
- Giá trị nhỏ nhất kết thúc đường đi liên tục sang trái:
12,5,2.7bên dưới9và phần đệm-1không làm thay đổi điều đó.
Câu hỏi mở rộng
Nếu cây thay đổi thường xuyên và bạn được hỏi nhiều lần về giá trị nhỏ thứ k, mỗi nút có thể lưu trữ gì để mỗi truy vấn mất O(h)?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Cách duyệt cây tìm kiếm nhị phân nào liệt kê các giá trị theo thứ tự từ nhỏ nhất đến lớn nhất?
Đi qua cây con bên trái, sau đó đến nút, rồi đến cây con bên phải sẽ cho ta thứ tự đã sắp xếp. Giá trị thứ
kmà quá trình duyệt tạo ra chính là đáp án, nên bạn có thể dừng tại đó.Dùng ngăn xếp. Từ nút hiện tại, đẩy các nút vào ngăn xếp khi di chuyển đến nút con bên trái. Lấy phần tử trên cùng ra và đếm; dừng ở lần lấy ra thứ
k. Nếu chưa đến, chuyển đến nút con bên phải của nút vừa lấy ra tại2*i+2rồi lặp lại.
Lời giải
Duyệt theo thứ tự giữa (cây con trái, nút, cây con phải) đọc các giá trị của cây tìm kiếm nhị phân theo thứ tự tăng dần, nên giá trị thứ k mà bạn gặp là đáp án. Duyệt bằng ngăn xếp tự tạo và dừng tại đó; không cần sắp xếp.
Thu thập mọi giá trị và sắp xếp
Ý tưởng
Bỏ qua hình dạng: giữ lại mọi phần tử khác -1, sắp xếp rồi trả về phần tử ở vị trí k-1. Trong ví dụ đầu tiên, danh sách đã sắp xếp là 6, 17, 22, 29, 41, 65, 90, và vị trí 3 có giá trị 29.
Cách này đúng với mọi cây, dù có thứ tự hay không. Đó cũng là cái giá phải trả: cách này bỏ qua thứ tự vốn có của cây, tốn O(n log n) để sắp xếp và dùng O(n) bộ nhớ để sao chép.
Thuật toán
- Thu thập mọi phần tử của
rootkhông phải là-1. - Sắp xếp các giá trị đã thu thập theo thứ tự tăng dần.
- Trả về giá trị ở vị trí
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]Duyệt theo thứ tự vào một danh sách
Ý tưởng
Bên dưới mỗi nút, cây con bên trái chỉ chứa các giá trị nhỏ hơn, còn cây con bên phải chỉ chứa các giá trị lớn hơn. Duyệt cây con bên trái, rồi đến nút, sau đó đến cây con bên phải, và làm tương tự trong từng cây con: mỗi nút nằm sau tất cả các giá trị nhỏ hơn và trước tất cả các giá trị lớn hơn, nên kết quả được sắp xếp. Trong ví dụ đầu tiên, quá trình duyệt cho kết quả 6, 17, 22, 29, 41, 65, 90.
Chỉ cần một lượt duyệt thay cho việc sắp xếp: thời gian O(n) và không gian O(n) cho danh sách. Cách này vẫn duyệt toàn bộ cây, ngay cả khi k = 1, trong trường hợp đáp án nằm ở cuối đường đi ngoài cùng bên trái.
Thuật toán
- Viết
inorder(i): trả về khi gặp vị trí trống (vượt quá cuối hoặc-1). - Nếu không, gọi
inorder(2*i+1), thêmroot[i]vào danh sách, rồi gọiinorder(2*i+2). - Gọi
inorder(0). - Trả về phần tử trong danh sách ở vị trí
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 sortedDuyệt trung thứ tự lặp lại và dừng tại k
Ý tưởng
Một ngăn xếp tường minh cho phép bạn dừng quá trình duyệt giữa chừng. Đi sang trái xa nhất có thể, đồng thời đẩy từng nút vào ngăn xếp. Nút trên cùng là giá trị nhỏ nhất chưa được tính, vì mọi giá trị nhỏ hơn đều nằm trong cây con bên trái của nó, vốn rỗng hoặc đã được tính. Lấy nút ra khỏi ngăn xếp và tính nó; cây con bên phải của nút đó là phần tiếp theo theo thứ tự tăng dần.
Với k = 4 trong ví dụ đầu tiên: đẩy 41, 17, 6 vào ngăn xếp. Lấy 6 ra, rồi đến 17, sau đó chuyển sang nút con bên phải của nó: đẩy 29 và 22 vào ngăn xếp. Lấy 22 ra, rồi đến 29, giá trị thứ tư. Quá trình duyệt không chạm đến 65 hay 90.
Ngăn xếp chứa tối đa một nút ở mỗi mức, vì vậy độ phức tạp không gian là O(h). Quá trình duyệt đi xuống một lần rồi lấy ra k nút: độ phức tạp thời gian là O(h + k).
Thuật toán
- Bắt đầu với một ngăn xếp rỗng và
i = 0. - Khi
ilà một nút thực, đẩy nó vào ngăn xếp rồi chuyển đến2*i+1. - Lấy phần tử trên cùng ra, gán cho
irồi trừ1khỏik. - Nếu lúc này
kbằng0, trả vềroot[i]. - Nếu không, chuyển đến
2*i+2rồi quay lại bước 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
Lỗi thường gặp và trường hợp biên
- Đọc mảng theo thứ tự chỉ số. Thứ tự theo tầng không được sắp xếp: ví dụ đầu tiên bắt đầu bằng
41, 17, 65. - Lệch một vị trí ở
k. Cách đếm bắt đầu từ1: trả về vị trík-1trong danh sách và dừng lượt duyệt khi số đếm đạtk. - Bỏ qua cây con bên phải sau khi lấy một phần tử ra. Trong ví dụ thứ hai,
9và7nằm trong cây con bên phải của5, nên lượt duyệt sẽ không bao giờ đếm đến chúng. - Coi nút con không tồn tại là nút có thật. Nút con trống khi chỉ số của nó vượt quá độ dài mảng hoặc có giá trị
-1:22nằm ở chỉ số9, nên các nút con19và20nằm ngoài phạm vi mảng. - Mảng trong Lua và R bắt đầu từ 1. Giữ chỉ số nút bắt đầu từ 0 để dùng
2*i+1và đọcroot[i + 1].
Câu hỏi thường gặp3
Độ phức tạp thời gian để tìm phần tử nhỏ thứ k trong BST là bao nhiêu?
Phép duyệt cây theo thứ tự giữa có tính lặp mất O(h + k) thời gian và O(h) không gian bổ sung với cây có độ sâu h. Trong trường hợp xấu nhất, khi k = n hoặc cây có dạng đường đi, độ phức tạp là O(n).
Làm thế nào để tìm phần tử lớn thứ k trong BST?
Mô phỏng đường đi: cây con bên phải, rồi đến nút, sau đó là cây con bên trái. Cách này liệt kê các giá trị theo thứ tự giảm dần. Đi sang phải xa nhất có thể trong khi đẩy nút vào ngăn xếp, lấy nút ra và đếm, rồi chuyển sang nút con bên trái sau mỗi lần lấy ra. Lần lấy ra thứ k là giá trị lớn thứ k.
Làm thế nào để dừng phép duyệt trung thứ tự đệ quy (in-order traversal) tại giá trị thứ k?
Giữ một bộ đếm bên ngoài đệ quy, bắt đầu từ k. Trừ đi 1 sau khi cây con bên trái của một nút trả về, rồi ghi lại giá trị của nút khi bộ đếm đạt 0. Sau mỗi lần gọi, trả về ngay nếu đã ghi lại đáp án. Khi đó, cách đệ quy khớp với phiên bản dùng ngăn xếp: thời gian O(h + k), bộ nhớ O(h).
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def kthSmallest(root, k):
# Viết code tại đâyKiểm thử #1
Kiểm thử #2
Đối số
root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22] k = 4
Đầu ra mong đợi
29