Cho một giới hạn trên tiệm cận trên chiều cao của cây tìm kiếm nhị phân n-nút trong đó độ sâu trung bình của một nút là Θ (lg n)

Question

Gần đây, tôi đang cố gắng giải quyết tất cả các bài tập trong CLRS. nhưng có một số người trong số họ tôi không thể tìm ra. Đây là một trong số đó, từ bài tập CLRS 12.4-2:

Mô tả cây tìm kiếm nhị phân trên nút n sao cho độ sâu trung bình của một nút trong cây là Θ (lg n) nhưng chiều cao của cây là ω (lg n). Đặt một giới hạn trên tiệm cận trên chiều cao của cây tìm kiếm nhị phân n-nút, trong đó độ sâu trung bình của một nút là Θ (lg n).

Mọi người có thể chia sẻ một số ý tưởng hoặc tham chiếu để giải quyết vấn đề này không? Cảm ơn.

Answer 1

Vì vậy, giả sử chúng ta xây dựng cây theo cách này: cho n nút, lấy f (n) nút và đặt chúng sang một bên. Sau đó xây dựng một cây bằng cách xây dựng một cây nhị phân hoàn hảo, nơi gốc có một cây con trái là một cây nhị phân hoàn hảo của các nút n - f (n) - 1 và một cây con phải là một chuỗi có chiều dài f (n). Chúng tôi sẽ chọn f (n) sau.

Vậy độ sâu trung bình của cây là bao nhiêu? Vì chúng ta chỉ muốn một ràng buộc tiệm cận, hãy chọn n sao cho n - f (n) - 1 là một ít hơn một sức mạnh hoàn hảo của hai, nói, 2^k - 1. Trong trường hợp đó, tổng các chiều cao trong một phần của cây là 1 * 2 + 2 * 3 + 4 * 4 + 8 * 5 + ... + 2^(k-1) * k, là (IIRC) về k2^k, mà chỉ là về (n - f (n)) log (n - f (n)) bằng cách chọn k. Ở phần còn lại của cây, tổng chiều sâu là khoảng f (n)^2. Điều này có nghĩa là chiều dài đường dẫn trung bình là khoảng ((n - f (n)) log (n - f (n)) + f (n)^2)/n. Ngoài ra, chiều cao của cây là f (n). Vì vậy, chúng tôi muốn tối đa hóa f (n) trong khi vẫn giữ độ sâu trung bình O (log n).

Để làm điều này, chúng ta cần tìm f (n) sao cho

1. n - f (n) = Θ (n), hoặc hạn ghi trong tử số biến mất và chiều cao không phải là logarit,
2. f (n)^2/n = O (log n) hoặc thuật ngữ thứ hai trong tử số quá lớn.

Nếu bạn chọn f (n) = Θ (sqrt (n log n)), tôi nghĩ rằng 1 và 2 được thỏa mãn tối đa. Vì vậy, tôi cược (mặc dù tôi có thể hoàn toàn sai về điều này) rằng điều này là tốt như bạn có thể nhận được. Bạn nhận được một cây có chiều cao Θ (sqrt (n log n)) có chiều sâu trung bình Θ (Nhật ký n).

Hy vọng điều này sẽ hữu ích! Nếu toán học của tôi là cách tắt, xin vui lòng cho tôi biết. Đã muộn rồi và tôi đã không thực hiện kiểm tra kép thông thường. :-)

Answer 2

trước tiên hãy phóng to chiều cao của cây. (có một cây nơi mỗi nút chỉ có một nút con, vì vậy bạn có một chuỗi dài đi xuống).

Kiểm tra độ sâu trung bình. (rõ ràng độ sâu trung bình sẽ quá cao).

trong khi độ sâu trung bình quá cao, bạn phải giảm chiều cao của cây xuống một. Có nhiều cách để giảm chiều cao của cây một. Chọn cách giảm thiểu chiều cao trung bình. (chứng minh bằng cảm ứng rằng mỗi khi bạn nên chọn một trong đó giảm thiểu chiều cao trung bình). Tiếp tục cho đến khi bạn rơi dưới yêu cầu chiều cao trung bình. (ví dụ: tính toán bằng cách sử dụng công thức cảm ứng cho chiều cao và độ sâu trung bình).

Answer 3

Nếu bạn đang cố gắng tối đa hóa chiều cao của cây trong khi giảm thiểu độ sâu trung bình của tất cả các nút của cây, hình dạng tốt nhất rõ ràng sẽ là hình dạng "ô", ví dụ: một cây nhị phân đầy đủ với k nút và chiều cao = lg k, trong đó 0 < k < n, cùng với một đường đơn, hoặc "đuôi", của các nút n-k xuất phát từ một trong những lá của toàn bộ phần. Chiều cao của cây này là khoảng lg k + n - k.

Bây giờ, hãy tính tổng chiều sâu của tất cả các nút. Tổng chiều sâu của các nút của toàn bộ phần là tổng [j * 2^j], trong đó tổng được lấy từ j = 0 đến j = lg k. Theo một số đại số, thuật ngữ chi phối của kết quả là 2k lg k.

Tiếp theo, tổng độ sâu của phần đuôi được cho bởi tổng [i + lg k], trong đó tổng được lấy từ i = 0 đến i = n-k. Bởi một số đại số, kết quả là khoảng (n-k) lg k + (1/2) (n-k)^2.

Do đó, tổng hợp hai phần trên với nhau và chia cho n, độ sâu trung bình của tất cả các nút là (1 + k/n) lg k + (n-k)^2/(2n). Lưu ý rằng vì 0 < k < n, thuật ngữ đầu tiên ở đây là O (lg n) bất kể chúng ta chọn gì k. Do đó, chúng ta chỉ cần chắc chắn rằng thuật ngữ thứ hai là O (lg n). Để làm như vậy, chúng ta yêu cầu (n-k)^2 = O (n lg n), hoặc k = n - O (sqrt (n lg n)). Với lựa chọn này, chiều cao của cây là

lg k + n - k = O (sqrt (n lg n))

này là tiệm lớn hơn so với O bình thường (lg n), và là tiệm cao nhất bạn có thể làm cho cây trong khi giữ độ sâu trung bình là O (lg n)