上高县建设局网站,网站建设制作、微信公众号,aso优化方法,榆林华科网站建设红黑树浅浅学习 红黑树概念红黑树平衡性调整 红黑树概念
二叉树#xff1a;二叉树是每个节点最多有两个子树的树结构。二叉查找树#xff1a;又称“二叉搜索树”#xff0c;左孩子比父节点小#xff0c;右孩子比父节点大#xff0c;还有一个特性就是”中序遍历“可以让结… 红黑树浅浅学习 红黑树概念红黑树平衡性调整 红黑树概念
二叉树二叉树是每个节点最多有两个子树的树结构。二叉查找树又称“二叉搜索树”左孩子比父节点小右孩子比父节点大还有一个特性就是”中序遍历“可以让结点有序。平衡二叉树它是一颗空树或者它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一颗平衡二叉树。红黑树是一种自平衡的二叉查找树它属于平衡树但是却没有平衡二叉树那么“平衡”。可以保证在最坏情况下基本动态操作的时间复杂度为O(log n)。红黑树中的每个节点都有一个颜色属性可以是红色或黑色。
红黑树满足以下5个性质
每个节点要么是红色的要么是黑色的根节点是黑色的。每个叶子节点NIL节点空节点是黑色的。任何相邻节点不能同时为红色。任何叶子节点到根节点所经过的黑节点数目相同。当前节点到其所有叶节点包含的黑色节点数量相同。
通过这些性质红黑树可以保证在插入和删除节点时自动调整树的结构以保持树的平衡和性质的满足。相比于普通的二叉查找树红黑树的平衡性更好查找、插入和删除都具有更稳定的时间复杂度因此在很多场景下被广泛应用。 红黑树平衡性调整
依次插入 100 90 120不需要进行平衡性调整 插入85把90和120变成黑色100变成红色。但100必须为黑色100也变成黑色
平衡性调整情况1爷节点为黑色父节点为红色且有叔节点为红色父亲节点为爷节点的左孩子
将父节点和叔节点都变为黑色。爷节点变成红色 若爷节点变色之后红黑树性质出现问题需要沿着爷节点继续向上调整若爷节点为根节点要变黑色。
插入60为红色红黑树继续进行调整85变成黑色90变成红色。
平衡性调整情况2爷节点为黑色父节点为红色没有叔节点或叔节点为黑色父亲节点为爷节点的左孩子插入的节点是父节点的左孩子
平衡性调整情况3爷节点为黑色父节点为红色没有叔节点或叔节点为黑色父亲节点为爷节点的右孩子插入的节点是父节点的左孩子
平衡性调整情况4-6分别为1-3的反情况
#include iostream
#include list
#include vector
#include string
#include map
#include set
#include assert.h
#include sstream
#include stackusing namespace std;templatetypename T
struct RBNode{T data;RBNode* leftChild;RBNode* rightChild;RBNode* parentNd;bool isRed; //判断是否为红色节点。
};templatetypename T
class RBTree{
public:RBTree():root(nullptr){}~RBTree(){ReleaseNode(root);}void InsertElem(const Te){InsertElem(root,e);}void InsertElem(RBNodeT* tNode, const T e){ //第一个参数类型指针引用RBNodeT* point tNode; // 从指向根节点开始RBNodeT* parent nullptr; // 保存父节点根节点的父节点先为nullptr// 通过一个while循环寻找要插入节点的位置同时还要把插入路线上所经过的所有节点都保存到栈中因为这些节点的平衡因子可能要调整。while(point !nullptr){if(epoint-data) return; //要插入的数据和当前树中某节点的数据相同不允许插入parent point; // 记录父节点if(e point-data){point point-rightChild;}else{point point-leftChild;}}// end while// 走到这里point 等于nullptr该生成新节点了point new RBNodeT;point-data e;point-leftChild nullptr;point-rightChild nullptr;point-parentNd nullptr;point-isRed true; //缺省插入的节点先给红色之后才会判断需不需要进行调整if(parent nullptr){// 创建的是根节点point-isRed false;tNode point;return;} // 创建的不是根节点要把节点链接到父节点上if(e parent-data){parent-rightChild point;}else{parent-leftChild point;}point-parentNd parent;if(parent-isRed false) return; //如果父节点是黑色当前插入的又是红色节点不需要做什么直接返回BalanceTune(point,parent);// 不管前面经历了什么根节点固定黑色root-isRed false;}private:// 获取兄弟节点指针RBNodeT* getBrotherNode(RBNodeT* p){// 由调用者确认p-parent 一定不为nullptrif(p-parentNd-leftChild p){return p-parentNd-rightChild;}return p-parentNd-leftChild; }// 平衡性调整void BalanceTune(RBNodeT* point, RBNodeT* parent){// 能走到这里的要插入的节点肯定至少在第三层了因为如果是第二层那么插入的节点都是红色的父节点肯定是黑色的// 父节点为红色才能走下来(当前节点为红色此时需要进行平衡性调整)RBNodeT* parentBroNode nullptr; //叔节点可能不存在RBNodeT* grandFatherNode nullptr; //爷节点因为父节点为红色红色不能为根那么至少都是爷节点做根while(true){parentBroNode (parent-parentNd !nullptr) ? (getBrotherNode(parent)):nullptr; //叔节点grandFatherNode point-parentNd-parentNd; //爷节点// 不断向上调整爷节点可能有为空的时候if(grandFatherNode nullptr) break;// 如果叔节点为红色那么爷节点不可能为红色if(parentBroNode ! nullptr parentBroNode-isRed true){//平衡性调整情况1没有将爷节点置为黑色的原因是统一在外部进行根节点为黑色的设置// 先处理变色问题// (1)父节点和叔节点变为黑色爷节点变为红色parent-isRed false;parentBroNode-isRed false;grandFatherNode-isRed true;// (2)如果爷节点是根跳出循环根节点颜色在循环外进行设置为黑色的处理if(grandFatherNode root) break;// (3) 往上走继续循环point grandFatherNode;parent point-parentNd;if(parent-isRed false) break;continue;} // 能走到这里的平衡性调整情况2不满足if(parentBroNode ! nullptr parentBroNode-isRed true)// 叔节点为黑色或叔节点为空的情况// 旋转变色之前的一些信息这是通用代码RBNodeT* gff grandFatherNode-parentNd; //太爷节点int sign 0; // 标记1grandFatherNode是父节点的左孩子标记2grandFatherNode是父节点的右孩子。if(gff!nullptr){if(gff-leftChild grandFatherNode){sign 1;}else{sign 2;}}if(grandFatherNode-leftChild parent){ //第一种情形父亲是爷节点的左孩子// 开始旋转和变色以调整平衡if(parent-leftChild point){ //新节点是父亲节点的左孩子// 右旋转RotateRight(grandFatherNode);}else{ //新节点是父亲节点的右孩子// 先左旋后右旋RotateLeftRight(grandFatherNode);}// 旋转之后变色的代码通用grandFatherNode-isRed false; //新的根节点设置为黑色grandFatherNode-rightChild-isRed true; //新右叶子设置为红色}else{ // 第二种情形父亲是爷节点的右孩子if(parent-rightChild point){ //新节点是父亲的右孩子RotateLeft(grandFatherNode);}else{RotateRightLeft(grandFatherNode);}// 旋转变色之后的一些公用代码grandFatherNode-isRed false; //新根设置为黑色grandFatherNode-leftChild-isRed true; //新左叶子设置为红色}//*** 一些通用代码// 根已经改变了所以要设置一些节点指向信息if(gff nullptr){root grandFatherNode;}else if(sign 1){gff-leftChild grandFatherNode;}else if(sign 2){gff-rightChild grandFatherNode;}break;}// end while(true)return;}// 右旋转void RotateRight(RBNodeT* pointer){ //注意参数类型RBNodeT* ptmproot pointer;pointer ptmproot-leftChild;pointer-parentNd ptmproot-parentNd;ptmproot-leftChild pointer-rightChild;if(pointer-rightChild){pointer-rightChild-parentNd ptmproot;}pointer-rightChild ptmproot;ptmproot-parentNd pointer;}void ReleaseNode(RBNodeT* pnode){if(pnode !nullptr){ReleaseNode(pnode-leftChild);ReleaseNode(pnode-rightChild);}delete pnode;}private:RBNodeT* root;
};int main()
{RBTreeint myrbtr;int array[] {80,50,120,30,60,20,40};int acount sizeof(array)/sizeof(int);for(int i0;iacount;i){myrbtr.InsertElem(array[i]);}return 0;
}
