您的位置:首页 > 新闻 > 资讯 > 附近图文广告公司电话_行业排名查询网站_百度竞价排名的优缺点_百度竞价推广是什么意思

附近图文广告公司电话_行业排名查询网站_百度竞价排名的优缺点_百度竞价推广是什么意思

2024/12/5 20:51:20 来源:https://blog.csdn.net/2301_80373479/article/details/143485917  浏览:    关键词:附近图文广告公司电话_行业排名查询网站_百度竞价排名的优缺点_百度竞价推广是什么意思
附近图文广告公司电话_行业排名查询网站_百度竞价排名的优缺点_百度竞价推广是什么意思

目录

红黑树的概念

红黑树的约束颜色规则

如何确保最长路径不超过最短路径的2倍

红黑树的效率

红黑树的实现

红黑树的整体框架

红黑树的插入

变色

单旋+变色

双旋+变色

插入的完整代码

红黑树的查找

红黑树的验证

红黑树的测试


红黑树的概念

红黑树,是一种二叉搜索树,但在每个节点增加一个存储位来表示节点的颜色(红色或者黑色),通过对任意一条从根到叶子的路径上各个节点的颜色进行约束,以达到没有任何一条路径会比其他路径的2倍还大,从而保持高度差的平衡

红黑树的约束颜色规则

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

2.根节点是黑色的

3.红色节点两个子节点必须是黑色,任意路径下不允许有连续的两个红色节点

4.任一节点到其每个叶子的所有路径上黑色节点数相同

 以下4可树均是合法的红黑树。

《算法导论》等书籍上补充了⼀条每个叶⼦结点(NIL)都是黑色的规则。他这⾥所指的叶子结点不是传统的意义上的叶子结点,⽽是我们说的空结点,有些书籍上也把NIL叫做外部结点。NIL是为了 ⽅便准确的标识出所有路径,《算法导论》在后续讲解实现的细节中也忽略了NIL结点,知道下即可。

如何确保最长路径不超过最短路径的2倍

根据颜色规则可知,在一棵红黑树中,设从根到叶子的每条路径都有 x 个黑色节点,那么最短路径就是全黑长度为x最长路径是一黑一红交替长度为 2 * x

事实上,最长路径和最短路径在每棵红黑树中不一定存在,任意一条从根到叶子的路径长度 l 的范围应该是x <= l <= 2 * x

红黑树的效率

假设N为红黑树中节点数量,h是最短路径长度,既有 2 ^ h - 1 <= N < 2 ^ (2h) - 1,那么就有h ≈ logN,增删查改的时间复杂度为O(logN)。

红黑树的表达相对AVL树要抽象⼀些,AVL树通过高度差直观的控制了平衡。红黑树通过4条规则的颜色约束,间接的实现了近似平衡,他们效率都是同⼀档次,但是相对而言,插⼊相同数量的结点,红黑树的旋转次数是更少的,因为他对平衡的控制没那么严格。

红黑树的实现

红黑树的整体框架

//枚举值表示颜色
enum Color
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _col;RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),right(nullptr),_parent(nullptr){}};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Nodepublic:private:Node* _root = nullptr;
};

红黑树的插入

红黑树的插入是实现红黑树最关键的一步,具体过程如下:

  • 插入一个值按照二叉搜索树插入,插入后判断是否符合红黑树的4条规则
  • 非空树的插入,插入的节点必须是红色节点,因为插入黑色节点破坏规则4,规则4很难维护;只有在空树插入的情况下,插入节点才可是是黑色,因为根节点必须是黑色。
  • 非空树插入红色节点,如果父亲节点是黑色的插入结束;如果父亲节点是红色的,违反了规则3,需要分情况讨论,进行变色和旋转操作

新增节点为cur,cur的父亲为parent,parent的父亲为grandfather,parent的兄弟为uncle,这4个节点缩写为c、p、g、u

以下这种情况就违反了规则3,需要特殊处理。

