devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

二叉搜索树、AVL树、红黑树底层源码以及迭代器模拟实现，map/set的封装

作者：Monodyee | 2024-05-14 17:27:45

赞

踩

二叉搜索树、AVL树、红黑树底层源码以及迭代器模拟实现，map/set的封装

这次给大家分享的还是关于二叉树部分的内容，之前的文章已经分享过一些二叉树的基础知识，如果不了解的朋友可以看看：二叉树以及堆和堆排序。普通的二叉树其实是没有什么实际的应用价值的，而map和set大家用过或者听过吗？这是不管C++还是java等高级编程语言都有的数据结构。所以重要性不言而喻，而map/set的底层存储结构就是一颗二叉树，但是可不是简单的二叉树那么简单，至于其中奥妙需要我们共同去学习。

话不多说我们继续往下看。

树

二叉搜索树

二叉搜索树的概念：

	二叉搜索树也成为二叉排序树，或者是一颗空树，如果不为空树拥有以下特性。

  • 1
  • 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
  • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
  • 它的左右子树也分别为二叉搜索树。

在这里插入图片描述
这棵树就满足二叉搜索树的特性，左子树所有的节点都小于根节点，右子树所有的节点都大于根节点，如果中序遍历这颗搜索树，你就会发现，数据是升序序列。

这就是一颗树结点的定义。

	template <class K>
	struct BSTreeNode {
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _right;
		K _key;
	public:
		BSTreeNode(const K& key)
			:_key(key)
			, _left(nullptr)
			, _right(nullptr)
		{}
	};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

搜索二叉树的插入

插入其实非常简单，往一颗二叉树里面插入一个值，如果比根节点大，就往右子树走，比根节点小，就往左子树遍历。

bool Insert(const K& key) {
			if (_root == nullptr) { //如果根节点为空，树就为空，这个新插入的值就是根节点
				_root = new Node(key);
				return true;
			}
			else {
				Node* parent = nullptr;//需要记录父节点,让新插入的节点链接到父结点上。
				Node* cur = _root;
				while (cur) {
					if (cur->_key < key) {	//如果比根节点大,需要走右子树
						//需要更新父节点，让父节点跟着cur往下找。
						parent = cur;
						cur = cur->_right;
					}
					else if (cur->_key > key) { //如果比根节点小,需要走左子树
						parent = cur;
						cur = cur->_left;
					}
					else { //如果不大不小证明，这个值的节点已经存在了，不需要插入了，返回false;
						return false;
					}
				}
				//从循环出来证明，cur为空，已经走到了合适的位置。直接申请一个节点空间
				cur = new Node(key);
				//还需要让父节点指向它,如果比父节点大，让右指针指向它,否者左指针指向它。
				if (parent->_key < key) {
					parent->_right = cur;
				}
				else {
					parent->_left = cur;
				}
				return true;
			}
		}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

二叉搜索树的查找

