爲什麼每個二叉搜索樹的高度不是O（log n）

研究算法考試，我讀了每個BST的高度不是O（log n）。這個事實與樹是否平衡有關係嗎？是每個平衡BST O（log n）的高度，還是其他不平衡樹（如果是的話）？爲什麼每個二叉搜索樹的高度不是O（log n）

2015-06-05 vsingal5

是的，它與平衡/不平衡有關。設想一棵樹，其中根是最小項，並且沒有節點已經離開小孩。它的高度將是N（項目的數量）。 – ahruss

你可以說'h =Ω（log n）'，我想。 – Amadan

每個不平衡的高度 BST不是O(lg n)因爲想象樹中鍵的增加/減少順序，樹變成傾斜到一邊。這恰好是O(n)對於高度等於n的不平衡BST的最壞情況。另一方面，對於諸如AVL樹的平衡樹，插入/刪除期間的旋轉允許這些樹保持近似（不完美）的高度。

2015-06-05 02:09:42

是的，這是因爲樹不平衡。考慮當你將一個排序的數字序列插入到樹中時會發生什麼。每個人都是您插入的前一個號碼的子女。樹的高度是O（n）。

2015-06-05 02:12:29

回答