变色

cur为红,parent为红,grandfather为黑uncle存在且为红时,则将parent和parent变黑,grandfather变红,那这样就行了嘛吗?不,还没有结束,grandfather变红了,你无法保证grandfather的parent是黑色,grandfather的parent是红色的话还是违反规则,那就得把grandfather当成新的cur继续往上更新,可以说就是往上更新颜色这步,间接导致了单旋+变色和双旋+变色的情况出现

无论cur是parent的左节点还是右节点parent是grandparent的左节点还是节点,都是上面的处理方式。

单旋+变色

cur为红,parent为红,grandfather为黑时:

uncle不存在,则cur一定是新增节点

uncle存在且为黑,则cur一定不是新增的是更新颜色变化出来的(将原来的grandfather黑色节点变成了红色,然后更新cur到grandfather)。

解决方法就是parent必须变黑,解决连续红色节点问题,但uncle不存在或者存在且为黑单纯的变色无法解决需要旋转+变色

单旋+变色也需要分情况进行不同的旋转处理

1.若parent是grandfather的左孩子cur是parent的左孩子,那么先对parent进行右单旋,再把parent变黑grandfather变红

 

2.parent是grandfather的右孩子cur是parent的右孩子,那么先对parent进行左单旋,再把parent变黑grandfather变红

 

双旋+变色

单旋+变色的情况都是在cur和parent偏向同一边的情况下(同在左或同在右),那如果cur和parent不在同一边怎么办?这时候就要用双旋+变色解决了。

1.parent是grandfather的左孩子cur是parent的右孩子,那么先对parent进行左单旋,再把cur变黑grandfather变红

 

 2.parent是grandfather的右孩子cur是parent的左孩子,那么先对parent进行左单旋,再把cur变黑grandfather变红

插入的完整代码

​
void RotateR(Node* parent)
{//subL为parent的左孩子节点Node* subL = parent->_left;//subLR为subL的右子节点Node* subLR = subL->_right;// 将parent与subLR节点进行链接parent->_left = subLR;//在SubLR的情况下更改,让其指向正确的父亲if (subLR)subLR->_parent = parent;//提前记录祖父节点Node* pParent = parent->_parent;//链接subL与parentsubL->_right = parent;parent->_parent = subL;//根据parent是否是根节点进行不同处理if (parent == _root){_root = subL;subL->_parent = nullptr;}else{//将pParent和subL链接//但得先判断parent是pParent的左节点还是右节点if (pParent->_left == parent)pParent->_left = subL;elsepParent->_right = subL;//修改subL的parent指针,让其指向正确的父亲subL->_parent = pParent;}}void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* pParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (pParent->_left == parent)pParent->_left = subR;elsepParent->_right = subR;subR->_parent = pParent;}}bool Insert(const pair<K, 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;}elsereturn false;}cur = new Node(kv);//非空树插入红色节点cur->_col = RED;//判断cur应该插入到parent的左节点还是右节点if (kv.first > parent->_kv.first)parent->_right = cur;elseparent->_left= cur;//链接父亲cur->_parent = parent;//父亲是红色节点,出现连续的红色节点,要处理while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//判断叔叔是grandfather的左节点还是右节点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不存在 或者 uncle存在且为黑{if (cur == parent->_left){//     g//   p    u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   p    u//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else if (parent == grandfather->_right){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不存在 或者 uncle存在且为黑{if (cur == parent->_right){//     g//   u   p//        cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   u    p //      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//更新颜色时,_root的颜色可能会改变//当grandfather是_root时//    g        更新颜色时,parent和uncle会变黑//  p   u      grandfather会变红// c//所以必须加这句代码保证_root的颜色为黑。_root->_col = BLACK;return true;
}​