查找也是非常简单，我就不做过多的说明了，如果有细心的朋友会发现在插入里面其实就包含查找的代码和说明

	bool Find(const K& key) {
		Node* cur = _root;
		while (cur) {
			if (cur->_key < key) {
				cur = cur->_right;
			}
			else if (cur->_key > key) {
				cur = cur->_left;
			}
			else {
				return true;
			}
		}
		return false;
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

二叉搜索树的删除

对比插入和查找，其实删除才是有点难度的，如果面试的话，也只会考察删除，所以是学习的重点。

二叉搜索树删除一个节点有三种情况是需要被处理的：
在这里插入图片描述

三种情况的处理方法：

  • 情况一：把右子树的节点给了父节点，至于给父的左还是右，需要判断cur是父的左还是右。
  • 情况二：把左子树的节点给了父节点。
  • 情况三：找左子树的最大节点或者右子树的最小节点替代当前节点，上图的cur，可以当它是根节点，也可以当它是树的子树。

在这里插入图片描述
这就是删除的三种情况，已经详细的给大家介绍了解决方法，我们可以看看代码是如何控制实现的。

bool Erase(const K& key) {
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur) {
				if (cur->_key < key) { 
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key) {
					parent = cur;
					cur = cur->_left;
				}
				else { //找到要删除的节点
					//情况一:左为空
					if (cur->_left == nullptr) {
						//需要判断是不是根节点，根节点的parent为空
						if (cur == _root) {
							_root = cur->_right;
						}
						else {
							//如果是父节点的左就把右子树给了父节点的左，否则给父节点的右。
							if (parent->_left == cur) {
								parent->_left = cur->_right;
							}
							else {
								parent->_right = cur->_right;
							}
						}
						delete cur;
					}//情况二:右为空
					else if (cur->_right == nullptr)
					{
						if (cur == _root) {
							_root = cur->_left;
						}
						else {
							//如果是父节点的左就把左子树给了父节点的左，否则给父节点的右。
							if (parent->_left == cur) {
								parent->_left = cur->_left;
							}
							else {
								parent->_right = cur->_left;
							}
						}
						delete cur;
					}
					else { //情况三: 左子树和右子树都不为空
					
						Node* pminRight = cur;
						Node* minRight = cur->_right;//右子树最小节点存储
						
						//寻找右子树最小节点
						while (minRight->_left) {
							pminRight = minRight;//记录右子树最小节点的父节点
							minRight = minRight->_left;
						}
						
						//把右子树最小节点的值给了cur
						cur->_key = minRight->_key;
						
						//右子树最小节点代表左子树一定为空，右子树可能存在，需要处理。如果右子树最小节点是父节点的左就把右子树最小节点的右子树给了父节点的左，否则给父节点的右。
						if (pminRight->_left == minRight) {

							pminRight->_left = minRight->_right;
						}
						else {
							pminRight->_right = minRight->_right;
						}
						delete minRight;
					}
					return true;
				}
			}
			return false;
		}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75

这就是普通的搜索二叉树，如果核心逻辑和代码实现已经讲清楚了，如果想要所有的源代码，可以在我的gitee上下载：二叉搜索树源码

AVL树

上面介绍了普通的二叉搜索树，看起来它的查找效率好像是log2n，但是真的是这样吗？我们可以看看下面这张图。他已经变成了一颗歪脖子树，插入、删除、查找都和一个链表一样，这就失去了它的价值。针对于这种情况，AVL树可以很好的解决它。
在这里插入图片描述

AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

  • 它的左右子树都是AVL树。
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)。

就是树的每个节点都有一个平衡因子，0代表左子树和右子树的高度相同，1代表右子树比左子树高一个，-1代表右子树比左子树低一个（也可以是-1代表右子树比左子树高一个，1代表右子树比左子树低一个）。
在这里插入图片描述
AVL树节点代码定义

template<class K,class V>
class AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	int _bf;//平衡因子

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

AVL树是如何保证它的平衡性的呢？如果插入一个节点导致平衡性被破坏了要如何调整呢？我们继续往下看。

AVL树的插入

插入节点：

  1. 先按照二叉搜索树的规则将节点插入到AVL树中
  2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了AVL树。

调整平衡因子

Cur插入后，Parent的平衡因子一定需要调整，在插入之前，pParent的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：

  • 1
  1. 如果pParent的平衡因子为0，说明插入之前pParent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功。
  2. 如果pParent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更新成正负1，此时以pParent为根的树的高度增加，需要继续向上更新。
  3. 如果pParent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进行旋转处理。

旋转的四种情况：
左单旋
在这里插入图片描述
左单旋代码实现

