概念
红黑树是一种二叉搜索树,一般的二叉搜索会发生不平衡现象,导致搜索效率下降,于是学者们开始探索如何让二叉搜索树保持平衡,这种树叫做自平衡二叉搜索树。起初学者发明了AVL树,其通过一定算法保持了二叉搜索树的严格平衡,不久后Rudolf Bayer发明了红黑树,红黑树的平衡是较为宽泛的,为了保持平衡,红黑树付出的代价比AVL树更小。
红黑树的要求如下:
红黑树中,最长路径的长度不会超过最短路径的两倍
先解释一下路径
的概念:从根走到nullptr
。
有不少人认为路径是从根走到叶子节点,这是不正确的。
红黑树用了五条规则来限制一棵树,从而达到以上要求:
- 每个节点不是红色就是黑色
- 根节点一定是黑色
- 不可以出现连续的红色节点(黑色可以连续出现)
- 每一条路径都包含相同数目的黑色节点
nullptr
视为黑色节点
只要满足以上五个条件,那么这棵树就是一颗红黑树,而且满足最长路径的长度不会超过最短路径的两倍。
实现
基本结构
首先我们要在节点中加入一个成员来表示节点的颜色,颜色有红黑和黑色两种状态,这里我使用枚举来区分两者:
enum Colour
{RED,BLACK
};
在某些红黑树的实现中,使用bool
值来表示红黑颜色,这也是可以的,但是本博客以枚举来表示颜色。
节点类:
template<class K, class V>
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pair<K, V> _kv;Colour _col;
};
对于一棵红黑树,其所有路径的黑色节点数目都相同,如果我们在某一条路径末尾插入了黑色节点,那么整棵树的所有其它路径都会少一个黑节点。而插入红色节点只影响当前路径,所以新节点应该是红色节点。
构造函数:
RBTreeNode(const pair<K, V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED)//初始化为红节点
{}
接着就是红黑树本体,类中只存储一个根节点_root
:
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
private:Node* _root = nullptr;
}
插入
那么我们先写出当基本的二叉搜索树的插入代码逻辑,既然要插入,那么就要先找到合适的位置插入
bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//保持根为黑节点}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first > kv.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;//调整红黑树//......//......//......return true;
}
对于红黑树的插入,我们需要关注新节点的父亲parent
,祖父grandfather
,叔叔uncle
三个节点:
- 先根据父亲节点的颜色,来判断是否需要调整
父亲节点为黑色:
新插入的节点默认为红色,所以新插入节点不会影响路径上黑色节点的数目,而parent
是黑节点,我们也没有出现连续的红色节点,所以这种情况无需任何调整,直接插入就可以。
父亲节点为红色:
如果父亲节点为红色,我们就会出现连续的红色节点,这时我们就需要进行调整了
当parent
为红色,我们就需要再根据uncle
的颜色,将插入分类两类:uncle为红色
以及uncle为黑色
。
值得注意的是:由于parent
是红色节点,此时的grandfather
一定是黑色节点,因为不能出现连续红色节点。
uncle为红色节点
当
uncle
节点为红色,此时需要进行变色
我们将grandfather
变为了红色,这有可能会影响到上一层节点,所以我们要写一个while循环,来反复向上检查。
当前代码如下:
while (parent && parent->_col == RED)//只有parent为红,才更新 (parent可能不存在)
{Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;//uncle存在且为红节点if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//uncle为黑节点 {//其它处理}}else{Node* uncle = grandfather->_left;//uncle存在且为红节点if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//uncle为黑节点 {//其它处理}}
}_root->_col = BLACK;//在循环内部不判断root情况,统一处理
uncle为黑色节点
由于红黑树中,nullptr
也算作黑色节点,所以uncle
为黑色分为以下两种情况:
uncle
为空指针uncle
不为空指针
如果 uncle
为空指针,那么cur
一定是新插入的节点。
因为如果cur
不是新插入的节点,那么cur
和parent
一定有一个原先是黑色节点,不然会出现连续的红色节点。但是如果cur
和parent
有一个是黑色节点,那么grandfather
的左子树就比右子树多出一个黑节点,这就违背了红黑树规则。
如果 uncle
不为空指针,那么cur
一定是从黑色节点变成的红色节点(不是新插入的)。
因为如果uncle
存在,那么grandfather
的右子树就存在一个黑节点,而parent
是红节点,所以cur
和parent
的右子树中都至少有一个黑节点,才能保证每一条路径黑节点数目相同。因此cur
原先一定是黑节点,是因为cur
下层插入了新节点,然后通过while
循环向上走,影响到了当前层。
对于这种uncle
为黑色的情况,我们需要通过旋转+变色来维持红黑树。
旋转又分为单旋和双旋:
当
cur
与parent
的关系和parent
与grandfather
的关系一致时,需要进行单旋
cur
是parent
的左子树,parent
是grandfather
的左子树,关系一致。
我们需要对其进行右单旋+变色:
当
cur
与parent
的关系和parent
与grandfather
的关系不一致时,需要进行双旋
以上结构中,cur
是parent
的左子树,parent
是grandfather
的右子树,关系不一致,要进行双旋。
以上单旋和双旋的变色,看似复杂,其实最后都是把新根的颜色变为黑色,新根的左右子树变为红色。由于我们旋转后,新根都是黑节点,所以不会影响上层,可以直接跳出循环。
当parent == grandfather->_left
:
else//uncle为黑节点 (旋转)
{if (cur == parent->_left){RotateR(grandfather);//右单旋parent->_col = BLACK;//变色grandfather->_col = RED;//变色}else{RotateL(parent);//左右双旋 - 左单旋RotateR(grandfather);//左右双旋 - 右单旋cur->_col = BLACK;//变色grandfather->_col = RED;//变色}break;//旋转后一定平衡
}
当parent == grandfather->_right
:
else//uncle为黑节点 (旋转)
{if (cur == parent->_right){RotateL(grandfather);//左单旋parent->_col = BLACK;//变色grandfather->_col = RED;//变色}else{RotateR(parent);//右左双旋 - 右单旋RotateL(grandfather);//右左双旋 - 左单旋cur->_col = BLACK;//变色grandfather->_col = RED;//变色}break;//旋转后一定平衡
}
insert
总代码:
bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//保持根为黑节点}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first > kv.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;while (parent && parent->_col == RED)//只有parent为红,才更新 (parent可能不存在){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;//uncle存在且为红节点if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//uncle不存在或为黑节点 (旋转){if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//旋转后一定平衡}}else{Node* uncle = grandfather->_left;//uncle存在且为红节点if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//uncle不存在或为黑节点 (旋转){if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//旋转后一定平衡}}}_root->_col = BLACK;//在循环内部不判断root情况,统一处理return true;
}
总代码展示
红黑树总代码:RBTree.h
:
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _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:bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//保持根为黑节点}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first > kv.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;while (parent && parent->_col == RED)//只有parent为红,才更新 (parent可能不存在){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;//uncle存在且为红节点if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//uncle不存在或为黑节点 (旋转){if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//旋转后一定平衡}}else{Node* uncle = grandfather->_left;//uncle存在且为红节点if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//uncle不存在或为黑节点 (旋转){if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//旋转后一定平衡}}}_root->_col = BLACK;//在循环内部不判断root情况,统一处理return true;}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppNode->_left == parent)ppNode->_left = subR;elseppNode->_right = subR;subR->_parent = ppNode;}}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent)ppNode->_left = subL;elseppNode->_right = subL;subL->_parent = ppNode;}}size_t Size(){return _Size(_root);}size_t _Size(Node* root){if (root == nullptr)return 0;;return _Size(root->_left) + _Size(root->_right) + 1;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}//中序void InOrder(){_InOrder(_root);cout << "end" << endl;}int Height(){return _Height(_root);}private://中序void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " - ";_InOrder(root->_right);}//求高度int _Height(Node* root){if (root == nullptr)return 0;return max(Height(root->_left), Height(root->_right)) + 1;}Node* _root = nullptr;
};