当前位置：首页 > news >正文

【数据结构】红黑树——领略天才的想法

news 来源：原创 2024/9/20 17:37:13

个人主页：东洛的克莱斯韦克-CSDN博客

祝福语：愿你拥抱自由的风

二叉搜索树

AVL树

红黑树概述

性质详解

效率对比

旋转操作

元素操作

代码实现

二叉搜索树

【数据结构】二叉搜索树-CSDN博客

AVL树

【数据结构】AVL树——平衡二叉搜索树-CSDN博客

红黑树概述

概念

在二叉搜索树的基础上符合一下性质便是红黑树

每一个节点不是红色就是黑色

根节点一定是黑色

空节点一定是黑色

父亲节点和孩子节点不能是连续的红色节点

每一条根节点至空节点路径上的黑色节点的数量一定相等

性质详解

理解路径

红黑树中，一条完整路径不是从叶子节点溯源至根节点，而是从空节点溯源至根节点

理解最长和最短路径

如果全是黑色节点，红黑树就是一颗满二叉树，因为每条路径的黑色节点数量相等

那么这颗树的每条完整路径都是最短路径，

如果在一条路径上红黑节点间隔（不允许连续的有红色节点），那么该路径为最长路径。

红黑树规则

那么最长路径是最短路径的两倍。这便是红黑树的平衡规则。

满二叉树的平衡条件是左右子树高度差为0，AVL树的平衡条件是左右子树高度差小于等于 1，相比于前两棵树平衡条件，红黑树是一种弱平衡。

红黑树和AVL树一样，只要保证自己的平衡规则不被打破，就能使自己不退化为类似于链表的结构。

退化成类似链表的结构——插入的数据接近有序或插入大量的数据不够随机或进行了一些插入删除等操作。

效率对比

查找效率

从直觉上讲，红黑树只是维持一种弱平衡，在最坏情况下，红黑树的高度是AVL树高度的两倍，那么红黑树查找数据的效率也应该比AVL树低两倍才对，为什么我们认为红黑树是一种更优的数据结构呢？下面小编带大家算笔账

2的40次方是一万亿，也就是说用满二叉树存一万亿个数据高度为40。AVL树是有高度差的，所以最坏情况下会查找40多次，而红黑树最坏情况下会找80多次。

那么对于cpu而言，找40多次和找80多次有区别吗？答案是没有的，现在的cpu每秒钟可以运算十亿次甚至几百亿。

可以理解为，在查找数据的效率上AVL树和红黑树是一样的。那么，红黑树的优势在哪里呢？

插入删除效率

不管是红黑树还是AVL树，如果打破平衡都需要旋转这一操作恢复平衡，旋转所付出的时间复杂度为 $O(1)$ 。对于AVL树而言，需要溯源更新平衡因子，对于红黑树而言，需要溯源更新节点颜色，溯源更新最坏情况下是从叶子节点更新到根节点，所付出的时间复杂度为 $O(logN)$ 。

因为AVL树的高度差小于等于1，平衡很容易被打破，要维持平衡就需要不断地付出 $O(1)$ 和 $O(logN)$ 来维持平衡。

那么红黑树维持弱平衡就不需要总是付出这样地代价，所以红黑树是一种更优的数据结构

旋转操作

旋转操作不是AVL树或红黑树特有的，旋转一次的本质是让二叉搜索树的某棵子树的高度减一。

对于红黑树而言，最长路径是最短路径的二倍加一，就意味着打破平衡，需要通过旋转让最长路径上的某棵子树高度减一来恢复平衡。旋转后需要更新节点的颜色，具体要怎么控制颜色下面细讲，现在看一下旋转操作吧

左单旋：新节点插入较高右子树的右侧——对fathernode

