网站导航
> 文档中心 > C++红黑树

C++红黑树

网友: 文档中心 2022-04-07 11:24:55

C++红黑树

  • 零、前言
  • 一、红黑树的概念及性质
  • 二、红黑树结点的定义
  • 三、红黑树的插入操作
    • 1、变色处理
    • 2、单旋+变色
    • 3、双旋+变色
    • 4、插入实现
  • 四、红黑树的验证
  • 五、红黑树的删除
  • 六、红黑树与AVL树的比较

零、前言

本章继AVL树后继续讲解学习C++中另一个二叉搜索树–红黑树

一、红黑树的概念及性质

  • 概念：

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

  2. 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的

注：AVL树是严格平衡的二叉搜索树，左右子树高度不超过1；红黑树是近似平衡，最长路径不超过最短路径的二倍

  • 示图：

C++红黑树

  • 红黑树的性质：

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

  2. 根节点是黑色的

  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的

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

  5. 每个NIL结点都是黑色的(此处的结点指的是空结点)（该条规则确定了路径条数）

  • 为什么红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍：

红黑树第三条性质说明红黑树不能存在连续（父子相连）的红结点，可以存在连续的黑结点，又由于第四条性质每个路径上的黑结点个数都相同 ，所以对于最短路径来说一定是都是黑色结点，对于最长路径来说一定是黑色红色相间的路径，所以最长路径不超过最短路径长度的二倍

  • 示图：

C++红黑树

二、红黑树结点的定义

对于红黑树来说以颜色来代替AVL树的平衡因子的作用，除此之外在定义上没有什么区别

  • 实现代码：
enum Colour//颜色{RED,BLACK,};template<class K, class V>struct RBTreeNode{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}};

注：此处采用枚举来表示，当然也可以使用其他方式

  • 在节点的定义中为什么要将节点的默认颜色给成红色的：

  1. 如果默认颜色为黑，那么在插入中插入一个黑结点一定会让该路径上的黑结点数量加1，从而与其他路径上黑结点数量造成不一致，而一定会影响该棵红黑树

  2. 如果默认颜色为红，那么在插入中插入一个红结点，可能新插入结点的父结点为黑色结点则没有影响，也可能新插入结点的父结点为红结点，由于不能存在连续的（父子相连的）红色结点，而对该棵树造成影响

  3. 所以默认为红色比较黑色来说是好的

三、红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，当违反限制条件时就需要做出相应的调整

  • 红黑树的插入可分为两步：

  1. 按照二叉搜索的树规则插入新节点

  2. 新节点插入后检查红黑树的性质是否造到破坏

  • 注意：

  1. 因为新节点的默认颜色是红色，如果其父亲节点的颜色是黑色，则没有违反红黑树任何性质，则不需要调整

  2. 当新插入节点的父亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论

  3. 因为插入结点的父结点是红色的，说明父结点不是根结点（根结点是黑色的），因此插入结点的祖父结点（父结点的父结点）就一定存在

  4. 红黑树调整时具体应该如何调整，主要是看插入结点的叔叔（插入结点的父结点的兄弟结点），根据插入结点叔叔的不同，可将红黑树的调整分为三种情况

注：约定cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

1、变色处理

情况一: cur为红，p为红，g为黑，u存在且为红

  • 示图：

C++红黑树

  • 分析：

  1. 为了让该以 g 为根的子树不存在连续的红色结点，并且不增加路径上的黑色结点，我们让 g 的颜色变红，让 u 和 p 的颜色变黑，各路径上黑色结点数量没变，以此达到红黑树的性质

  2. 因为 p 和 u 的颜色变黑，对其子树没有影响，但是 g 的颜色变红，可能存在影响，需要继续向上判断

  • 判断逻辑：

  1. 如果 g 就是该棵树的根那么最后需要将 g 的颜色变黑

  2. 如果 g 是整棵树的子树，如果 g 的父节点是是黑色结点则不用调整，如果是红色结点则需要根据具体情况来做出调整

  • 解决方式：

将p,u改为黑，g改为红，然后把g当成cur，继续向上调整

  • 抽象示图：

C++红黑树

  • 动图演示1：

C++红黑树

  • 动图演示2：

C++红黑树

2、单旋+变色

情况二: cur为红，p为红，g为黑，u不存在/u为黑

  • 示图：

C++红黑树

  • 分析：

  1. 当 u 节点不存在时，说明cur一定是插入节点，如果 cur 不是新插入节点，那么在插入前时 cur 一定是黑色结点（由黑色变红），则插入前就不符合路径上黑结点数量相同的性质

  2. 当 u 节点存在且为黑色时，说明 cur 的颜色插入前一定是黑色，进过插入后变色为红色，否则在插入前就存在连续的红色结点，不符合红黑树性质

  • 解决方法：

  1. 如果p为g的左孩子，cur为p的左孩子，则进行右单旋转，p变黑，g变红

  2. 如果p为g的右孩子，cur为p的右孩子，则进行左单旋转，p变黑，g变红

  • 抽象示图：

