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?

Question

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). "

Answer 1

• Hãy x là nút khởi động và z là nút kết thúc sau k cuộc gọi liên tiếp để TREE-NGƯỜI KẾ.
• Hãy để p là đường dẫn đơn giản giữa x và z bao gồm.
• Hãy để y là tổ tiên chung của x và z rằng lượt truy cập p.
• Độ 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 đến z.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ó trong p đang truy cập, và bên cạnh các nút x, y và z, nếu một cây con của một nút trong p được truy cập sau đó tất cả các phần tử của nó nằm trong output.
• Vì vậy, thời gian chạy là O(h+k).

Answer 2

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).