高级树、AVL 树和红黑树

平衡树

平衡树是计算机科学中的一类数据结构，为改进的二叉查找树。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡树。

在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。

基本操作

• 旋转（Rotate）：通过旋转操作可以使得树趋于平衡。如果可以让树维持平衡，也就是让 h 维持在 O(logN) 的左右，就可以在 O(logN) 的复杂度内完成各种基本操作。
• 插入（insert）：在树中插入一个新值。
• 删除（delete）：在树中删除一个值。
• 查询前驱（predecessor）：前驱定义为小于x，且最大的数。
• 查询后继（successor）：后继定义为大于x，且最小的数。
• 查询排名（rank）：排名定义为比x小的数的个数加一。
• 查询第k大：即排名为k的数。

各种平衡树

• AVL 树：是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logN)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。带有平衡因子1、0或 -1的节点被认为是平衡的。
• 红黑树：在 O(logN) 时间内完成查找，插入和删除，这里的n是树中元素的数目。