C++ RBTree 理论

2023-11-11 23:44

文章标签 c++ 理论 rbtree

本文主要是介绍C++ RBTree 理论，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这个性质可以总结为

红黑树的最短最长路径

红黑树的路径范围

code

结构

搞颜色

类

插入

插入逻辑

新插入节点

思考：2. 检测新节点插入后，红黑树的性质是否造到破坏？

解决方法

变色

旋转+变色

第三种情况，如果根节点上面还有节点

这个性质可以总结为

1.每个节点不是红色就是黑色

2.根节点是黑色的

3.不能有两个连续的红色节点，即可以出现红黑黑黑不能出现红红

4.每条路径上的黑色机节点数量不一样

至于性质5:每个叶子结点都是黑色的，这里的叶子节点并不是真的叶子节点，而是NIL节点，即空节点。如图（a）：

NIL节点有什么作用？如图（a-2），有多少条路径:

正确答案是有7条。路径路径的判断规则是：从根节点到NULL。

如果我们把NIL节点标记出来就好找路径了：

再比如，图(a-3)是否是红黑树：

大致一看好像是，但是把NIL节点标出来之后:

路径(b)只有两个黑色节点，不满足红黑树的性质，不是红黑树。

红黑树的最短最长路径

那么红黑树的最短路径是什么样子的，应该是全黑的最短：

那最长的路径呢，应该是一黑一红间隔排列的最长：

根据图(a-1）我们可以看出，最长的路径是最短的路径的2倍。

一个红黑树不一定有最长路径，也不一定有最短路径。

如图（a-2），有最短路径，没有最长路径:

红黑树的路径范围

而知道了最短路径，最长路径，剩下的路径都在最短路径，最长路径范围内，可以写为

                             [n,2*n]

code

结构

template<class K,class V>struct	RBTreeNode
{RBTreeNode<K,V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* parent;pair<K, V>;Color _col;//初始话列表RBTreeNode(const pair<K, V>kv):_left(nullptr),_right(nullptr), _parent(nullptr), pair<K, V>,_col(RED){}
};

搞颜色

enum Color
{RED,BALACK
};

类

template<class  K,class V>class RBTree{typedef RBTreenode<k,v> Node;public:private:Node* _root = nullptr;};

插入

插入逻辑

如果节点为空，就给黑色。如果节点不为空，就插入值。

这个值如果比根节点小，就往左边插入，否则就往右边插入。

bool Insert(const pair<K, v>& kv){if (_root == nullptr){_root = new(kv);_root->_col = BALACK;return true;}//初始化父亲节点和根节点Node* parent = nullptr;Node* cur = _root;while (cur){//key值大，往右走if (cur->kv.first < kv.first){cur = cur->right;}//key值小，往左走else if (cur->kv.first > kv.first){cur = -cur->left;}//否则key值和当前节点相等，不插入else{return false;}}//找到了返回true1return true;	 }