一、概念

红黑树，是一种二叉搜索树。但在每个结点上增加一个存储位表示结点的颜色，可以是Red或

Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路

径会比其他路径长出两倍，因而是接近平衡的。

性质:

1. 每个结点不是红色就是黑色

2. 根节点是黑色的

3. 若一个节点是红色的，则它的两个孩子结点是黑色的(即树中没有连续的红色结点)

4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点(即每条路径上黑色结点数量相等)

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点NIF)

二、红黑树的插入操作

红黑树的插入操作大致可以分成两步:

第一步: 按照二叉搜索树的规则插入新节点

bool insert(const pair<K, V>& kv) {
    if (_root == nullptr) {
      _root = new TreeNode(kv);
      _root->_color = BLACK;
      return true;
    }
    TreeNode* parent = nullptr;
    TreeNode* cur = _root;
    while (cur != nullptr) {
      if (kv.first > cur->_data.first) {
        parent = cur;
        cur = cur->_right;
      }
      else if (kv.first < cur->_data.first) {
        parent = cur;
        cur = cur->_left;
      }
      else return false;
    }
    cur = new TreeNode(kv);
    cur->_color = RED;
    if (kv.first > parent->_data.first) {
      parent->_right = cur;
    }
    else { //kv.first < parent->_data.first)
      parent->_left = cur;
    }
    cur->_parent = parent;
    //………………
  }

第二步: 插入后检测性质是否造到破坏，若遭到破坏则进行调整

新节点的默认颜色是红色，若其双亲结点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入结点的双亲结点颜色为红色时，就出现了连续的红色结点，此时需要对红黑树分情况来讨论：

情况一: cur为红，parent为红，grandfather为黑，uncle存在且为红

if (uncle != nullptr && uncle->_color == RED) {
    parent->_color = uncle->_color = BLACK;
  grandfather->_color = RED;
  cur = grandfather;
  parent = cur->_parent;
}

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑(单旋+变色)

uncle的情况有两种:

1.若uncle结点不存在时，cur结点一定是新增结点。若cur不是新增结点，则cur和parent之间一定有一个黑色结点。这不满足性质4:每条路径上黑色结点的个数相同。

2.若uncle存在且为黑色，那么cur原来的颜色一定为黑色。看到cur结点是红色，是因为cur的子树在调整的过程中将cur的颜色从黑色改变为红色。

//右单旋 + 变色
if (cur == parent->_left) {
  rotate_right(grandfather);
  grandfather->_color = RED;
  parent->_color = BLACK;
}
//左单旋 + 变色
if (cur == parent->_right) {
  rotate_left(grandfather);
  grandfather->_color = RED;
  parent->_color = BLACK;
}

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑(双旋+变色)

//左右双旋 + 变色
else {//cur == parent->_right
  rotate_left(parent);
    rotate_right(grandfather);
  cur->_color = BLACK;
  grandfather->_color = RED;
}
//右左双旋 + 变色
else {//cur == parent->_left
  rotate_right(parent);
  rotate_left(grandfather);
  cur->_color = BLACK;
  grandfather->_color = RED;
}

三、红黑树的验证

红黑树的检测分为两步：

检测其是否满足二叉搜索树

使用中序遍历判断其是否有序即可，这里不做过多解释

检测其是否满足红黑树的性质

bool IsBalance() {
  //空树也是红黑树
  if (_root == nullptr) return true;
  //根结点是黑色的
  if (_root->_color != BLACK) return false;
  int benchmark = 0;//基准值
  return _IsBalance(_root, 0, benchmark);
}
bool _IsBalance(TreeNode* root, int blackNum, int& benchmark) {
  if (root == nullptr) {
    if (benchmark == 0) {
      benchmark = blackNum;//将第一条路径的blackNum设为基准值
        return true;
    }
    else {
      return blackNum == benchmark;
    }
  }
  if (root->_color == BLACK) ++blackNum;
  if (root->_color == RED && root->_parent->_color == RED) return false;
    //逻辑短路，若root结点为红色，其就不可能为根结点，一定有parent结点
  return _IsBalance(root->_left, blackNum, benchmark) && 
            _IsBalance(root->_right, blackNum, benchmark);
}