代码解释:

  • 向红黑树中插入一个key-value,如果是空树插入,则直接根据kv来new一个节点,然后赋值给_root,记得将根节点的颜色置为黑
  • 如果是非空树的插入,首先利用cur指针找到kv应该插入的位置,在此过程中也需要一个parent来记录cur的父亲找到位置后new节点赋值给cur置节点颜色为红,这个时候还不能直接链接cur与parent,得先判断插入parent的左边还是右边,插入后记得修改cur的_parent指针
  • 接着就该判断插入节点cur与parent的颜色有没有发生冲突,如果parent的颜色是红色,那么就需要进行处理,可以说处理颜色冲突是红黑树插入的最重要操作。
  • 首先得用grandfather来记录parent的父亲,然后得判断parent是grandfather的左节点还是右节点从而知道uncle节点的具体位置,这里就假设parent是grandfather的左节点,那么uncle就是右节点,由于uncle是左节点的情况是相对的,所以我们只需要讨论一种情况即可。
  • 若uncle存在且为红,那么将parent和uncle的颜色置黑grandfather的颜色置红,然后将cur移动到grandfather,重新记录parent,继续向上更新颜色。
  • 继续更新颜色导致了uncle存在或者uncle存在且为黑的情况,分场景触发单旋+变色或双旋+变色,如果cur是parent的左节点就是parent和cur相较于grandfather偏向左边,左单旋+变色处理cur是右边,左右双旋+变色。
  • 注意触发单旋+变色或双旋+变色后cur已经变成parent和grandfather的父亲了记得break出循环,因为这时候以cur为根节点的子树已经是合法的红黑树继续向上循环的话cur就会变色了,你的处理就白忙活了。

红黑树的查找

跟二叉搜索树一样,不过多叙述。

Node* Find(const K& key)
{Node* cur = _root;while (cur){if (key > cur->_kv.first)cur = cur->_right;else if (key < cur->_kv.first)cur = cur->_left;elsereturn cur;}return nullptr;
}

红黑树的验证

对于红黑树的验证,只需要验证4条颜色规则就行了,这样就保证了最长路径1不超过最短路径的2倍。

  • 规则1枚举颜色类型,天然实现保证了颜色不是黑色就是红色。
  • 规则2根节点是否为黑色直接检查根即可
  • 规则3前序遍历检查,遇到红色结点查孩子不太方便,因为孩子有两个,且不⼀定存在,反过来检查父亲的颜色是否为红就方便多了。
  • 规则4前序遍历,遍历过程中用形参记录跟到当前结点的blackNum(黑色结点数量),前序遍历遇到黑色结点就++blackNum,走到空就计算出了⼀条路径的黑色结点数量。将其作为任意⼀条路径黑色结点数量的参考值,依次比较即可。
bool Check(Node* root, int blackNum, int refNum)
{if (root == nullptr){//检查是否与参考值相等if (refNum != blackNum){cout << "存在黑色结点的数量不相等的路径" << endl;return false;}return true;}//出现连续的红色节点返回falseif (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色结点" << endl;return false;}//遇到黑色节点,blackNum++if (root->_col == BLACK)blackNum++;return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}bool IsRBTree()
{//空树也是REBTreeif (_root == nullptr)return true;if (_root->_col == RED)return false;//黑色节点的参考值int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++refNum;cur = cur->_left;}return Check(_root, 0, refNum);
}

红黑树的测试

void test_RBTree1()
{RBTree<int, int> t;//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//双旋测试用例int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert({ e, e });}//中序遍历t.InOrder();cout << t.IsRBTree() << endl;
}

随机数测试

void test_RBTree2()
{srand((unsigned int)time(0));int N = 10000000;vector<int> v(N);v.reserve(N);for (int i = 0; i < N; ++i){v.push_back(rand() + i);}size_t begin = clock();RBTree<int, int> t;for (auto e : v){t.Insert({ e, e });}size_t end = clock();cout << "Insert: " << end - begin << "ms" << endl;cout << t.IsRBTree() << endl;
}


 拜拜,下期再见😏

摸鱼ing😴✨🎞

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com