C++红黑树

  • 动态示图：

C++红黑树

  • 动图演示2：

C++红黑树

3、双旋+变色

情况三: cur为红，p为红，g为黑，u不存在/u为黑

  • 示图：

C++红黑树

  • 分析：

这里显然一次旋转也无法让达到红黑树平衡，由此就需要进行两次旋转

  • 解决方式：

  1. 如果p为g的左孩子，cur为p的右孩子，则针对p做左单旋转，p旋转后再对g进行右单旋，旋转后将cur变黑，g变红

  2. 如果p为g的右孩子，cur为p的左孩子，则针对p做右单旋转，p旋转后再对g进行左单旋，旋转后将cur变黑，g变红

  • 抽象示图：

C++红黑树

  • 动图演示1：

C++红黑树

  • 动图演示2：

C++红黑树

4、插入实现

插入主体实现：

pair<Node*, bool> Insert(const pair<K, V>& kv){    //空树的情况    if (_root == nullptr)    { _root = new Node(kv); _root->_col = BLACK; return make_pair(_root, true);    }    //查找位置插入节点    Node* cur = _root, * parent = _root;    while (cur)    { if (cur->_kv.first > kv.first) {     parent = cur;     cur = cur->_left; } else if (cur->_kv.first < kv.first) {     parent = cur;     cur = cur->_right; } else {     return make_pair(cur, false); }    }    //创建链接节点    cur = new Node(kv);    Node* newnode = cur;    if (parent->_kv.first > kv.first)    { parent->_left = cur;    }    else    { parent->_right = cur;    }    cur->_parent = parent; //父节点存在且为红，则需要调整（不能存在连续的红色节点）    while (parent && parent->_col == RED)    { //此时当前节点一定有祖父节点 Node* granparent = parent->_parent; //具体调整情况主要看叔叔节点 //分左右讨论 if (parent == granparent->_left) {     Node* uncle = granparent->_right;     //情况1：叔叔节点存在且为红     if (uncle && uncle->_col == RED)     {  //修改颜色，继续向上检查  granparent->_col = RED;  parent->_col = uncle->_col = BLACK;  cur = granparent;  parent = cur->_parent;     }     else//情况2和3：叔叔节点不存在 或者存在且为黑     {  //单旋(三代节点为斜线)+变色  if (cur == parent->_left)  {      RotateR(granparent);      granparent->_col = RED;      parent->_col = BLACK;  }  else//双旋(三代节点为折线)+变色  {      RotateL(parent);      RotateR(granparent);      cur->_col = BLACK;      granparent->_col = RED;  }  //旋转后不需再向上调整了  break;     } } else//parent=grandparent->right {     Node* uncle = granparent->_left;     if (uncle && uncle->_col == RED)     {  parent->_col = uncle->_col = BLACK;  granparent->_col = RED;  cur = granparent;  parent = cur->_parent;     }     else     {  if (cur == parent->_right)  {      RotateL(granparent);      parent->_col = BLACK;      granparent->_col = RED;  }  else  {      RotateR(parent);      RotateL(granparent);      cur->_col = BLACK;      granparent->_col = RED;  }  break;     } }    } //确保根节点为黑    _root->_col = BLACK;    return make_pair(newnode, true);}

旋转实现：

void RotateL(Node* parent){    Node* subR = parent->_right;    Node* subRL = subR->_left;    Node* parentP = parent->_parent;    parent->_right = subRL;    if (subRL)    { subRL->_parent = parent;    }    subR->_left = parent;    parent->_parent = subR;    if (parent == _root)    { _root = subR; subR->_parent = nullptr;    }    else    { subR->_parent = parentP; if (parentP->_left == parent) {     parentP->_left = subR; } else {     parentP->_right = subR; }    }}void RotateR(Node* parent){    Node* subL = parent->_left;    Node* subLR = subL->_right;    Node* parentP = parent->_parent;    parent->_left = subLR;    if (subLR)    { subLR->_parent = parent;    }    subL->_right = parent;    parent->_parent = subL;    if (parent == _root)    { _root = subL; subL->_parent = nullptr;    }    else    { subL->_parent = parentP; if (parentP->_left == parent) {     parentP->_left = subL; } else {     parentP->_right = subL; }    }}

四、红黑树的验证

  • 红黑树的检测分为两步：

  1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

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

  • 实现代码：
bool IsRBTree(){    //空树    if (_root == nullptr)    { return true;    }    //根节点为黑色    if (_root->_col == RED)    { cout << "根节点为红色" << endl; return false;    }    //黑色结点数量各路径上相同    //先走一条得到基准值    int Blacknum = 0;    Node* cur = _root;    while (cur)    { if (cur->_col == BLACK)     Blacknum++; cur = cur->_left;    }    //检查子树    int i = 0;    return _IsRBTree(_root, Blacknum, i);}bool _IsRBTree(Node* root, int blacknum, int count){    //递归到空节点    if (root == nullptr)    { if (blacknum == count)     return true; cout << "各路径上黑色节点个数不同" << endl; return false;    }//子节点为红则检查父节点是否为红（通过父节点检查子节点会遇到空节点）    if (root->_col == RED && root->_parent->_col == RED)    { cout << "存在连续红色节点" << endl; return false;    }//计数黑结点    if (root->_col == BLACK) count++;//递归左右子树    return _IsRBTree(root->_left, blacknum, count) && _IsRBTree(root->_right, blacknum, count);}

五、红黑树的删除

红黑树的删除不做讲解，有兴趣可参考：《算法导论》或者《STL源码剖析》
http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html
http://blog.csdn.net/chenhuajie123/article/details/11951777

六、红黑树与AVL树的比较

  • 分析总结：

  1. 红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( )

  2. 红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数

  3. 所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多

  • 附上源码

  • RBTree.h:

#pragma once#include#includeusing namespace std;//颜色enum Colour{RED,BLACK,};template<class K, class V>struct RBTreeNode{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}};template<class K, class V>class RBTree{typedef RBTreeNode<K, V> Node;public:RBTree():_root(nullptr){}void _Destory(Node*& root){if (root == nullptr)return;_Destory(root->_left);_Destory(root->_right);delete root;root = nullptr;}~RBTree(){_Destory(_root);}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first > key){cur = cur->_left;}else if (cur->_kv.first < key){cur = cur->_right;}else{return cur;}}return nullptr;}pair<Node*, bool> Insert(const pair<K, V>& kv){//空树的情况if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return make_pair(_root, true);}//查找位置插入节点Node* cur = _root, * parent = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return make_pair(cur, false);}}//创建链接节点cur = new Node(kv);Node* newnode = cur;if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//父节点存在且为红，则需要调整（不能存在连续的红色节点）while (parent && parent->_col == RED){//此时当前节点一定有祖父节点Node* granparent = parent->_parent;//具体调整情况主要看叔叔节点//分左右讨论if (parent == granparent->_left){Node* uncle = granparent->_right;//情况1：叔叔节点存在且为红if (uncle && uncle->_col == RED){//修改颜色，继续向上检查granparent->_col = RED;parent->_col = uncle->_col = BLACK;cur = granparent;parent = cur->_parent;}else//情况2和3：叔叔节点不存在 或者存在且为黑{//单旋(三代节点为斜线)+变色if (cur == parent->_left){RotateR(granparent);granparent->_col = RED;parent->_col = BLACK;}else//双旋(三代节点为折线)+变色{RotateL(parent);RotateR(granparent);cur->_col = BLACK;granparent->_col = RED;}//旋转后不需再向上调整了break;}}else//parent=grandparent->right{Node* uncle = granparent->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;granparent->_col = RED;cur = granparent;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(granparent);parent->_col = BLACK;granparent->_col = RED;}else{RotateR(parent);RotateL(granparent);cur->_col = BLACK;granparent->_col = RED;}break;}}}//确保根节点为黑_root->_col = BLACK;return make_pair(newnode, true);}bool IsRBTree(){if (_root == nullptr){return true;}if (_root->_col == RED){cout << "根节点为红色" << endl;return false;}int Blacknum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)Blacknum++;cur = cur->_left;}int i = 0;return _IsRBTree(_root, Blacknum, i);}private:bool _IsRBTree(Node* root, int blacknum, int count){if (root == nullptr){if (blacknum == count)return true;cout << "各路径上黑色节点个数不同" << endl;return false;}if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续红色节点" << endl;return false;}if (root->_col == BLACK)count++;return _IsRBTree(root->_left, blacknum, count) && _IsRBTree(root->_right, blacknum, count);}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentP = parent->_parent;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{subR->_parent = parentP;if (parentP->_left == parent){parentP->_left = subR;}else{parentP->_right = subR;}}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentP = parent->_parent;parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{subL->_parent = parentP;if (parentP->_left == parent){parentP->_left = subL;}else{parentP->_right = subL;}}}private:Node* _root;};
  • test.cpp:
#define _CRT_SECURE_NO_WARNINGS 1#include "RBTree.h"#include #include #include #include void TestRBTree(){//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTree<int, int> t;int n = 1000000;srand(time(0));for (int i = 0; i < n; ++i){int e = rand();t.Insert(make_pair(e, e));}//t.InOrder();cout << t.IsRBTree() << endl;}void test_RBTree(){int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}cout << t.IsRBTree() << endl;}int main(){    test_RBTree();TestRBTree();return 0;}
网络标签：

相关问题