常见的平衡二叉树

1. AVL树（Adelson-Velsky和Landis树）

    定义：AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任何节点的两个子树的高度最大差别为1。

    平衡因子：每个节点都有一个平衡因子，定义为左子树高度减去右子树高度，平衡因子的值只能是-1、0或1。

    旋转操作：AVL树通过四种旋转操作（单旋转和双旋转）来维护平衡：左旋、右旋、左-右双旋、右-左双旋。

2. 红黑树

    定义：红黑树是另一种自平衡二叉查找树，它通过确保树满足一系列的红黑性质来保持大致平衡。

    性质：每个节点要么是红色，要么是黑色。根节点是黑色。每个叶子节点（NIL节点，空节点）是黑色。如果一个节点是红色的，则它的两个子节点都是黑色的。从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

    旋转和重新着色：红黑树通过旋转和重新着色来维持平衡。

3. Treap（树堆）

    定义：Treap结合了二叉查找树和堆的性质。每个节点有一个优先级，树满足二叉查找树的性质，并且每个节点的优先级大于其子节点的优先级。

    平衡：Treap通过随机分配优先级和旋转操作来保持平衡。

4. Splay树

    定义：Splay树是一种自调整二叉查找树，它通过一种名为"splay"的操作将最近访问过的节点移到树的根部。

    平衡：Splay树不保证严格的平衡，但它能保证最坏情况下的操作时间复杂度是对数级的。