平衡二元搜寻树

平衡二叉搜索树（英语：Balanced Binary Search Tree）是一种结构平衡的二叉搜索树，它是一种每个节点的左右两子树高度差都不超过1的二元树。它能在O(${\displaystyle \log n}$)内完成插入、查找和删除操作，最早被发明的平衡二叉搜索树为AVL树。

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

• AVL树
• 红黑树
• Treap
• 节点大小平衡树