• AVL树的概念
  • 二叉搜索树虽可以缩短查找的效率，但 如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当 于在顺序表中搜索元素，效率低下 。因此，两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之 差的绝对值不超过 1( 需要对树中的结点进行调整 ) ，即可降低树的高度，从而减少平均搜索长度。
  • 一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
    • 它的左右子树都是AVL树
    • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在

，搜索时间复杂度

?红黑树

• 红黑树的概念
  • 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
• 红黑树的性质
  • 每个结点不是红色就是黑色
  • 根节点是黑色的?
  • 如果一个节点是红色的，则它的两个孩子结点是黑色的?
  • 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点?
  • 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
• 红黑树结构
  • 为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点， pLeft 域指向红黑树中最小的节点，pRight 域指向红黑树中最大的节点

• 红黑树的插入操作
  • 红黑树是二叉搜索树: 按照二叉搜索树的性质插入新节点
    • 找新节点在树中的插入位置并保存其双亲
    • 插入新节点
  • 检测新节点插入后是否违反性质三︰是否存在连在一起的红色节点
    • 因为: 新节点的默认颜色是红色
  • 情况一: 叔叔节点存在 & 红色
  • 前提: 叔叔不存在 || 叔叔节点存在但是颜色是黑色的
    • 情况二:?cur在双亲的左侧
    • 情况三: cur在双亲的右侧
• 红黑树的验证
  • 检测其是否满足二叉搜索树 ( 中序遍历是否为有序序列 )
  • 检测其是否满足红黑树的性质