四、完整代码

#include<iostream>
#include<cassert>
using std::pair;
using std::make_pair;
using std::cout;
using std::cout;
using std::endl;
enum Color { RED,BLACK };
template<class K,class V>
struct RedBlackTreeNode {
  RedBlackTreeNode(const pair<K, V>& kv) :
        _parent(nullptr), 
        _left(nullptr), 
        _right(nullptr), 
        _data(kv),
        _color(RED){}
  RedBlackTreeNode<K, V>* _parent;
  RedBlackTreeNode<K, V>* _left;
  RedBlackTreeNode<K, V>* _right;
  pair<K, V> _data;
  Color _color;
};
template<class K,class V>
class RedBlackTree 
{
  typedef RedBlackTreeNode<K, V> TreeNode;
public:
  bool insert(const pair<K, V>& kv) {
    if (_root == nullptr) {
      _root = new TreeNode(kv);
      _root->_color = BLACK;
      return true;
    }
    TreeNode* parent = nullptr;
    TreeNode* cur = _root;
    while (cur != nullptr) {
      if (kv.first > cur->_data.first) {
        parent = cur;
        cur = cur->_right;
      }
      else if (kv.first < cur->_data.first) {
        parent = cur;
        cur = cur->_left;
      }
      else return false;
    }
    cur = new TreeNode(kv);
    cur->_color = RED;
    if (kv.first > parent->_data.first) {
      parent->_right = cur;
    }
    else { //kv.first < parent->_data.first)
      parent->_left = cur;
    }
    cur->_parent = parent;
    while (parent && parent->_color == RED)
    {
      TreeNode* grandfather = parent->_parent;
      assert(grandfather != nullptr);
            //当parent结点为红时，grandfather结点必不为空(根结点为黑)
      assert(grandfather->_color == BLACK);
            //当parent结点为红时，grandfather结点必为黑色(否则违反性质，出现连续的红色结点)
      if (parent == grandfather->_left) {
        TreeNode* uncle = grandfather->_right;
        if (uncle != nullptr && uncle->_color == RED) {
          parent->_color = uncle->_color = BLACK;
          grandfather->_color = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else {//uncle不存在或者为黑
          //右单旋 + 变色
          if (cur == parent->_left) {
            rotate_right(grandfather);
            grandfather->_color = RED;
            parent->_color = BLACK;
          }
          //左右双旋 + 变色
          else {//cur == parent->_right
            rotate_left(parent);
            rotate_right(grandfather);
            cur->_color = BLACK;
            grandfather->_color = RED;
          }
          break;
        }
      }
      else {//parent == grandfather->_right
        TreeNode* uncle = grandfather->_left;
        if (uncle != nullptr && uncle->_color == RED) {
          parent->_color = uncle->_color = BLACK;
          grandfather->_color = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else {//uncle不存在或者为黑
          //左单旋 + 变色
          if (cur == parent->_right) {
            rotate_left(grandfather);
            grandfather->_color = RED;
            parent->_color = BLACK;
          }
          //右左双旋 + 变色
          else {//cur == parent->_left
            rotate_right(parent);
            rotate_left(grandfather);
            cur->_color = BLACK;
            grandfather->_color = RED;
          }
          break;
        }
      }
    }
    _root->_color = BLACK;
    return true;
  }
  void inorder() {
    _inorder(_root);
  }
  bool IsBalance() {
    //空树也是红黑树
    if (_root == nullptr) return true;
    //根结点是黑色的
    if (_root->_color != BLACK) return false;
    int benchmark = 0;//基准值
    return _IsBalance(_root, 0, benchmark);
  }
private:
  void _inorder(TreeNode* root) {
    if (root == nullptr) {
      return;
    }
    _inorder(root->_left);
    cout << root->_data.first << ":" << root->_data.second << " ";
    _inorder(root->_right);
  }
  bool _IsBalance(TreeNode* root, int blackNum, int& benchmark) {
    if (root == nullptr) {
      if (benchmark == 0) {
        benchmark = blackNum;
        return true;
      }
      else {
        return blackNum == benchmark;
      }
    }
    if (root->_color == BLACK) ++blackNum;
    if (root->_color == RED && root->_parent->_color == RED) return false;
        //逻辑短路，若root结点为红色，其就不可能为根结点，一定有parent结点
    return _IsBalance(root->_left, blackNum, benchmark) && 
                _IsBalance(root->_right, blackNum, benchmark);
  }
  void rotate_left(TreeNode* parent) {
    TreeNode* subR = parent->_right;
    TreeNode* subRL = subR->_left;
    TreeNode* pparent = parent->_parent;
    parent->_right = subRL;
    if (subRL != nullptr) subRL->_parent = parent;
    subR->_left = parent;
    parent->_parent = subR;
    //解决根结点变换带来的问题
    if (_root == parent) {
      _root = subR;
      subR->_parent = nullptr;
    }
    else {
      if (pparent->_left == parent) pparent->_left = subR;
      else pparent->_right = subR;
      subR->_parent = pparent;
    }
  }
  void rotate_right(TreeNode* parent) {
    TreeNode* subL = parent->_left;
    TreeNode* subLR = subL->_right;
    TreeNode* pparent = parent->_parent;
    parent->_left = subLR;
    if (subLR != nullptr) subLR->_parent = parent;
    subL->_right = parent;
    parent->_parent = subL;
    if (_root == parent) {
      _root = subL;
      subL->_parent = nullptr;
    }
    else {
      if (pparent->_left == parent) pparent->_left = subL;
      else pparent->_right = subL;
      subL->_parent = pparent;
    }
  }
private:
  TreeNode* _root = nullptr;
};
void RBTreeTest() {
  size_t N = 10000;
  srand((unsigned)time(NULL));
  RedBlackTree<int, int> t;
  for (size_t i = 0; i < N; ++i) {
    int x = rand();
    //cout << "insert:" << x << ":" << i << endl;
    t.insert(make_pair(x, i));
  }
  t.inorder();
  cout << t.IsBalance() << endl;
}
int main() 
{
  RBTreeTest();
  return 0;
}

五、红黑树与AVL树的比较

与AVL树的平衡 (左右高度差不超过1) 相比，红黑树的平衡(没有一条路径会比其他路径长出两倍)并没有那么严格。所以两者在插入或删除相同数据时，红黑树需要旋转调整的次数更少，这使得红黑树的性能略高于AVL树。

可是AVL树更加平衡，查找数据所需的次数不是更加少吗？在AVL树与红黑树中进行数据的查找都十分快捷(譬如在查找100万数据中进行查找只需大概20次)，对于CPU从时间上来说并不会造成什么负担。

总的来说，AVL树更适用于插入删除不频繁，只对查找要求较高的场景; 红黑树相较于AVL树更适应对插入、删除、查找要求都较高的场景，红黑树在实际中运用更加广泛。

手撕红黑树

一、概念

二、红黑树的插入操作

第一步: 按照二叉搜索树的规则插入新节点

第二步: 插入后检测性质是否造到破坏，若遭到破坏则进行调整

情况一: cur为红，parent为红，grandfather为黑，uncle存在且为红

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑(单旋+变色)

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑(双旋+变色)

三、红黑树的验证

检测其是否满足二叉搜索树

检测其是否满足红黑树的性质

四、完整代码

五、红黑树与AVL树的比较

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

手撕红黑树

一、概念

二、红黑树的插入操作

第一步: 按照二叉搜索树的规则插入新节点

第二步: 插入后检测性质是否造到破坏，若遭到破坏则进行调整

情况一: cur为红，parent为红，grandfather为黑，uncle存在且为红

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑(单旋+变色)

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑(双旋+变色)

三、红黑树的验证

检测其是否满足二叉搜索树

检测其是否满足红黑树的性质

四、完整代码

五、红黑树与AVL树的比较

热门文章

最新文章

相关电子书