平衡二元搜尋樹

平衡二叉搜索樹（英語：Balanced Binary Search Tree）是一種結構平衡的二叉搜索樹，它是一種每個節點的左右兩子樹高度差都不超過1的二元樹。它能在O(${\displaystyle \log n}$)內完成插入、查找和刪除操作，最早被發明的平衡二叉搜索樹爲AVL樹。

常見的平衡二叉搜索樹有：

• AVL樹
• 紅黑樹
• Treap
• 節點大小平衡樹