赞
踩
在本篇博客中,作者将会带领你使用C++来实现一棵红黑树,此红黑树的实现是基于二叉搜索树和AVLTree一块来讲的,所以在看本篇博客之前,你可以先看看下面这两篇博客
在这棵红黑树中,我们用到了二叉搜索树的插入规则和AVLTree的旋转,所以在本篇博客中,在旋转部分可以直接看AVLTree的博客。
目录
cur为红,cur_parent为红,grandparent为黑,uncle为红
cur为红,cur_parent为红,grandparent为黑,uncle为黑\uncle不存在
红黑树是一棵二叉搜索树,它的结点不是黑的就是红的,其中它有一个非常重要的特点:
通过对任何一条从根到叶子的路径上各个结点的着色控制,保证了红黑树没有一条路径会比最短路径长出两倍,达到接近平衡的特点。
看到这句话,可能你还云里雾里的,但是不要怕,简单的来说,红黑树的特点就是:找出树中最短的路径和最长的路径,其中这条最长路径的长度不会大于最短路径长度的两倍。
如下图所示:
在这棵红黑树中,最短的路径是最左边的那条,长度为3,最长的路径是最右边的那条,长度为4,即4 < 2*3,最长的路径不会大于最短路径的两倍。
那么红黑树是怎么做到上面的这个特点的呢?
那是因为红黑树需要遵循下面这5条性质:
1.每个结点不是红的就是黑的
2.根节点是黑色的
3.如果一个结点是红色的,那么它的两个孩子一定是黑色的
4.对于每个结点,从该结点到其所有后代叶结点的路径上,均包含相同数量的黑色结点
5.每个叶子结点都是黑色的(此处的我叶子结点指的是空结点)
对于这5条性质来说,可能有一些很难理解,但是不用怕,我们来解释一下。
对于1、2这两条性质来说,很好理解就字面意思,这里就不做过多的解释,其中最重要的是3、4这两条性质,在下面的红黑树插入讲解中,我们都将会围绕着3、4这两条性质来进行。
3.如果一个结点是红色的,那么它的两个孩子一定是黑色的。
其实这个也很好理解,但是这个很重要。其规则如下图所示。
4.对于每个结点,从该结点到其所有后代叶结点的路径上,均包含相同数量的黑色结点。
这条规则说的是,从任意一个结点开始,一直往下走,走遍所有可能,这其中会有很多条可能的路径,但是这些路径都有一个特点,就是每条路径上的黑色结点的个数相同。如下图所示。
5.每个叶子结点都是黑色的(这里的叶子结点指的是空结点),如下图所示。 但是其实这个并不是那么重要,理解就行了。
那么为什么只要遵循上面这五条性质,就能做到红黑树的特点的呢?红黑树的特点是,最长路径的长度不会大于最短路径的长度的两倍。
既然红黑树的特点与最短路径和最长路径有关,那么我们来把这两条路径分析一下。
最短路径:通过这五条性质,我们可以知道在一棵红黑树中,最短路径上,一定全是黑结点。不会再有情况比这种情况要短了。
最长路径: 对于最长路径来说,由于有性质4,所以在最长路径上,它的黑色结点的个数一定和最短路径的黑色结点个数相同。又由于有性质3,对于最长的路径来说,它一定是黑结点,红结点交替的。所以最长的路径的长度不会大于最短路径的两倍。
如下图所示
知道了红黑树的性质和特点,接下来我们可以来实现一棵红黑树了。
在定义红黑树的结点时,与普通的树结点不同的是,这里多了一个_parent指针和一个记录结点颜色的变量。
- enum Color
- {
- BLACK,
- RED
- };
-
- template<class T>
- struct TreeNode
- {
- //成员变量
- T _data;//数据
- TreeNode<T>* _left;
- TreeNode<T>* _right;
- TreeNode<T>* _parent;
- Color _col;//保存结点的颜色
-
- //构造函数
- TreeNode(const T& data)
- :_data(data)
- ,_left(nullptr)
- ,_right(nullptr)
- ,_parent(nullptr)
- ,_col(RED)//每生成一个新结点,都将结点的颜色默认给红色,至于为什么,后面会解释
- {}
- };
对于红黑树类的定义,我们先简单的给出一个构造函数,并将_root根结点赋值为nullptr即可。
- template<class T>
- class RBTree
- {
- typedef TreeNode<T> Node;
- public:
- //构造函数
- RBTree()
- :_root(nullptr)//给根结点一个nullptr
- {}
-
- private:
- Node* _root;
- };
接下来就是最重要的部分了,红黑树的插入,对于红黑树的插入,我们可以分为两个过程:
1.先按二叉搜索树的插入规则把新结点插入进去先。
2.插入新结点后,判断红黑树的性质有没有被破坏,如果没有被破坏,则插入直接结束,如果有被破坏,则进行调整处理。
由于插入结点的函数有点长,所以这里把插入函数分开来实现 。下面是函数的名称以及参数
bool insert(const T& data)
二叉搜索树的插入规则就是,先不管三七二十一,先把新结点插入进去再说。
对于二叉搜索树的插入规则,这里不在多讲,不是很理解的,可以看下面这篇博客,这里面讲到了二叉搜索树的插入实现。我们在这里直接给出代码。
- //如果树为NULL,则直接将新结点给到_root
- if (_root == nullptr)
- {
- _root = new Node(data);
- _root->_col = BLACK;//把新结点给_root后,要记得把颜色给位BLACK
- return true;
- }
-
- Node* cur = _root;
- Node* cur_parent = nullptr;
- while (cur != nullptr)
- {
- if (data > cur->_data)
- {
- cur_parent = cur;
- cur = cur->_right;
- }
- else if (data < cur->_data)
- {
- cur_parent = cur;
- cur = cur->_left;
- }
- else//说明该值已经存在,不进行插入
- {
- return false;
- }
- }
-
- //将新结点插入
- Node* newnode = new Node(data);
- if (cur_parent->_data > data)
- {
- cur_parent->_left = cur;
- cur->_parent = cur_parent;
- }
- else
- {
- cur_parent->_right = cur;
- cur->_parent = cur_parent;
- }
当插入完结点后,就要判断红黑树的性质是否被破坏,如没有,则插入结束,如果有,则进行调整处理。
对于前者没有什么好讨论的,我们在着重于讨论后者。
红黑树的性质:
1.每个结点不是红的就是黑的
2.根节点是黑色的
3.如果一个结点是红色的,那么它的两个孩子一定是黑色的
4.对于每个结点,从该结点到其所有后代叶结点的路径上,均包含相同数量的黑色结点
5.每个叶子结点都是黑色的(此处的我叶子结点指的是空结点)
首先我们来思考一个问题,如果新增了一个结点,你希望这个新增的结点是红色的还是黑色的呢?
其实我们希望这个新增的结点是红色的,为什么,我们来从红黑树的性质来分析。
当我们新插入一个结点的时候,性质1、2、5是绝对不会被破坏的,这应该很好理解。
被破坏的只有3或者4,当我们插入一个红结点,有可能会破坏性质3,当我们插入一个黑结点,会破坏性质4,如下图所示。
既然不管插入的是红结点还是黑结点,都会破坏红黑树的性质,那么为什么我们要选择插入红结点呢?
其实大家凭感觉来判断,应该都会感觉性质3的破坏更好的调整,而性质4的破坏不好调整,因为对于性质4的破坏,我们去给其他路径新增黑结点显然不合理,所以只有给当前路径减少一个黑结点来解决,那么我们把这个新增的结点给成红色即可。
既然这里已经确定了新增的结点一定为红色,所以对于红黑树的调整,我们都围绕着这个来讲解。
对于性质3的破坏,我们可以分为下面着三种情况。
上图是其中的一种插入的情况,其中cur刚好是叶子,但是cur也有可能不是叶子,所以我们可以给出这种情况的抽象图。
对于这种情况,我们的调整过程是这样的:
把cur_parent和uncle的颜色变为黑色,grandparent的颜色变为红色。如下图所示。
但是这样的处理后,还会有可能会发生性质破坏,例如grandparent的父结点还是红色,对于这样的情况,我们只需要把grandparent给cur,继续向上处理即可。如下图所示。
在这种情况中,又可以分为两种小情况,一种是uncle存在且为黑,一种是uncle不存在。
先来说说第一种情况,uncle不存在的情况,我们先来看图。
对于这种情况来说,cur一定是新插入的结点,因为如果cur不是新插入的结点,那么说明是由情况一调整而来的,那么既然是从情况一调整而来的,那么cur的孩子肯定是黑色,但是这样就不符合性质4:从任意结点开始,每条路径的黑色结点的数量相同。
接着第二种情况,uncle存在且为黑色,我们先来看图。
对于这种情况来说,cur一定不是新插入的结点,因为如果cur是新插入的结点,那么在插入cur之前,这棵红黑树违反了性质4:从任意结点开始,每条路径的黑色结点的个数相同。
基于这两种情况,我们可以给出这它们的抽象图,同时它们的调整方法是一样的。
对于情况二,我们的处理是对grandparent进行一个右单旋,后调整cur_parent和grandparent的颜色即可。如下图所示。
情况三看上去与情况二类似,其实可以说是,也可以说不是,首先同样的,情况三也可以分为两种情况,一种是uncle不存在,一种是uncle存在且为黑色。
我们直接来看图。
也情况二不同的是,它是一个折线。同样的如果uncle不存在,那么cur一定是新插入的结点。
同样的,我们直接来看图。
对于这种情况来说,cur一定不是新插入的结点,它是由情况一调整过来的
基于这两种情况,我们可以给出它的抽象图处理,如下图所示。
对于情况三,我们的处理是,先对cur_parent进行一个左单旋,左单旋后,要交换cur和cur_parent,后再对grandparent进行一个右单旋,最后再调整颜色,如下图所示。
走到这里,我们所有的情况都已经讲完了,接下来可以编写我们的调整代码了。
注意,我们上面讲到的三种情况没有覆盖到全部情况,因为还有另外三种情况是上面这三种情况的反方向,如情况一的反方向,如下图所示。
同样的情况二和情况三也有它们的反方向,这里就不在多讲了,逻辑都是一样的。接下来我们可以来编写我们的调整代码了,我们的调整代码可以分为如上图所示的正反向和反方向来编写。
- //调整结点代码
- while (cur_parent != nullptr && cur_parent->_col == RED)
- {
- Node* grandparent = cur_parent->_parent;
- if (grandparent->_left == cur_parent)//正方向
- {
- Node* uncle = grandparent->_right;
- if (uncle != nullptr && uncle->_col == RED)//情况一,uncle存在且为红
- {
- cur_parent->_col = uncle->_col = BLACK;
- grandparent->_col = RED;
- //继续向上处理
- cur = grandparent;
- cur_parent = cur->_parent;
- }
- else//情况二和情况三
- {
- //这里情况三经过第一次旋转后可以变成情况二,所以可以先判断是否是情况三
- if (cur_parent->_right == cur)//这种情况就是情况三
- {
- //先进行一个左单旋
- RotateL(cur_parent);
- swap(cur, cur_parent);//这里一定要进行交换,不然如果是情况二的,会出现逻辑错误
- }
- //代码走到这里就一定是情况二了
- RotateR(grandparent);
- cur_parent->_col = BLACK;
- grandparent->_col = RED;
- break;
- }
- }
- else if (grandparent->_right == cur_parent)//反方向
- {
- Node* uncle = grandparent->_left;
- if (uncle != nullptr && uncle->_col == RED)//反方向的情况一
- {
- cur_parent->_col = uncle->_col = BLACK;
- grandparent->_col = RED;
-
- cur = grandparent;
- cur_parent = cur->_parent;
- }
- else//反方向的情况二和情况三
- {
- if (cur_parent->_left == cur)
- {
- RotateR(cur_parent);
- swap(cur, cur_parent);
- }
- RotateL(grandparent);
- cur_parent->_col = BLACK;
- grandparent->_col = RED;
- break;
- }
- }
- }
- _root->_col = BLACK;
- //插入结点
- bool insert(const T& data)
- {
- //如果树为NULL,则直接将新结点给到_root
- if (_root == nullptr)
- {
- _root = new Node(data);
- _root->_col = BLACK;//把新结点给_root后,要记得把颜色给位BLACK
- return true;
- }
-
- Node* cur = _root;
- Node* cur_parent = nullptr;
- while (cur != nullptr)
- {
- if (data > cur->_data)
- {
- cur_parent = cur;
- cur = cur->_right;
- }
- else if (data < cur->_data)
- {
- cur_parent = cur;
- cur = cur->_left;
- }
- else//说明该值已经存在,不进行插入
- {
- return false;
- }
- }
-
- //将新结点插入
- cur = new Node(data);
- if (cur_parent->_data > data)
- {
- cur_parent->_left = cur;
- cur->_parent = cur_parent;
- }
- else
- {
- cur_parent->_right = cur;
- cur->_parent = cur_parent;
- }
-
- //调整结点代码
- while (cur_parent != nullptr && cur_parent->_col == RED)
- {
- Node* grandparent = cur_parent->_parent;
- if (grandparent->_left == cur_parent)//正方向
- {
- Node* uncle = grandparent->_right;
- if (uncle != nullptr && uncle->_col == RED)//情况一,uncle存在且为红
- {
- cur_parent->_col = uncle->_col = BLACK;
- grandparent->_col = RED;
- //继续向上处理
- cur = grandparent;
- cur_parent = cur->_parent;
- }
- else//情况二和情况三
- {
- //这里情况三经过第一次旋转后可以变成情况二,所以可以先判断是否是情况三
- if (cur_parent->_right == cur)//这种情况就是情况三
- {
- //先进行一个左单旋
- RotateL(cur_parent);
- swap(cur, cur_parent);
- }
- //代码走到这里就一定是情况二了
- RotateR(grandparent);
- cur_parent->_col = BLACK;
- grandparent->_col = RED;
- break;
- }
- }
- else if (grandparent->_right == cur_parent)//反方向
- {
- Node* uncle = grandparent->_left;
- if (uncle != nullptr && uncle->_col == RED)//反方向的情况一
- {
- cur_parent->_col = uncle->_col = BLACK;
- grandparent->_col = RED;
-
- cur = grandparent;
- cur_parent = cur->_parent;
- }
- else//反方向的情况二和情况三
- {
- if (cur_parent->_left == cur)
- {
- RotateR(cur_parent);
- swap(cur, cur_parent);
- }
- RotateL(grandparent);
- cur_parent->_col = BLACK;
- grandparent->_col = RED;
- break;
- }
- }
- }
- _root->_col = BLACK;
- }
在我们的插入函数的调整部分中,有下面这段逻辑
- //调整结点代码
- while (cur_parent != nullptr && cur_parent->_col == RED)
- {
- Node* grandparent = cur_parent->_parent;
- if (grandparent->_left == cur_parent)//正方向
- {
-
-
- }
有的人可能会有个疑问,就是在这里的grandparent指针中,没有进行做判空处理,不会出现grandparent是个空指针的错误吗?
答案是不会的,原因如下:
首先我们可以确定的是,cur和cur_parent指针不会是空指针,不然这个while循环也不会进入,且进去这个循环后,cur和cur_parent结点的颜色一定为红色。那么既然cur_parent为红色,那么cur_parent就一定不是根结点,因为在红黑树的性质中,根结点一定是黑色的,但是这个时候cur_parent是红色的,说明cur_parent一定有父结点,所以不会出现grandparent为空指针的情况。
红黑树的查找就比较简单了,就是普通的二叉搜索树的查找方式,这里就不在多解释,不了解的可以去看前面的二叉搜索树的博客。
-
- //查找结点
- Node* find(const T& data)
- {
- Node* cur = _root;
- if (data > cur->_data)
- {
- cur = cur->_right;
- }
- else if (data < cur->_data)
- {
- cur = cur->_left;
- }
- else
- {
- return cur;
- }
- return nullptr;
- }
不是所有红黑树的结点都是可以修改的,只有<key,value>模型的红黑树才能修改,例如STL中的map,而key模型的红黑树是不能修改的,例如STL中的set,我们这里默认实现的是key模型的红黑树,所以在这里是不能修改的,但是如果想要做到修改,可以把这棵红黑树改成<key,value>模型即可,即在TreeNode结构体中,多加一个参数即可。
看到这里,我们的这棵红黑树除了删除都已经搞定了,那么我们如果判断我们写的代码是对的呢?即我们写的这棵红黑树到底是不是红黑树,判断这棵树是不是红黑树的方法就是用红黑树的性质去检查它即可。
首先,我们再来看一下红黑树的五条性质:
1.每个结点不是红的就是黑的
2.根节点是黑色的
3.如果一个结点是红色的,那么它的两个孩子一定是黑色的
4.对于每个结点,从该结点到其所有后代叶结点的路径上,均包含相同数量的黑色结点
5.每个叶子结点都是黑色的(此处的我叶子结点指的是空结点)
通过下面这个代码,可以测试一个红黑树是否正确。
- //判断是否符合红黑树的性质
- bool JudgeTree()
- {
- //空树也是红黑树
- if (_root == nullptr)
- {
- return true;
- }
- //性质1:树结点不是红的就是黑的
- //这条性质就没必要检查的了
-
- //性质2:根结点一定是黑色的
- if (_root->_col != BLACK)
- {
- cout << "违反性质2:根结点一定是黑色的" << endl;
- return false;
- }
-
- //性质5:所有叶子结点都是黑色的
- //这个性质也没必要检查
-
- size_t blackcount = 0;
- Node* cur = _root;
- while (cur != nullptr)//先求出一条路径中的黑色结点的个数
- {
- if (cur->_col == BLACK)
- {
- blackcount++;
- }
- cur = cur->_left;
- }
- size_t k = 0;//用来存储黑色结点的个数
- return _JudgeTree(_root, k, blackcount);//判断性质3和性质4
-
- //性质3:如果一个结点是红色的,那么它的孩子一定是黑色的
- //性质4:每条路径上的黑色结点的个数都相同
- }
-
- //判断是否红黑树的子函数
- bool _JudgeTree(Node* root, size_t k, size_t blackcount)
- {
- //当root走到NULL的时候,判断这条路径的黑色结点个数是否==blackcount
- if (root == nullptr)
- {
- if (k == blackcount)
- {
- return true;
- }
- else
- {
- cout << "违反性质4:每条路径上的黑结点个数相同" << endl;
- return false;
- }
- }
-
- //如果结点是红色的,判断它的父结点是否也为红色
- Node* root_parent = root->_parent;
- if (root_parent != nullptr && root->_col == RED)
- {
- if (root_parent->_col == RED)
- {
- cout << "违反性质3:如果一个结点是红色的,那么它的孩子一定是黑色的" << endl;
- return false;
- }
- }
-
- //如果结点是黑色的,则k++
- if (root->_col == BLACK)
- {
- k++;
- }
-
- return _JudgeTree(root->_left, k, blackcount) && _JudgeTree(root->_right, k, blackcount);
- }
- #pragma once
- #include<iostream>
- #include<time.h>
- using namespace std;
- namespace blog_RBTree
- {
- enum Color
- {
- BLACK,
- RED
- };
-
- template<class T>
- struct TreeNode
- {
- //成员变量
- T _data;//数据
- TreeNode<T>* _left;
- TreeNode<T>* _right;
- TreeNode<T>* _parent;
- Color _col;//保存结点的颜色
-
- //构造函数
- TreeNode(const T& data)
- :_data(data)
- ,_left(nullptr)
- ,_right(nullptr)
- ,_parent(nullptr)
- ,_col(RED)//每生成一个新结点,都将结点的颜色默认给红色,至于为什么,后面会解释
- {}
- };
-
- template<class T>
- class RBTree
- {
- typedef TreeNode<T> Node;
- public:
- //构造函数
- RBTree()
- :_root(nullptr)//给根结点一个nullptr
- {}
-
- //插入结点
- bool insert(const T& data)
- {
- //如果树为NULL,则直接将新结点给到_root
- if (_root == nullptr)
- {
- _root = new Node(data);
- _root->_col = BLACK;//把新结点给_root后,要记得把颜色给位BLACK
- return true;
- }
-
- Node* cur = _root;
- Node* cur_parent = nullptr;
- while (cur != nullptr)
- {
- if (data > cur->_data)
- {
- cur_parent = cur;
- cur = cur->_right;
- }
- else if (data < cur->_data)
- {
- cur_parent = cur;
- cur = cur->_left;
- }
- else//说明该值已经存在,不进行插入
- {
- return false;
- }
- }
-
- //将新结点插入
- cur = new Node(data);
- if (cur_parent->_data > data)
- {
- cur_parent->_left = cur;
- cur->_parent = cur_parent;
- }
- else
- {
- cur_parent->_right = cur;
- cur->_parent = cur_parent;
- }
-
- //调整结点代码
- while (cur_parent != nullptr && cur_parent->_col == RED)
- {
- Node* grandparent = cur_parent->_parent;
- if (grandparent->_left == cur_parent)//正方向
- {
- Node* uncle = grandparent->_right;
- if (uncle != nullptr && uncle->_col == RED)//情况一,uncle存在且为红
- {
- cur_parent->_col = uncle->_col = BLACK;
- grandparent->_col = RED;
- //继续向上处理
- cur = grandparent;
- cur_parent = cur->_parent;
- }
- else//情况二和情况三
- {
- //这里情况三经过第一次旋转后可以变成情况二,所以可以先判断是否是情况三
- if (cur_parent->_right == cur)//这种情况就是情况三
- {
- //先进行一个左单旋
- RotateL(cur_parent);
- swap(cur, cur_parent);
- }
- //代码走到这里就一定是情况二了
- RotateR(grandparent);
- cur_parent->_col = BLACK;
- grandparent->_col = RED;
- break;
- }
- }
- else if (grandparent->_right == cur_parent)//反方向
- {
- Node* uncle = grandparent->_left;
- if (uncle != nullptr && uncle->_col == RED)//反方向的情况一
- {
- cur_parent->_col = uncle->_col = BLACK;
- grandparent->_col = RED;
-
- cur = grandparent;
- cur_parent = cur->_parent;
- }
- else//反方向的情况二和情况三
- {
- if (cur_parent->_left == cur)
- {
- RotateR(cur_parent);
- swap(cur, cur_parent);
- }
- RotateL(grandparent);
- cur_parent->_col = BLACK;
- grandparent->_col = RED;
- break;
- }
- }
- }
- _root->_col = BLACK;
- }
-
- //查找结点
- Node* find(const T& data)
- {
- Node* cur = _root;
- if (data > cur->_data)
- {
- cur = cur->_right;
- }
- else if (data < cur->_data)
- {
- cur = cur->_left;
- }
- else
- {
- return cur;
- }
- return nullptr;
- }
-
- //判断是否符合红黑树的性质
- bool JudgeTree()
- {
- //空树也是红黑树
- if (_root == nullptr)
- {
- return true;
- }
- //性质1:树结点不是红的就是黑的
- //这条性质就没必要检查的了
-
- //性质2:根结点一定是黑色的
- if (_root->_col != BLACK)
- {
- cout << "违反性质2:根结点一定是黑色的" << endl;
- return false;
- }
-
- //性质5:所有叶子结点都是黑色的
- //这个性质也没必要检查
-
- size_t blackcount = 0;
- Node* cur = _root;
- while (cur != nullptr)//先求出一条路径中的黑色结点的个数
- {
- if (cur->_col == BLACK)
- {
- blackcount++;
- }
- cur = cur->_left;
- }
- size_t k = 0;//用来存储黑色结点的个数
- return _JudgeTree(_root, k, blackcount);//判断性质3和性质4
-
- //性质3:如果一个结点是红色的,那么它的孩子一定是黑色的
- //性质4:每条路径上的黑色结点的个数都相同
- }
-
- private:
- //左单旋
- void RotateL(Node* cur_parent)
- {
- Node* cur = cur_parent->_right;
- Node* cur_left = cur->_left;
-
- //改变指针的链接关系
- cur_parent->_right = cur_left;
- if (cur_left != nullptr)
- {
- cur_left->_parent = cur_parent;
- }
-
- cur->_left = cur_parent;
- Node* cur_parent_parent = cur_parent->_parent;
- cur_parent->_parent = cur;
-
- //旋转完成后要判断cur_parent是否为根
- if (cur_parent_parent != nullptr)//说明cur_parent不是根
- {
- if (cur_parent_parent->_data < cur_parent->_data)
- {
- cur_parent_parent->_right = cur;
- cur->_parent = cur_parent_parent;
- }
- else
- {
- cur_parent_parent->_left = cur;
- cur->_parent = cur_parent_parent;
- }
- }
- else//说明cur_parent是根
- {
- _root = cur;
- cur->_parent = nullptr;
- }
-
- }
-
- //右单旋
- void RotateR(Node* cur_parent)
- {
- Node* cur = cur_parent->_left;
- Node* cur_right = cur->_right;
-
- cur_parent->_left = cur_right;
- if (cur_right != nullptr)
- {
- cur_right->_parent = cur_parent;
- }
-
- cur->_right = cur_parent;
- Node* cur_parent_parent = cur_parent->_parent;
- cur_parent->_parent = cur;
-
- if (cur_parent_parent != nullptr)
- {
- if (cur_parent_parent->_data > cur_parent->_data)
- {
- cur_parent_parent->_left = cur;
- cur->_parent = cur_parent_parent;
- }
- else
- {
- cur_parent_parent->_right = cur;
- cur->_parent = cur_parent_parent;
- }
- }
- else
- {
- _root = cur;
- cur->_parent = nullptr;
- }
-
- }
-
- //获取根节点
- Node* GetRoot()
- {
- return _root;
- }
-
- //判断是否红黑树的子函数
- bool _JudgeTree(Node* root, size_t k, size_t blackcount)
- {
- //当root走到NULL的时候,判断这条路径的黑色结点个数是否==blackcount
- if (root == nullptr)
- {
- if (k == blackcount)
- {
- return true;
- }
- else
- {
- cout << "违反性质4:每条路径上的黑结点个数相同" << endl;
- return false;
- }
-
-
- }
-
- //如果结点是红色的,判断它的父结点是否也为红色
- Node* root_parent = root->_parent;
- if (root_parent != nullptr && root->_col == RED)
- {
- if (root_parent->_col == RED)
- {
- cout << "违反性质3:如果一个结点是红色的,那么它的孩子一定是黑色的" << endl;
- return false;
- }
- }
-
- //如果结点是黑色的,则k++
- if (root->_col == BLACK)
- {
- k++;
- }
-
- return _JudgeTree(root->_left, k, blackcount) && _JudgeTree(root->_right, k, blackcount);
- }
-
- private:
- Node* _root;
- };
-
- void Test1()
- {
- srand(time(0));
- RBTree<int> root;
- const int n = 10000;
- for (int i = 0; i < n; i++)
- {
- int input = rand();
- root.insert(input);
- }
- cout << root.JudgeTree() << endl;
- }
- }
- #include"blog_RBTree.h"
-
- int main()
- {
- blog_RBTree::Test1();
-
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。