平衡二元搜尋樹

Template:NoteTA 平衡二叉搜索树（Template:Lang-en）是一种結構平衡的二叉搜索树，它是一種每個節點的左右兩子樹高度差都不超過1的二元樹。它能在O($\log n$)内完成插入、查找和删除操作，最早被發明的平衡二叉搜索树爲AVL树。

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

• AVL树
• 紅黑樹
• Treap
• 节点大小平衡树