二進制搜索樹密度？

Question

我正在處理二進制搜索樹的家庭作業任務，我遇到了一個我不太明白的問題。這個問題詢問密度如何影響搜索二叉樹所花費的時間。我瞭解二分搜索樹和大O符號，但我們以前從未處理過密度。

Answer 1

二叉搜索樹的密度可以定義爲一個級別累計的節點數量。一棵完美的二叉樹將具有最高的密度。所以這個問題基本上會問你如何在每個級別的節點數量影響樹中的搜索時間。如果不清楚，請告訴我。