教甄◆資訊科技概論專業(電腦科)題庫下載題庫

一般的二元搜尋樹的查詢複雜度是跟目標結點到樹根的距離（即深度）有關，因此當結點的深度普遍較大時，查詢的均攤複雜度會上升，為了更高效的查詢，平衡樹應運而生了。

常見平衡樹：

AVL樹，經典平衡樹, 所有操作的最壞複雜度都是{displaystyle O(log {n})}的。Treap，利用隨機堆的期望深度來優化樹的深度，達到較優的期望複雜度。伸展樹，使得經常查找的結點深度較小，從而降低均攤複雜度。紅黑樹。加權平衡樹。2-3樹AA樹替罪羊樹節點大小平衡樹

參考資料：https://zh.wikipedia.org/wiki/%E5%B9%B3%E8%A1%A1%E6%A0%9...

查看完整內容

一般的二元搜尋樹的查詢複雜度是跟目標結點到樹根的距離（即深度）有關，因此當結點的深度普遍較大時，查詢的均攤複雜度會上升，為了更高效的查詢，平衡樹應運而生了。

常見平衡樹：

• AVL樹，經典平衡樹, 所有操作的最壞複雜度都是{displaystyle O(log {n})}的。

• Treap，利用隨機堆的期望深度來優化樹的深度，達到較優的期望複雜度。
• 伸展樹，使得經常查找的結點深度較小，從而降低均攤複雜度。
• 紅黑樹。
• 加權平衡樹。
• 2-3樹
• AA樹
• 替罪羊樹
• 節點大小平衡樹

參考資料：https://zh.wikipedia.org/wiki/%E5%B9%B3%E8%A1%A1%E6%A0%91