青海西宁制作网站专业,wordpress无法创建文件,上海公司车牌申请条件,济南做网站的网络公司红黑树的概念
红黑树#xff0c;是一种二叉搜索树#xff0c;但它并不像AVL树一样#xff0c;每个结点绑定一个平衡因子。但在每个结点上增加一个存储位表示结点的颜色#xff0c;可以是Red或Black。 通过 对任何一条从根到叶子的路径上各个结点着色方式的限制#xff0c…红黑树的概念
红黑树是一种二叉搜索树但它并不像AVL树一样每个结点绑定一个平衡因子。但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过 对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 最长路径中结点的个数不会超过最短路径中结点个数的两倍
红黑树的性质
每个结点不是红色就是黑色根节点是黑色的 空树也是红黑树。如果一个节点是红色的则它的两个孩子结点是黑色的 不可能出现连在一起的红色结点。对于每个结点从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点 每条路径里黑色结点个数是相等的。每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
问题
为什么满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两 倍 极端情况下刚好是两倍但是这种极端情况不存在。因为根结点是黑的那么第二层的两个结点都必须是红色的。
红黑树的结构 红黑树结点的定义
enum COLOR{RED,BLACK};templateclass T
struct RBTreeNode
{RBTreeNode(const T data T(), COLOR color RED):_pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _color(color) {}RBTreeNodeT* _pLeft;RBTreeNodeT* _pRight;RBTreeNodeT* _pParent;T _data;COLOR _color;
};为什么要将结点的默认颜色给成红色的
因为如果默认颜色是黑色的话往已经是一颗红黑树里插入的话性质4一定遭到破坏所以给成红色有些情况下破坏有些情况下不被破坏。
红黑树的插入
红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步
1. 按照二叉搜索的树规则插入新节点
templateclass T
class RBTree
{typedef RBTreeNodeT Node;
public:RBTree(){_pHead new Node;_pHead-_pLeft _pHead;_pHead-_pRight _pHead;//构造里已经将双亲给成空}bool Insert(const Tdata){Node* pRoot GetRoot();if (nullptr pRoot) //树为空,创建根结点{pRoot new Node(data,BLACK);pRoot-_pParent _pHead;//只有一个结点head就是根节点的双亲_pHead-_pLeft pRoot; //改变左右指针域_pHead-_pRight pRoot;return true;}else{//说明树已经不为空了//1.按照二叉搜索树的性质找到带插入结点在红黑树的位置Node* pCur pRoot;Node* pParent nullptr;while (pCur){pParent pCur;//标记双亲位置if (data pCur-_data)pCur pCur-_pLeft;else if (datapCur-_data)pCur pCur-_pRight;else//相同不插入return false;}//2. 插入新结点pCur new Node(data);if (data pParent-_data)pParent-_pLeft pCur;else{pParent-_pRight pCur;}//3. 更新双亲位置pCur-_pParent pParent;//4.检测:是否新结点插入后连在一起的红色结点if (RED pParent-_color){//调整//检测新节点插入后红黑树的性质是否造到破坏}}//5.调整头结点的左右指针域//保证根节点是黑色pRoot-_color BLACK;_pHead-_pLeftleftMost();_pHead-_pRight RightMost();return true;}Node* LeftMost(){//得到根节点Node* pRoot GetRoot();if (nullptr pRoot)return _pHead;Node* pCur pRoot;//找到最左侧结点while (pCur-_pLeft)pCur pCur-_pLeft;return pCur;}Node* RightMost(){//得到根节点Node* pRoot GetRoot();if (nullptr pRoot)return _pHead;Node* pCur pRoot;//找到最右侧结点while (pCur-_pRight)pCur pCur-_pRight;return pCur;}
protected:Node* GetRoot() //head是new出来的head存在parent一定存在按引用方式返回没有问题{//得到根节点也就是头结点的下一个结点return _pHead-_pParent;}
private:Node* _pHead;
};2. 检测新节点插入后红黑树的性质是否造到破坏
因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论 cur为当前节点p为父节点g为祖父节点u为叔叔节点
2.1 cur为红p为红g为黑u存在且为红
解决方式将p,u改为黑g改为红然后把g当成cur继续向上调整。
2.2 cur为红p为红g为黑u不存在/u为黑
p为g的左孩子cur为p的左孩子则进行右单旋转相反 p为g的右孩子cur为p的右孩子则进行左单旋转 p、g变色–p变黑g变红
如果u不存在假设cur本来就存在cur和双亲比然是黑的因为两个红的不能连在一起那么这条路径里就有两个黑色所以不满足性质4cur所以一定是新插入的结点如果u存在且为黑色右侧路径里有两个黑色路径因为两条路径黑色结点必须一样。新节点一插入插入到cur的子树中导致子树中不满足情况。向上调整时把cur改成黑色。
2.3 cur为红p为红g为黑u不存在/u为黑 红黑树的验证
红黑树的检测分为两步
检测其是否满足二叉搜索树(中序遍历是否为有序序列)检测其是否满足红黑树的性质
templateclass T
class RBTree
{typedef RBTreeNodeT Node;
public:RBTree(){_pHead new Node;_pHead-_pLeft _pHead;_pHead-_pRight _pHead;//构造里已经将双亲给成空}bool Insert(const Tdata){Node* pRoot GetRoot(); //必须以引用的方式进行接受if (nullptr pRoot) //树为空,创建根结点{pRoot new Node(data,BLACK);pRoot-_pParent _pHead;//只有一个结点head就是根节点的双亲_pHead-_pLeft pRoot; //改变左右指针域_pHead-_pRight pRoot;return true;}else{//说明树已经不为空了//1.按照二叉搜索树的性质找到带插入结点在红黑树的位置Node* pCur pRoot;Node* pParent nullptr;while (pCur){pParent pCur;//标记双亲位置if (data pCur-_data)pCur pCur-_pLeft;else if (data pCur-_data)pCur pCur-_pRight;else//相同不插入return false;}//2. 插入新结点pCur new Node(data);if (data pParent-_data)pParent-_pLeft pCur;elsepParent-_pRight pCur;//3. 更新双亲位置pCur-_pParent pParent;//以上没错//4.检测:是否新结点插入后连在一起的红色结点while (pParent!_pHead RED pParent-_color){Node* granderFather pParent-_pParent;if (pParent granderFather-_pLeft){//叔叔结点在右侧Node* uncle granderFather-_pRight;//情况一:叔叔结点存在且为红if (uncle RED uncle-_color){pParent-_color BLACK;uncle-_color BLACK;granderFather-_color RED;pCur granderFather;pParent pCur-_pParent;}//以上没问题else{//情况三if (pCur pParent-_pRight) //情况三{//转变成情况二RotateLeft(pParent);swap(pParent, pCur);}//情况二pParent-_color BLACK;granderFather-_color RED;RotateRight(granderFather);}//以上没问题}else{//叔叔结点在左侧Node* uncle granderFather-_pLeft;//情况一的反情况if (uncle uncle-_color RED){pParent-_color BLACK;uncle-_color BLACK;granderFather-_color RED;pCur granderFather;pParent pCur-_pParent;}//以上没问题else{//情况三的反情况if (pCur pParent-_pLeft) /**/{//情况三的反情况变成情况二的反情况RotateRight(pParent);swap(pParent, pCur);}//情况二反情况处理pParent-_color BLACK;granderFather-_color RED;RotateLeft(granderFather);}//以上没问题}}}//5.调整头结点的左右指针域//保证根节点是黑色pRoot-_color BLACK;_pHead-_pLeft LeftMost();_pHead-_pRight RightMost();return true;}void InOrder(){_InOrder(GetRoot());}//检测红黑树bool IsValidRBTree(){Node* pRoot GetRoot();if (nullptr pRoot)return true;if (pRoot-_color ! BLACK){cout 违反性质2根结点颜色必须为黑色 endl;return false;}//获取一条路径中结点的个数size_t blackCount 0; //基准值Node* pCur pRoot;while (pCur){if (pCur-_color BLACK)blackCount;pCur pCur-_pLeft;}size_t pathBlack 0; //每条路径中的黑色结点个数return _IsValidRBTree(pRoot, blackCount,pathBlack);}
protected:bool _IsValidRBTree(Node* pRoot, size_t blackCount, size_t pathBlack){if (nullptr pRoot)return true;if (pRoot-_color BLACK)pathBlack;//检测性质3Node* pParent pRoot-_pParent;if (pParent ! _pHead pParent-_color REDpRoot-_color RED){cout 违反性质3:不能有连在一起的红色结点 endl;return false;}if (nullptr pRoot-_pLeftnullptr pRoot-_pRight){//一条路径到叶子if (blackCount ! pathBlack){cout 违反了性质4每条路径中黑色结点个数必须相同 endl;return false;}}return _IsValidRBTree(pRoot-_pLeft, blackCount, pathBlack) _IsValidRBTree(pRoot-_pRight, blackCount, pathBlack);}Node* LeftMost(){//得到根节点Node* pRoot GetRoot();if (nullptr pRoot)return _pHead;Node* pCur pRoot;//找到最左侧结点while (pCur-_pLeft)pCur pCur-_pLeft;return pCur;}Node* RightMost(){//得到根节点Node* pRoot GetRoot();if (nullptr pRoot)return _pHead;Node* pCur pRoot;//找到最右侧结点while (pCur-_pRight)pCur pCur-_pRight;return pCur;}void RotateLeft(Node* pParent){Node* pSubR pParent-_pRight;Node* pSubRL pSubR-_pLeft;pParent-_pRight pSubRL;if (pSubRL)pSubRL-_pParent pParent;pSubR-_pLeft pParent;Node* pPParent pParent-_pParent;pParent-_pParent pSubR;pSubR-_pParent pPParent;if (pPParent _pHead)GetRoot() pSubR;else{if (pPParent-_pLeft pParent)pPParent-_pLeft pSubR;elsepPParent-_pRight pSubR;}}void RotateRight(Node* pParent){Node* pSubL pParent-_pLeft;Node* pSubLR pSubL-_pRight;pParent-_pLeft pSubLR;if (pSubLR)pSubLR-_pParent pParent;pSubL-_pRight pParent;Node* pPParent pParent-_pParent;pParent-_pParent pSubL;pSubL-_pParent pPParent;//pParent是根结点if (pPParent _pHead)GetRoot() pSubL;else{//非根结点if (pPParent-_pLeft pParent)pPParent-_pLeft pSubL;elsepPParent-_pRight pSubL;}}Node* GetRoot() //head是new出来的head存在parent一定存在按引用方式返回没有问题{//得到根节点也就是头结点的下一个结点return _pHead-_pParent;}void _InOrder(Node* pRoot){if (pRoot){_InOrder(pRoot-_pLeft);cout pRoot-_data ;_InOrder(pRoot-_pRight);}}
private:Node* _pHead;
};void TestRBTree()
{int array[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };RBTreeintt;for (auto e : array)t.Insert(e);t.InOrder();if (t.IsValidRBTree()){cout t is vaild rbTree endl;}elsecout t is not vaild rbTree endl;
}红黑树的删除
参考链接1 参考链接2
红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O( log2N)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。
红黑树的应用
Java中的java.util.TreeMap,java.util.TreeSetC STL中的map,multimap,multiset.NET中的SortedDictionary,SortedSet 等
模拟实现map和set
模拟实现
