服装网站 欣赏,企业微信和个人微信的区别,网站后台界面,住房和城乡建设部网站防排烟一、红黑树的概念
红黑树是一种二叉搜索树#xff0c;在其每个节点上增加一个存储位用于表示节点的颜色#xff0c;可以是Red或Black
通过对任何一条从根到叶子的路径上的各个节点着色方式的限制#xff0c;红黑树确保没有一条路径比其他路径长两倍 红黑树的性质#xff…一、红黑树的概念
红黑树是一种二叉搜索树在其每个节点上增加一个存储位用于表示节点的颜色可以是Red或Black
通过对任何一条从根到叶子的路径上的各个节点着色方式的限制红黑树确保没有一条路径比其他路径长两倍 红黑树的性质 ①每个结点的颜色不是红色就是黑色 ②根节点是黑色的 ③如果一个节点是红色的则它的两个孩子节点是黑色的不能出现连续的红色节点 ④对于每个节点从该节点到其所有后代叶子节点的简单路径上均包含数量相同的黑色节点每条路径上都有相同数量的黑色节点 路径的计算必须最终指向空
红黑树的最短路径路径上所有节点的颜色都为黑色 最长路径路径上节点黑红相间一黑一红
假设黑色节点总共有N个整棵树的节点数量在[N2N]之间
最短路径长度为logN 最长路径长度为2logN
红黑树通过规则的约束使得最长路径的搜索长度不超过最短路径搜索长度的二倍
二、红黑树节点的定义
红黑树节点中包括指向左右孩子以及父节点的指针当前节点的颜色与存储数据
红黑树节点的构造中默认设置新插入节点的颜色为红色
是因为如果插入节点颜色为黑色那么一定会违背上面描述红黑树性质中的第四条每条路径上都有数量相同的黑色节点。因此为了最大程度减少对原本红黑树的影响默认颜色为红色
enum Colour
{RED,BLACK,
};templateclass T
struct RBTreeNode
{RBTreeNodeT* _lef;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;Colour _col;//节点的构造默认颜色为红色RBTreeNode(const T data):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED),_data(data){}
};
三、红黑树的插入
红黑树是在二叉搜索树的基础上增加平衡限制条件红黑树的插入因此可以分为两步①按照二叉搜索树的规则插入新节点即找位置插入调整②插入新节点之后判断红黑树的性质是否遭到破坏
由于新节点默认为红色因此如果其双亲节点为黑色则并不违反红黑树的性质则不需要调整
如果双亲节点为红色则会出现连续的红色节点。违反红黑树的性质需要调整。此时需要分情况讨论
假设当前节点为cur其父节点为parent其叔叔节点为uncle其祖父节点为grandparent
情况一cur为红p为红g为黑u存在且为红 插入cur后 此时已经出现连续的红色节点因此需要进行调整。保持插入节点cur颜色不变改变其祖宗节点颜色 调整后 如果g是根节点则需要将g的颜色改为黑色
如果g不是根节点则g一定具有父亲节点。如果g的父亲节点也为红色则继续向上调整颜色 为什么不能直接修改cur的颜色而是向上调整 是由于如果插入节点cur的颜色直接改为黑色则很有可能导致路径上黑色节点的数量不同同样导致不满足红黑树的性质。一般情况下插入红色对红黑树的影响最小 以上图调整前为例。如果将cur的颜色变为黑色则g从左子树到达叶子节点的黑色节点数量为1而右子树到达叶子节点的黑色节点数量为0 情况二cur为红p为红g为黑u不存在/u存在并且为黑
情况二一般是由情况一变化而来 其中cde都可以是子树其形状均有四种可能性如下 因此在新插入节点并进行了一次调整后出现u存在且为黑的情况。需要进行右单旋与变色 旋转变色后 u不存在的情况与存在且为黑色的处理完全类似。只是u存在为单旋不存在是双旋
程序实现
#pragma once
#includeiostream
using namespace std;enum Colour
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Colour _col;//节点的构造默认颜色为红色RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:~RBTree(){_Destroy(_root);_root nullptr;}
public: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;}bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* parent nullptr;Node* cur _root;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;}else{parent-_right cur;}cur-_parent parent;while (parent parent-_col RED){Node* grandfather parent-_parent;if (grandfather-_left parent){Node* uncle grandfather-_right;// 情况1u存在且为红变色处理并继续往上处理if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 继续往上调整cur grandfather;parent cur-_parent;}else // 情况23u不存在/u存在且为黑旋转变色{// g// p u// c if (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;//parent-_col RED;grandfather-_col RED;}break;}}else // (grandfather-_right parent){// g// u p// cNode* uncle grandfather-_left;// 情况1u存在且为红变色处理并继续往上处理if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 继续往上调整cur grandfather;parent cur-_parent;}else // 情况23u不存在/u存在且为黑旋转变色{// g// u p// cif (cur parent-_right){RotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;}void InOrder(){_InOrder(_root);}bool IsBalance(){if (_root _root-_col RED){cout 根节点颜色是红色 endl;return false;}int benchmark 0;Node* cur _root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}// 连续红色节点return _Check(_root, 0, benchmark);}int Height(){return _Height(_root);}private:void _Destroy(Node* root){if (root nullptr){return;}_Destroy(root-_left);_Destroy(root-_right);delete root;}int _Height(Node* root){if (root NULL)return 0;int leftH _Height(root-_left);int rightH _Height(root-_right);return leftH rightH ? leftH 1 : rightH 1;}bool _Check(Node* root, int blackNum, int benchmark){if (root nullptr){if (benchmark ! blackNum){cout 某条路径黑色节点的数量不相等 endl;return false;}return true;}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}return _Check(root-_left, blackNum, benchmark) _Check(root-_right, blackNum, benchmark);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppnode parent-_parent;subR-_left parent;parent-_parent subR;if (ppnode nullptr){_root subR;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subR;}else{ppnode-_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;Node* ppnode parent-_parent;subL-_right parent;parent-_parent subL;if (parent _root){_root subL;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}}private:Node* _root nullptr;
};