void RotateL(Node* parent)
	{
		Node* RChild = parent->_right;
		Node* RChild_L = RChild->_left;

		parent->_right = RChild_L;
		if (RChild_L)
			RChild_L->_parent = parent;

		Node* grandparent = parent->_parent;
		RChild->_left = parent;
		parent->_parent = RChild;

		if (grandparent == nullptr)
		{
			_root = RChild;
			RChild->_parent = nullptr;
		}
		else {
			if (grandparent->_left == parent)
			{
				grandparent->_left = RChild;
			}
			else
			{
				grandparent->_right = RChild;

			}
			parent->_bf = RChild->_bf = 0;
		}

	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

右单旋
在这里插入图片描述

void RotateR(Node* parent)
	{
		Node* LChild = parent->_left;
		Node* LChild_R = LChild->_right;
		parent->_left = LChild_R;

		if (LChild_R)
			LChild_R->_parent = parent;

		Node* grandparent = parent->_parent;

		LChild->_right = parent;
		parent->_parent = LChild;
		if (grandparent == nullptr)
		{
			_root = LChild;
			_root->_parent = nullptr;
		}
		else 
		{
			if (grandparent->_left == parent)
			{
				grandparent->_left = LChild;
			}
			else
			{
				grandparent->_right = LChild;
			}
			LChild->_bf = parent->_bf = 0;
		}
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

左右双旋：先左单旋再有单旋
在这里插入图片描述

void RotateLR(Node* parent)
	{
		Node* LChild = parent->_left;
		Node* LChild_R = LChild->_right;
		int bf = LChild_R->_bf;

		RotateL(parent->_left);
		RotateR(parent);

		if (bf == 1)
		{
			parent->_bf = 0;
			LChild_R->_bf = 0;
			LChild->_bf = -1;
		}
		else if(bf == -1)
		{
			parent->_bf = 1;
			LChild_R->_bf = 0;
			LChild->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			LChild_R->_bf = 0;
			LChild->_bf = 0;

		}
		else {
			assert(false);
		}
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

右左双旋：先右单旋，再左单旋
在这里插入图片描述

void RotateRL(Node* parent) {
		Node* RChild = parent->_right;
		Node* RChild_L = RChild->_left;
		int bf = RChild_L->_bf;

		RotateR(RChild);
		RotateL(parent);

		if (bf == 1) {
			parent->_bf = -1;
			RChild_L->_bf = 0;
			RChild->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			RChild_L->_bf = 0;
			RChild->_bf = 1;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			RChild_L->_bf = 0;
			RChild->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

插入代码

bool Insert(const pair<K, V>& kv) {
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.frist < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.frist > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else {
				return false;
			}
		}

		cur = new Node(kv);
		while (parent) 
		{	
			//更新父节点平衡因子
			if (cur == parent->_right)
			{
				parent->_bf++;
			}
			else {
				parent->_bf--;
			}
			
			//更新完如果为1或者-1代表这颗树的高度增加了，需要继续向上更新祖宗节点的平衡因子
			if (parent->_bf == 1 || parent->_bf == -1)
			{
				//
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (parent->_bf == 0)	//更新完为0，代表高度没有变化，直接退出
			{
				break;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)//更新完之后变为-2或者2，需要旋转调整
			{
				//具体怎么旋转根据旋转之前的平衡因子判断
				if (parent->_bf == 2 && cur->_bf == 1) {
					RotateL(parent);//进行左单旋
				}
				else if (parent->_bf == -2 || cur->_bf == -1)
				{
					RotateR(parent); //进行右单旋
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);//左右双旋
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);//右左双旋
				}
				else {
					assert(false);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78

判断AVL树的平衡

AVL树对平衡性的要求是非常严格的，写完我们并不知道是否是真正保证了平衡性，所以需要代码验证。

bool IsBalance() {
	return _IsBlance(_root);
}
int Height() {
	_Height(_root);
}
//求一颗树的高度
int _Height(Node* root) {
		if (root == nullptr) {
			return 0;
		}
		int left = _Height(root->_left);
		int right = _Height(root->_right);
		if (right - left != root->_bf) {
			assert(false);
		}
		return left > right ? left + 1 : right + 1;
}
bool _IsBlance(Node* root) {
	if (root == nullptr) {
		return true;
	}
	int leftH = _Height(root->_left);//求左子树的高度
	int rightH = _Height(root->_right);//求右子树的高度

	return abs(leftH - rightH) < 2 && //保证这个节点的左右子树的绝对值小于2
		_IsBlance(root->_left) && 	//需要递归求证左右子树的子树高度差不大于2
		_IsBlance(root->_right);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

这就是AVL树的概念和基本操作，如果想要完整的源代码，可以在我的gitee上获取：AVL树

红黑树

学习了上面的AVL树，好像不管是插入数据还是查询，效率都变得极高，但是有一个缺点就是，对平衡新的要求很高，只要高度差一就需要立即调整，这就意味着他可能需要大量的调整，所以我们可以学习一下红黑树。红黑树是一个重头戏，红黑树可能有的人听过或者没听过，但是学习高级编程语言，红黑树几乎是必学，因为map和set的底层就是一颗红黑树。
在这里插入图片描述

红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

红黑树到底是如何通过两种颜色就控制路径的长度的呢？还需要了解一下红黑树的性质。
红黑树的性质：

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

通过上面几条性质，我们总结一下为什么红黑树最短路径不会超过最长路径的2倍。

根据性质3，我们可以看出来，一个红色节点的孩子节点必须是黑色节点，代表，一条路径不能有两个连续的红色节点。
根据性质4，每条路径的黑色节点必须都是一样的，也就代表如果这棵树的最短路径是全黑色节点，最长路径最长只能是一黑一红，因为不能连续的红色节点，每条路径的黑色节点必须是一样的。所以最长路径不会超过最短路径的二倍。

红黑树节点定义

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	Colour _col;
	RBTreeNode(const pair<K, V>& kv) 
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(RED) //新增节点默认为红色，方便处理
	{}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

红黑树的插入

想要从一个空树，通过插入变成一颗红黑树，究竟怎么实现的，需要进行哪些转换我们继续往下看：

红黑树的插入分为几种情况：

  1. 该树为空树，直接插入根结点的位置，违反性质2，把节点颜色有红改为黑即可。

  2. 插入节点cur的父节点P为黑色，不违反任何性质，无需做任何修改。
    在这里插入图片描述

  3. cur为红，Parent为红，（祖节点一定存在，且为黑）Uncle存在并且也为红，需要进行变色处理。
    在这里插入图片描述

  4. cur为红，parent为红，uncle为黑或者不存在，这两种情况都是一样的处理方式，需要先旋转再变色。旋转完不用继续往上更新。需要旋转的情况比较多，给大家列举几种代表性的，剩下的旋转方式和AVL树使一样的。旋转的代码直接服用AVL树的就可以。我就不重复贴了。
    在这里插入图片描述

在这里插入图片描述

最后根节点一定要变黑，至于更详细的变色情况，代码里面已经表达清楚了。

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;
			}
			else {
				return false;
			}
		}
		cur = new Node(kv);
		if (parent->_kv.first > kv.first) {
			parent->_left = cur;
		}
		else {
			parent->_right = cur;
		}
		cur->_parent = parent;
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			//uncle存在且为红，变色处理，并继续往上处理
			if (grandfather->_left == parent) { //父节点是祖父节点的左孩子
				Node* uncle = grandfather->_right;

				//如果叔叔存在且为红，变色处理，并继续往上处理
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else //叔叔不存在/叔叔存在且为黑
				{
					if (cur == parent->_left) //父节点是祖父节点的左孩子，cur是parent的左孩子只需要进行右单旋
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else	//父节点是祖父节点的左孩子，cur是parent的右孩子只需要进行左右双旋
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else //父节点是祖父节点的右孩子
			{
				Node* uncle = grandfather->_left;
				//如果叔叔节点存在且为红，往上更新
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else //叔叔节点不存在或者为黑，进行旋转处理
				{
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102

检查是否为红黑树

检查一颗树是否为红黑树，检查方式还是

	bool IsBlance()
	{	
		//根节点不能为红
		if (_root && _root->_col == RED)
		{
			cout << "根节点颜色是红色" << endl;
			return false;
		}

		int benchmark = 0;
		Node* cur = _root;
		//先查看其中一条路径的黑色节点，记录在benchmark里面
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				benchmark++;
			}
			cur = cur->_left;
		}
		return _Check(_root, 0, benchmark);
	}
	bool _Check(Node* root, int blackNum, int benchmark)
	{
		if (root == nullptr)
		{	
			//检查这条路径的黑色节点和benchmark是否相同，如果不相同说明不是红黑树
			if (benchmark != blackNum)
			{
				cout << "某条路径黑色节点的数量不相等" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == BLACK)
		{
			++blackNum;
		}
		if (root->_col == RED
			&& root->_parent
			&& root->_parent->_col == RED) //检查当前节点的节点颜色是否和父节点都是红色，如果是则不是红黑树
		{
			cout << "存在连续的节点" << endl;
			return false;
		}
		return _Check(root->_left, blackNum, benchmark)
			&& _Check(root->_right, blackNum, benchmark);
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

这就是如何从0到生成一颗红黑树以及它是如何维护的具体过程。想要具体的源码可以登录gitee查看：红黑树底层实现

set/map的封装和迭代器的实现

set和map底层都是一颗红黑树，但是set存储的是key，map存储的是key/value值，是不是需要为set和map各写一份红黑树吗？答案当然是不需要，我们可以借助模板参数进行封装

这是红黑树节点的定义，它只有一个模板参数，不管是存pair还是key都可以。

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;
	Colour _col;
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
这个红黑树源码太多了，所以我截去了一部分进行讲解，如果想要完整的源码，我一会把gitee链接贴到文章末尾。
我还是拿代码进行讲解，详情看代码注释讲解。

  • 1
  • 2
//模板参数改成了三个，其中第一个就是key，第二个参数set还是传key，如果是map就传入pair对象，第三个参数是比较大小方式
template<class K, class T ,class KeyOfT>
class RBTree
{
public:
	typedef  RBTreeNode<T> Node;
	typedef _RBTreeIterator<T, T&, T*> iterator;
	typedef _RBTreeIterator<T, const T&, const T*> const_iterator;
	iterator begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}
	iterator end()
	{
		return iterator(nullptr);
	}
	//返回pair对象，第二个bool值代表插入成功，成功true，失败false，第一个参数返回成功插入节点的迭代器，失败的话代表值存在，返回存在值的迭代器
	pair<iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root),true);
		}
		KeyOfT kot;
		Node* parent = nullptr;
		Node* cur = _root;

		while (cur)
		{
			if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(iterator(cur), false);
			}
		}
		cur = new Node(data);
		Node* newnode = cur;
		if (kot(parent->_data) > kot(data))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;

			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;

				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					grandfather = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else {
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return make_pair(iterator(newnode), true);
	}


private:
	Node* _root = nullptr;
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135

我们看看set是如何对RBTree进行封装的。

#pragma once
#include "tree.h"
namespace JRG {
	template<class K>
	class set
	{	
		//
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		//普通迭代器和const迭代器都是const迭代器，应为key不允许修改
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
		pair<iterator,bool> insert(const K& key)
		{
			return _t.Insert(key);
		}
	private:
		RBTree<K, K, SetKeyOfT> _t; //第一个参数和第二个参数都传入key，第三个参数传入类
	};
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

map的封装和set大同小异

#pragma once
namespace JRG {
	template<class K,class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _t.Insert(key);
			return ret.first->second;
		}
		pair<iterator, bool> insert(const pair<const K, V>& kv)
		{
			return _t.Insert(kv);
		}
	private:
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;
	};
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

重点是RBTree的迭代器的实现，同时兼容了set和map，设计的非常巧妙

template<class T,class Ref,class Ptr>
struct _RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef _RBTreeIterator<T, Ref, Ptr> Self;
	Node* _node;
	_RBTreeIterator(Node* node)
		:_node(node)
	{}
	//这个部分专门为set设计的，因为set里面的迭代器都是const迭代器，而set调用的begin返回值却是普通迭代器，所以需要可以用普通迭代器构造const迭代器
	_RBTreeIterator(const _RBTreeIterator<T, T&, T*>& it) 
		:_node(it._node)
	{}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	//默认是中序遍历红黑树，所以模拟中序遍历迭代
	Self& operator++()
	{	
		//如果右不为空迭代右子树
		if (_node->_right)
		{
			Node* subLeft = _node->_right;
			while (subLeft->_right)
			{
				subLeft = subLeft->_right;
			}
			_node = subLeft;
		}
		else	//代表右为空，那么这颗子树遍历完了，需要找孩子是父节点的左子树的节点。
		{
			Node* cur = _node;
			Node* parent = _node->_parent;
			while (parent&&cur != parent->_left) {
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	Self& operator--()
	{
		if (_node->_left)
		{
			Node* subRight = _node->_left;
			while (subRight->_right)
			{
				subRight = subRight->_right;
			}
			_node = subRight;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	Self operator++(int)
	{
		Self s = *this;
		if (_node->_right)
		{
			Node* subLeft = _node->_right;
			while (subLeft->_right)
			{
				subLeft = subLeft->_right;
			}
			_node = subLeft;
		}
		else
		{
			Node* cur = _node;
			Node* parent = _node->_parent;
			while (parent && cur != parent->_left) {
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return s;
	}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99

这就是map和set的封装以及迭代器的实现，如果需要需要完整源代码可以点击链接：红黑树全部源代码

这就是全部的内容，希望对您有所帮助。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/569390
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号