AVL树

插入时出现失衡的情况有如下四种（其中X为最小失衡子树的根节点）：

插入点位于X的左子节点的左子树——左左；
插入点位于X的左子节点的右子树——左右；
插入点位于X的右子节点的左子树——右左；
插入点位于X的右子节点的右子树——右右。

情况1和4对称，称为外侧插入，可以采用单旋转操作调整恢复平衡；2和3对称，称为内侧插入，可以采用双旋转操作调整恢复平衡：先经过一次旋转变成左左或右右，然后再经过一次旋转恢复平衡，例如：

3，4类似于1，2。

RB-tree

RB-tree的平衡条件不同于AVL-tree，但同样运用了单旋转和双旋转的恢复平衡的机制，下面我们详细介绍RB-tree的实现。

性质

每个节点不是黑色就是红色；
根节点为黑色；
每个叶子节点（NIL）为黑色；
如果节点为红，其左右子节点必为黑；
对每个节点，从该节点到其子孙中的叶子节点的所有路径上所包含的黑色点数目相同。

这些约束保证了这个树大致上是平衡的，这也决定了红黑树的插入、删除、查询等操作是比较快速的。根据规则5，新增节点必须为红色；根据规则4，新增节点之父节点必须为黑色。当新增节点根据二叉搜索树的规则到达其插入点时，却未能符合上述条件时，就必须调整颜色并旋转树形。下图是一个典型的RB-tree（来自wiki）：

17 11 22

实现

RB-tree的结构定义：主要包含一个标志颜色的bool变量 _M_color，3个节点指针 _M_parent , _M_left , _M_right，2个成员函数 _S_minimum 和 _S_maximum （分别求取最小（最左）、最大（最右）节点）

typedef bool _Rb_tree_Color_type;
const _Rb_tree_Color_type _S_rb_tree_red = false;
const _Rb_tree_Color_type _S_rb_tree_black = true;
//======================================
struct _Rb_tree_node_base { // 节点的定义
  typedef _Rb_tree_Color_type _Color_type;
  typedef _Rb_tree_node_base* _Base_ptr;
  _Color_type _M_color; // 节点颜色，实际为一个bool型变量
  _Base_ptr _M_parent; // 指向父节点，方便遍历
  _Base_ptr _M_left;
  _Base_ptr _M_right;

  static _Base_ptr _S_minimum(_Base_ptr __x) {
    while (__x->_M_left != 0) __x = __x->_M_left;
    return __x;
  }
  static _Base_ptr _S_maximum(_Base_ptr __x) {
    while (__x->_M_right != 0) __x = __x->_M_right;
    return __x;
  }
};
//======================================
template <class _Value> struct _Rb_tree_node : public _Rb_tree_node_base { // 节点的定义
  typedef _Rb_tree_node<_Value>* _Link_type;
  _Value _M_value_field;
};

迭代器：自增自减操作
插入操作
- 基本插入操作
- 调整至平衡
- 破坏RB-tree性质4的可能起因是插入了一个红色节点、将一个黑色节点变为红色或者是旋转，而破坏性质5的可能原因是插入一个黑色的节点、节点颜色的改变（红变黑或黑变红）或者是旋转。
- 新插入的节点的颜色必为红色，因为插入黑点会增加某条路径上黑结点的数目，从而导致整棵树黑高度的不平衡。但如果新结点的父结点为红色时（如下图所示），将会违反红黑树的性质：一条路径上不能出现父子同为红色结点。这时就需要通过一系列操作来使红黑树保持平衡。为了清楚地表示插入操作以下在结点中使用“N”字表示一个新插入的结点，使用“P”字表示新插入点的父结点，使用“U”字表示“P”结点的兄弟结点，使用“G”字表示“P”结点的父结点。插入操作分为以下几种情况：
- - 树为空
  - - 将插入节点改成黑色以满足性质2
  - 黑父（插入时不影响平衡）
  - - 红黑树比AVL树优秀的地方之一在于黑父的情况比较常见，从而使红黑树需要旋转的几率相对AVL树来说会少一些。
  - 红父（复杂）
    
    由于父节点为红，所以祖父节点必为黑色。由于新节点和父节点均为红，所以需要重新着色或进行旋转，此时就需要考虑叔父节点的颜色，进而可能需要考虑祖父、祖先节点的颜色。
    - 叔父为红
    - 叔父为黑
删除操作(复杂)
查询操作（简单O(logN))

参考blog:http://ibillxia.github.io/blog/2014/08/03/insight-into-stl-4-associative-containers-1-red-black-tree/

自平衡二叉搜索树

AVL树

RB-tree

性质

实现

Comments