Tôi muốn bạn cho tôi một gợi ý để chứng minh bài tập này từ sách Cormen: "Chứng minh rằng bất kể nút nào chúng ta bắt đầu ở cây tìm kiếm nhị phân chiều cao h, k gọi liên tiếp đến TREE-SUCCESSOR mất thời gian O (k + h). "Làm cách nào để chứng minh hoạt động này trên cây tìm kiếm nhị phân?
5
A
Trả lời
6
- Hãy
x
là nút khởi động vàz
là nút kết thúc sauk
cuộc gọi liên tiếp để TREE-NGƯỜI KẾ. - Hãy để
p
là đường dẫn đơn giản giữax
vàz
bao gồm. - Hãy để
y
là tổ tiên chung củax
vàz
rằng lượt truy cậpp
. - Độ dài
p
tối đa là2h
, làO(h)
. - Cho phép
output
là các phần tử mà giá trị của chúng nằm trong khoảng từx.key
đếnz.key
. - Kích thước của
output
làO(k)
. - Trong việc thực hiện các
k
cuộc gọi liên tiếp để TREE-NGƯỜI KẾ, các nút có trongp
đang truy cập, và bên cạnh các nútx
,y
vàz
, nếu một cây con của một nút trongp
được truy cập sau đó tất cả các phần tử của nó nằm trongoutput
. - Vì vậy, thời gian chạy là
O(h+k)
.
3
Gợi ý: làm việc ra một ví dụ nhỏ, quan sát kết quả, cố gắng ngoại suy lý do.
Để bắt đầu, dưới đây là một số điều cần xem xét.
Bắt đầu tại một nút nhất định, k cuộc gọi thành công đến Tree-Succcesor consititutes đi bộ một phần cây. Có bao nhiêu nút (ít nhất và nhiều nhất) các lượt truy cập đi bộ này? (Gợi ý: Hãy suy nghĩ về khóa (x)). Hãy nhớ rằng một cạnh được truy cập nhiều nhất hai lần (tại sao?).
Gợi ý cuối cùng: Kết quả là O(2h+k)
.
+1
Nút được truy cập nhiều nhất ba lần. –
Các vấn đề liên quan
- 1. Cây tìm kiếm nhị phân trên cây AVL
- 2. Cây tìm kiếm nhị phân đệ quy
- 3. Tìm hiểu về cấu trúc cây tìm kiếm nhị phân
- 4. Số cây tìm kiếm nhị phân trên n thành phần riêng biệt
- 5. đại diện cho cây tìm kiếm nhị phân trong python
- 6. Xây dựng cây tìm kiếm nhị phân cân bằng
- 7. Cây tìm kiếm nhị phân cân bằng hoàn hảo
- 8. Tìm kiếm nhị phân Cây C thực hiện
- 9. Cây tìm kiếm nhị phân tích hợp trong Python?
- 10. Làm thế nào chúng ta có thể chứng minh bằng cảm ứng rằng tìm kiếm nhị phân là chính xác?
- 11. Java: Làm thế nào để thực hiện một cây tìm kiếm nhị phân chung?
- 12. Cách tạo cây nhị phân
- 13. Sự khác nhau giữa cây tìm kiếm và cây nhị phân hiệu quả là gì?
- 14. Hoạt động nhị phân trên tệp nhị phân Erlang?
- 15. kiểm tra xem cây có phải là cây tìm kiếm nhị phân không
- 16. Tìm kiếm nhị phân không phân nhánh
- 17. javascript triển khai thực hiện tìm kiếm nhị phân javascript
- 18. Làm thế nào để thực hiện tìm kiếm nhị phân trên NSArray?
- 19. Chuyển cây nhị phân
- 20. Cây nhị phân từ cây chung
- 21. Tìm kiếm nhị phân chung trong C#
- 22. Tìm đường dẫn trong cây tìm kiếm nhị phân tổng hợp thành giá trị đích
- 23. Lập trình động: Tại sao cải tiến của Knuth thành Cây tìm kiếm nhị phân tối ưu O (n^2)?
- 24. Có tên nào cho loại tìm kiếm nhị phân này không?
- 25. Tính trung trong tìm kiếm nhị phân
- 26. OCaml: vẽ cây nhị phân
- 27. Tìm kiếm nhị phân đệ quy Cây x = thay đổi (x)
- 28. JAVA: cây nhị phân
- 29. Tìm thuật toán nhanh để tìm khoảng cách giữa hai nút trong cây nhị phân
- 30. Cách triển khai cây không nhị phân
'Trong việc thực hiện các cuộc gọi liên tiếp tới TREE-SUCCESSOR, các nút trong p được truy cập, và bên cạnh các nút x, y và z' Bạn có thể giải thích' y' ở đây là gì không? –
Tôi đã thêm 'y' vào câu trả lời. –