Độ phức tạp truyền tải trong đơn hàng trong cây tìm kiếm nhị phân (sử dụng trình vòng lặp)?

Question

Câu hỏi liên quan: Time Complexity of InOrder Tree Traversal of Binary Tree O(N)?, tuy nhiên nó dựa trên một traversal qua đệ quy (do đó trong không gian O (log N)) trong khi vòng lặp cho phép tiêu thụ chỉ O (1) không gian.

Trong C++, thường có yêu cầu gia tăng trình lặp của vùng chứa tiêu chuẩn là hoạt động O (1). Với hầu hết các thùng chứa nó được chứng minh một cách trivially, tuy nhiên với map và như vậy, nó có vẻ khó khăn hơn một chút.

• Nếu một map được thực hiện như một bỏ qua danh sách, sau đó kết quả sẽ rõ ràng
• Tuy nhiên chúng thường được thực hiện như cây đỏ-đen (hoặc ít nhất là cây tìm kiếm nhị phân)

Vì vậy, trong quá trình truyền tải theo thứ tự có những khoảnh khắc mà giá trị "tiếp theo" không dễ dàng đạt được. Ví dụ bạn nên chỉ vào lá dưới cùng bên phải của cây con trái, sau đó nút tiếp theo để đi ngang là gốc, cách đó depth bước.

Tôi đã thử "chứng minh" rằng độ phức tạp về thuật toán (về "bước") là được phân bổ O (1), có vẻ như không sao. Tuy nhiên tôi chưa có trình diễn. Đây là một sơ đồ nhỏ tôi truy tìm cho một cây với độ sâu 4, các con số (ở vị trí của các nút) đại diện cho số bước đi từ nút đó đến nút tiếp theo trong quá trình truyền tải trong đơn hàng. :

 3 
    2  2 
1 1 1 1 
1 2 1 3 1 2 1 4 

Lưu ý: lá bên phải có chi phí 4 trong trường hợp đây là cây con của cây lớn hơn.

Tổng là 28, cho tổng số nút là 15: vì vậy chi phí thấp hơn 2 cho mỗi nút, trung bình (nếu nó nắm giữ) sẽ là chi phí phân bổ hợp lý. Vì vậy:

• Trong quá trình truyền tải theo thứ tự, gia tăng vòng lặp thực sự O (1) cho cây tìm kiếm nhị phân cân bằng (và đầy đủ)?
• Có thể mở rộng kết quả để che các cây tìm kiếm nhị phân không đầy đủ không?

Answer 1

Có, chi phí phân bổ thực sự là O(1) cho mỗi lần lặp lại, cho bất kỳ cây nào.

Bằng chứng dựa trên số lần bạn "ghé thăm" từng nút.
Lá chỉ được truy cập một lần. Không có lá nào được truy cập nhiều nhất 3 lần:

1. khi chuyển từ gốc sang nút.
2. khi trở về từ các cây con trái
3. khi trở về từ các cây con đúng

Không có nhiều lần cho bất kỳ nút, do đó nếu chúng ta tính tổng số lần truy cập của mỗi nút, chúng tôi có được một số đó nhỏ hơn 3n, vì vậy tổng số lượt truy cập của tất cả các nút được kết hợp là O(n), cho chúng tôi O(1) mỗi bước được phân bổ.

(Lưu ý vì trong một cây đầy đủ có n/2 lá, chúng tôi đang nhận được 2n bạn gặp phải, tôi tin rằng có thể cho thấy tổng số lượt truy cập sẽ nhỏ hơn 2n cho bất kỳ cây nào, nhưng "tối ưu hóa này "nằm ngoài phạm vi IMO ở đây).

---

Trường hợp xấu nhất cho mỗi bước là O(h), đó là O(logn) trong một cây cân bằng, nhưng có thể O(n) trong một số trường hợp.

---

P.S. Tôi không biết cây Red-Black được triển khai bằng C++ như thế nào, nhưng nếu cấu trúc dữ liệu cây của bạn chứa trường parent từ mỗi nút, nó có thể thay thế ngăn xếp đệ quy và cho phép tiêu thụ không gian O(1). (Điều này tất nhiên là "gian lận" vì lưu trữ n các trường như vậy là chính mình là O(n)).