void RevolveLeft(node *& fathernode)//左单旋      
{node* cur = fathernode->_right; //父亲节点的右孩子fathernode->_right = cur->_left; //更改指向关系if (cur->_left != nullptr) //特殊情况cur->_left->_FatherNode = fathernode;//更改指向关系cur->_FatherNode = fathernode->_FatherNode;//更改指向关系if (fathernode->_FatherNode != nullptr) //为空是特殊情况，{if (fathernode->_FatherNode->_right == fathernode){fathernode->_FatherNode->_right = cur;//更改指向关系}else{fathernode->_FatherNode->_left = cur;//更改指向关系}}cur->_left = fathernode;//更改指向关系fathernode->_FatherNode = cur;//更改指向关系}

右单旋：新节点插入较高左子树的左侧——对fathernode

void RevolveRight(node *& fathernode) //右单旋
{node* cur = fathernode->_left; //父亲节点的左节点fathernode->_left = cur->_right;//更新指向关系if (cur->_right != nullptr) //特殊情况cur->_right->_FatherNode = fathernode;//更新指向关系cur->_FatherNode = fathernode->_FatherNode;//更新指向关系if (fathernode->_FatherNode != nullptr)//特殊情况{if (fathernode->_FatherNode->_right == fathernode){fathernode->_FatherNode->_right = cur;//更新指向关系}else{fathernode->_FatherNode->_left = cur;//更新指向关系}}cur->_right = fathernode;//更新指向关系fathernode->_FatherNode = cur;//更新指向关系}

左右双旋：新节点插入在较高左子树的右侧——先对fathernodeL左单旋再对fathernodeLR右单旋

右左双旋：新节点插入再较高右子树的左侧——先对fathernodeR右单旋再对fathernodeRL左单旋

元素操作

我们再来理解一下红黑树两条核心性质

父亲节点和孩子节点不能是连续的红色节点

每一条根节点至空节点路径上的黑色节点的数量一定相等

红黑树插入的新节点应该是黑色还是红色呢？

也就是说，插入红色节点可能会破坏第一条性质，插入黑色节点会破坏第二条性质。第一条性质被破坏只影响了当前路径，而第二条性质被破坏影响的是所有路径。所以插入新节点的颜色是红色。

如果新插入节点的父亲节点是黑色，那么不会破坏任何性质，如果新插入节点的父亲节点是红色该怎么办呢？

颜色管理

下面介绍红黑树如何通过管理颜色来判断是否需要旋转，为了方便讨论讨论，给以下节点起个别名，

父亲节点：Father

孩子节点：child（父亲节点的孩子节点）

祖父节点：grandfather（父亲节点的父亲节点）

叔叔节点：uncle（如果父亲节点是祖父节点的左孩子，叔叔节点就是祖父节点的右孩子，反之亦然）

如果新节点的父亲节点为黑，插入成功。如果父亲节点为红，需要溯源更新颜色，规则如下：

如果uncle存在且为红色，Father和uncle变为黑色，grandfather变为黑色，让grandfather变为child，继续溯源更新。

如果更新至整棵树的根节点（Father为空），让根节点置黑，或uncle为空或uncle黑色，停止溯源更新（uncle为空或uncle黑色后面会讨论）。

如果uncle不存在，或uncle存在且为黑，说明红黑树的平衡被打破了，此时就不需要溯源更新颜色了，需要旋转来恢复红黑树的平衡，旋转之后再更新Father，grandfather或child的颜色

右单旋颜色更新：

Father成为了根需要变成黑色节点，Father旋转之前的孩子节点为黑，该孩子会成为grandfather左孩子，grandfather需要变成红节点。

为什么Father旋转之前的孩子节点为黑呢？因为数据是一个一个插入的，新节点只会和一条路径上的父亲节点冲突，如果这是一颗正常的红黑树，Father旋转之前的孩子节点只能为黑色。Father作为根是黑色的，Father的孩子节点也只能是红色的。下面的旋转也一样

左单旋颜色更新：

还是和右单旋一样，Father成了根需要变成黑色，grandfather需要变成红色。

双旋颜色更新：

无论是左右双旋还是右左双旋，最终都是child变成了根，grandfather和Father变成了child的左右孩子，grandfatjie作为孩子需要变成红色。

代码实现

【C++】详解C++的模板-CSDN博客

enum Color { RED, BLACK };    template <class K>
class RBTreeNode
{
public:typedef RBTreeNode <K> node_type;   K _ky;   node_type* _left;node_type* _right;node_type* _FatherNode;  Color _color;RBTreeNode(const K& key):_ky(key),_left(nullptr),_right(nullptr), _FatherNode(nullptr)  ,_color(RED){}};template <class K> 
class RBTree
{
public:typedef RBTreeNode <K> node_type;RBTree():_root(nullptr)    {}bool Insert(const K& key)//插入元素     {////if (nullptr == _root) //是否是空树{_root = new node_type(key);_root->_color = BLACK;     return true;}//node_type* cur = _root;node_type* fathernode = nullptr;  while (cur){if (cur->_ky < key)    {fathernode = cur;  cur = cur->_right;}else if (cur->_ky > key)     {fathernode = cur;cur = cur->_left;}else{return false;}}cur = new node_type(key); //新插入节点 if (fathernode->_ky < cur->_ky)    {fathernode->_right = cur;cur->_FatherNode = fathernode;}else{fathernode->_left = cur;cur->_FatherNode = fathernode;}while (fathernode && fathernode->_color == RED)  {node_type* grandfather_node = fathernode->_FatherNode;node_type* unclenode = nullptr;if (fathernode == grandfather_node->_left) //父亲节点是祖父节点的左孩子{unclenode = grandfather_node->_right; //叔叔节点是祖父节点的右孩子if (unclenode == nullptr || unclenode->_color == BLACK){if (cur == fathernode->_left)  {RevolveRight(fathernode);fathernode->_color = BLACK;grandfather_node->_color = RED; }else if (cur == fathernode->_right){RevolveLeft(fathernode);RevolveRight(cur);cur->_color = BLACK;   grandfather_node->_color = RED;     }}else{fathernode->_color = BLACK; //父亲变黑unclenode->_color = BLACK;  //叔叔变黑grandfather_node->_color = RED; //爷爷变红cur = grandfather_node;fathernode = cur->_FatherNode; }}else//父亲节点是祖父节点的右孩子{unclenode = grandfather_node->_left; //叔叔节点是祖父节点的左孩子       if (unclenode == nullptr || unclenode->_color == BLACK){if (cur == fathernode->_right){RevolveLeft(fathernode);   fathernode->_color = BLACK;grandfather_node->_color = RED;}else if (cur == fathernode->_left){RevolveRight(fathernode);RevolveLeft(cur);     cur->_color = BLACK;grandfather_node->_color = RED;}}else  {fathernode->_color = BLACK; //父亲变黑unclenode->_color = BLACK;  //叔叔变黑grandfather_node->_color = RED; //爷爷变红cur = grandfather_node;fathernode = cur->_FatherNode;}}}_root->_color = BLACK;  return true;}private:void RevolveLeft(node_type*& fathernode)//左单旋        {node_type* cur = fathernode->_right;  fathernode->_right = cur->_left;if (cur->_left != nullptr)cur->_left->_FatherNode = fathernode;cur->_FatherNode = fathernode->_FatherNode;if (fathernode->_FatherNode != nullptr){if (fathernode->_FatherNode->_right == fathernode){fathernode->_FatherNode->_right = cur;}else{fathernode->_FatherNode->_left = cur;}}cur->_left = fathernode;fathernode->_FatherNode = cur;}void RevolveRight(node_type*& fathernode) //右单旋 {node_type* cur = fathernode->_left;  fathernode->_left = cur->_right;if (cur->_right != nullptr)cur->_right->_FatherNode = fathernode;cur->_FatherNode = fathernode->_FatherNode;if (fathernode->_FatherNode != nullptr){if (fathernode->_FatherNode->_right == fathernode){fathernode->_FatherNode->_right = cur;}else{fathernode->_FatherNode->_left = cur;}}cur->_right = fathernode;fathernode->_FatherNode = cur;}node_type* _root;
};