【C++】AVL树和红黑树模拟实现

AVL树和红黑树

  • 1. 背景
  • 2. AVL树的概念
  • 3. AVL树节点的定义
  • 4. AVL树的插入
  • 5. AVL树的旋转
    • 5.1. 左单旋
    • 5.2. 右单旋
    • 5.3. 左右单旋
    • 5.4. 右左单旋
    • 5.5. 旋转总结
  • 6. AVL树的验证
  • 7. AVL树的性能
  • 8. 红黑树的概念
  • 9. 红黑树的节点的定义
  • 10. 红黑树的插入
    • 10.1. 情况一
    • 10.2.情况二
  • 11. 红黑树的验证
  • 12. 红黑树与AVL树的比较

1. 背景

  1. set、map、multiset、multimap，这几个关联式容器的共同点是：底层都是用二叉搜索树来实现的，但二叉搜索树自身有缺陷，若插入的元素有序或者接近有序，二叉搜索树就会退化为单支树，查询时相当于在顺序表中进行查询，效率低下，时间复杂度退化为O(n)，因此map、set等关联式容器的底层结构对二叉搜索树进行了平衡处理，即采用平衡树来实现。

  2. 通过保证每个节点的左、右子树高度差不超过1，对树中的节点进行调整，即可降低树的高度，从而减少树的搜索长度，时间复杂度为O(longn)。

2. AVL树的概念

  1. AVL树具有的性质：a. 每个节点的左右子树都是AVL树， b. 每个节点的左右子树高度差(平衡因子)的绝对值不超过1(0、-1、1)。

  2. 平衡因子：右子树高度-左子树高度，不是必须存在的，只是一种控制方式，帮助我们更便捷的++控制树，检查是否为AVL树。

image.png

  • 如果一颗二叉搜索树高度是平衡的，那么它就是AVL树，如果它有n个节点，它的高度就是longn，则搜索的时间复杂度为O(longn)。

  • 无法做到平衡因子的值恒为0，因为二叉树插入节点是一个一个插入进去的，对于2个或者4个节点的树是无法做到左右子树高度差等于0，最优的高度差就是1。

3. AVL树节点的定义

template<class K, class V>   //AVL树的节点(KV模型)
struct AVLTreeNode{  
	typedef AVLTreeNode<K, V> Node;  

	Node* _left;      //该节点的左孩子
	Node* _right;    //该节点的右孩子
	Node* _parent;  //该节点的父亲，便于向上更新
	int _bf;       //该节点的平衡因子
	pair<K, V> _kv;  

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

4. AVL树的插入

方法：先按二叉搜索树的方式插入新节点，在更新平衡因子。

AVL的插入.png

void RotateL(Node* parent)  //右右—左单旋
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	Node* pphead = parent->_parent;
    
	parent->_right = subRL;   //b变成父节点的右孩子
	if (subRL)   //当前节点的左孩子可能存在，也可能不存在  h=0,b=0
		subRL->_parent = parent;   //更新当前节点右孩子的父亲
	subR->_left = parent;   //父节点变为当前节点的左孩纸
	parent->_parent = subR;   //更新父节点的父亲
    
	//更新当前节点的父亲，父节点可能为根节点，也可能为根节点
	if (parent == _root)  //根节点 
	{
		_root = subR;
		subR->_parent = nullptr; //更新当前节点的父亲
	}
	else
	{
		if (pphead->_left == parent)   //子树
			pphead->_left = subR;
		else
			pphead->_right = subR;

		subR->_parent = pphead; //更新当前节点的父亲
	}

	subR->_bf = 0;  //更新平衡因子
	parent->_bf = 0;
}

void RotateR(Node* parent)  //左左—右单旋
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	Node* pphead = parent->_parent;

	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;
	subL->_right = parent;
	parent->_parent = subL;

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

		subL->_parent = pphead;
	}

	subL->_bf = 0;  //更新平衡因子
	parent->_bf = 0;
}

void RotateRL(Node* parent)  //右左—先右旋再左旋
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* bf = subRL->_bf;   //因为旋转后会改变bf，需要提前记录

	RotateR(subR); 
	RotateL(parent);

	subRL->_bf = 0;   //更新平衡因子
	if (bf == 0) //情况一：当h = 0,subRL为新增节点
	{
		subR->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == -1) //情况二：当h > 0，b插入，b的高度变为h，引发旋转
	{
		subR->_bf = 1;
		parent->_bf = 0;
	}
	else if(bf == 1) //情况三：当h > 0，c插入，c的高度变为h，引发旋转
	{
		subR->_bf = 0;
		parent->_bf = -1;
	}
	else  //平衡因子异常
	{
		assert(false);
	}
}

void RotateLR(Node* parent)  //左右—先左旋再右旋
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	int bf = subLR->_bf;

	RotateL(subL);
	RotateR(parent);
    
	subLR->_bf = 0; //更新平衡因子
	if (bf == 0)
	{
		subLR->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == 1)
	{
		subL->_bf = -1;
		parent->_bf = 0;
	}
	else if(bf == -1)
	{
		subL->bf = 0;
		parent->_bf = 1;
	}
	else
	{
    	assert(false);
	}
}

bool insert(const pair<K, V>& kv)  //插入
{
	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 == nullptr) //空树
	{
		_root = cur;
		return true;
	}

	if (parent->_kv.first < kv.first)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;  //记录当前节点的父亲

	while (parent)  //更新结束： 情况1，更新到根节点
	{
		if (parent->_left == cur) //再更新平衡因子
			parent->_bf--;
		else
			parent->_bf++;

		if (parent->_bf == 0) //更新结束： 情况2，p的高度不变，不会影响上层的bf
			break;
		else if (parent->_bf == 1 || parent->_bf == -1) //更新继续：p的高度改变，会影响上层的bf，但未违反平衡树性质
		{
			cur = cur->_parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2) //违反了平衡树的规则，做处理-》旋转 ->更新结束
		{   //注意：以下4种旋转，只要完成了某一种，都会更新结束，需要break
			if (parent->_bf == 2 && cur->_bf == 1) //插入到较高右子树的右边
			{
				RotateL(parent); //右右—左单旋
				break;  
			}
			else if (parent->_bf == -2 && cur->_bf == -1) //插入到较高左子树的左边
			{
				RotateR(parent);  //左左—右单旋
				break;
			}
			else if (parent->_bf == 2 && cur->_bf == -1)  //插入到较高右子树的左边
			{ 
				RotateRL(parent);  //右左—先右旋再左旋
				break;
			}
			else if (parent->_bf == -2 && cur->_bf == 1)  //插入到较高左子树的右边
			{ 
				RotateLR(parent);  //左右—先左旋再右旋
				break;
			}
			else   //在插入前就不是AVL树    必须保证再插入前是一颗AVL树 
			{
				assert(false);
				break;
			}
		}
	}
}

5. AVL树的旋转

5.1. 左单旋

void RotateL(Node* parent)  //右右—左单旋
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	Node* pphead = parent->_parent; 
    
	parent->_right = subRL;   //b变成父节点的右孩子
	if (subRL)   //当前节点的左孩子可能存在，也可能不存在  h=0,b=0
		subRL->_parent = parent;   //更新当前节点右孩子的父亲
	subR->_left = parent;   //父节点变为当前节点的左孩纸
	parent->_parent = subR;   //更新父节点的父亲

	//更新当前节点的父亲，父节点可能为根节点，也可能为根节点
	if (parent == _root)  //根节点 
	{
		_root = subR;
		subR->_parent = nullptr; //更新当前节点的父亲
	}
	else
	{
		if (pphead->_left == parent)   //子树
			pphead->_left = subR;
		else
			pphead->_right = subR;

		subR->_parent = pphead; //更新当前节点的父亲
	}
    subL->_bf = 0;  //更新平衡因子
	parent->_bf = 0;
}

左单旋.png

5.2. 右单旋

void RotateR(Node* parent)  //左左—右单旋
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	Node* pphead = parent->_parent;

	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;
	subL->_right = parent;
	parent->_parent = subL;
    
	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (pphead->_left == parent)
			pphead->_left = subL;
		else
			pphead->_right = subL;

		subL->_parent = pphead;
	}
	subL->_bf = 0;  //更新平衡因子
	parent->_bf = 0;
}

image.png

5.3. 左右单旋

void RotateLR(Node* parent)  //左右—先左旋再右旋
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
    
	int bf = subLR->_bf;

	RotateL(subL);
	RotateR(parent);

	subLR->_bf = 0; //更新平衡因子
	if (bf == 0)
	{
		subLR->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == 1)
	{
		subL->_bf = -1;
		parent->_bf = 0;
	}
	else if(bf == -1)
	{
		subL->bf = 0;
		parent->_bf = 1;
	}
	else
	{
		assert(false);
	}
}

左右旋.png

5.4. 右左单旋

void RotateRL(Node* parent)  //右左—先右旋再左旋
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* bf = subRL->_bf;   //因为旋转后会改变bf，需要提前记录

	RotateR(subR); 
	RotateL(parent);

	subRL->_bf = 0;  //更新平衡因子
	if (bf == 0) //情况一：当h = 0,subRL为新增节点
	{
		subR->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == -1) //情况二：当h > 0，b插入，b的高度变为h，引发旋转
	{
		subR->_bf = 1;
		parent->_bf = 0;
	}
	else if(bf == 1) //情况三：当h > 0，c插入，c的高度变为h，引发旋转
	{
		subR->_bf = 0;
		parent->_bf = -1;
	}
	else  //平衡因子异常
	{
		assert(false);
	}
}

AVL右左双旋.png

5.5. 旋转总结

image.png

6. AVL树的验证

方法：先验证其为二叉搜索树(中序遍历得到有序序列），再验证其为平衡树(左右子树高度差的绝对值不超过1、平衡因子正常)。

int _Height(Node* root) //后序遍历
{
	if (root == nullptr)
		return 0;

	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

bool _Isbalance(Node* root) //前序遍历  验证其为平衡树
{
	if (root == nullptr)
		return true;

	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	if (abs(rightHeight - leftHeight) >= 2)
	{
		cout << "不平衡" << endl; 
		return false;
	}

	if (rightHeight - leftHeight != root->_bf)
	{
		cout << root->_kv.first << ":平衡因子异常" << endl;
		return false;
	}
	return _Isbalance(root->_left) && _Isbalance(root->_right);
}

void _Inorder(Node* root) //中序遍历 验证其为二叉搜索树
{
	if (root == nullptr)
		return;

	_Inorder(root->_left);
	cout << root->_kv.first << "[" << root->_bf << "]" << endl;
	_Inorder(root->_right);
}

  • 不能采用层序遍历、看bf的值，原因：对于完全二叉树、满二叉树通过层序遍历可以推出树的正确结构，AVL树不一定为完全、满二叉树。在旋转时，bf可能更新异常，此时看bf的值，会造错误构。

  • 验证其为平衡二叉树，采用前序遍历，缺点：先求高度，再判平衡，递归式判子树平衡，导致重复求子树的高度，效率低——》解决方法：将前序改成后序，并将高度作为引用参数(引用，各个栈帧相互影响），边判平衡边求高度。

bool _Isbalance(Node* root, int& height) //后序遍历+引用参数
{
	if (root == nullptr) //空树也是AVL树
	{
		height = 0;
		return true;
	}

	int leftHeight = 0, rightHeight = 0;
	if(!_Isbalance(root->_left, leftHeight) || !_Isbalance(root->_right, rightHeight)) 
		return false;  //只要左右子树有一颗不是平衡树，该树就不是平衡树

	height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	return true;
}

int main()
{
	int a[] = { 8, 5, 2, 6, 3, 7, 4, 1 };
	AVLTree<int, int> t;
	for (auto& e : a)
	{
		t.insert(make_pair(e, e));
	}
	t.Inorder();
	cout << t.Isbalance() << endl;
	return 0;
}

image.png
image.png

7. AVL树的性能

  • AVL是一颗高度平衡的二叉搜索树，查询时效率高，时间复杂度为O(longn)，但如果要对AVL树进行结构修改操作，性能非常低，如：插入时，为了维持平衡需要进行多次旋转，删除可能旋转要持续到根节点位置处。

  • 如果需要一种查询高效且数据有序的数据结构，数据的个数为静态的(不会插入元素，结构不会发生改变），可以考虑使用AVL树。如果一个结构需要经常的修改，AVL树不太适用。

8. 红黑树的概念

  1. 红黑树的概念：红黑树，是一种二叉搜索树，在每个节点上增加一个存储位来表示节点的颜色，red或者black，通过对每条路径上节点着色方式的控制，红黑树保证了最长路径不超过最短路径的二倍，其他路径的长度位于最短路径长度和最长路径长度之间，即：每条路径不会比其他路径长出两倍，因此它接近于平衡。

  2. 红黑树的性质
    a.每个节点的颜色不是红色就是黑色 ；
    b.根节点的颜色一定是黑色 ；
    c.如果有一个节点的颜色是红色，则它的孩子节点的颜色一定是黑色，即：没有连续的红色节点；
    d.每条路径都具有相同数量的黑色节点。
    e.每个叶子节点都是黑色的，叶子节点指的是空节点，又名为NIL节点，是为了避免路径(根节点到空节点)数错的误区。

  3. 问：只要满足以上的性质，为什么红黑树就能保证最长路径中节点个数不超过最短路径中节点个数的两倍？
    答：因为在极端情况下，最短路径：全黑，最长路径：一黑一红。

image.png

9. 红黑树的节点的定义

enum Color {  //枚举，一一列举出事物具有的所有可能
	Red,  //枚举常量，给枚举变量进行赋值
	Black,
};

template<class K, class V>//红黑树的节点(KV模型)
struct RBTreeNode {
	typedef RBTreeNode<K, V> Node;

	Node* _left;      //该节点的左孩子
	Node* _right;    //该节点的右孩子
	Node* _parent;  //该节点的父亲，便于向上更新
	pair<K, V> _kv;   
	Color _col;

	RBTreeNode(const pair<K, V>& kv, Color col = Red)  //构造函数
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(col)   //默认新插入节点的颜色为红色
	{ }
};

10. 红黑树的插入

方法：先按照二叉搜素树的方式插入，在更新颜色。

红黑树的插入.png

void RotateL(Node* parent)  //右右—左单旋
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
    
    Node* pphead = parent->_parent;

	parent->_right = subRL;  
	if (subRL)   
		subRL->_parent = parent;  
	subR->_left = parent;  
	parent->_parent = subR;   

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

    	subR->_parent = pphead;
	}
}

void RotateR(Node* parent)  //左左—右单旋
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	Node* pphead = parent->_parent;

	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;
	subL->_right = parent;
	parent->_parent = subL;

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

		subL->_parent = pphead;
	}
}

void RotateRL(Node* parent)  //右左—先右旋再左旋
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
    
	RotateR(subR);
	RotateL(parent);
}

void RotateLR(Node* parent)  //左右—先左旋再右旋
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	RotateL(subL);
	RotateR(parent);
}

bool insert(const pair<K, V>& kv)  //插入
{
	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 == nullptr) //空树
	{
		_root = cur;
        _root->_col = Black;  //跟节点为黑
		return true;
	}

	if (parent->_kv.first < kv.first)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;  //记录当前节点的父亲

	//更新颜色
	//插入结束：1.插入节点的父亲是黑色，因为插入前该树就为红黑树 2.情况一处理完后，cur为根节点，且为黑色
	while (parent && parent->_col == Red) 
	{ //爷爷一定存在，因为c为红，p为红，所以p一定不是根节点，且一定有父节点
		Node* grandfather = parent->_parent; 
		if (parent == grandfather->_left)  //旋转需要确定方向
		{
			Node* uncle = grandfather->_right;  
			if (uncle && uncle->_col == Red) //情况一：叔叔存在且为红->无方向(p、u为g的任意边，c为p的任一边)
			{  //cur可能为新增节点，也可能一开始为黑色，cur的子树(下一层为红，下一层为新插入节点)在调整过程中将cur由黑变为红
				parent->_col = uncle->_col = Black; //p、u变为黑，g变为红
				grandfather->_col = Red;
				//g可能为根节点(更新结束)，也可能为子树(继续向上更新)
				cur = grandfather;   
				parent = cur->_parent; 
			}
			else  //情况二：叔叔不存在 或者 叔叔存在且为黑
			{  //叔叔不存在，cur为新增节点 或 cur原来为黑，经子树调整由黑变红
				if (parent->_left == cur)  //左左——右单旋
				{
					RotateR(grandfather);
    				parent->_col = Black; //p变为黑，g变为红
					grandfather->_col = Red;
				}
				else    //左右——左右单旋 
				{
					RotateL(parent); 
					RotateR(grandfather);
					cur->_col = Black;  //c变黑，g变红
					grandfather->_col = Red;
				}
				break;  //更新结束：3.旋转+颜色处理后就是红黑树了
			}
		}
		else
		{
			Node* uncle = grandfather->_left;
			if (uncle && uncle->_col == Red)
			{
				parent->_col = uncle->_col = Black;
				grandfather->_col = Red;

				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				if (parent->_right == cur)  //右右——左单旋
				{
					RotateL(grandfather);
					parent->_col = Black;
					grandfather->_col = Red;
				}
				else   //右左——右左单旋
				{
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = Black;
					grandfather->_col = Red;
				}
				break;  
			}
		}
	}
	_root->_col = Black;  //g为根，颜色变为黑，更新结束
    return true;  //情况一，插入节点的父亲为黑，插入结束
}

10.1. 情况一

  1. 叔叔存在且为红色——将p、u变为黑色，g变为红色，在把g给c。若c为根节点，将c变为黑色，插入结束(break)。若c不为根节点，继续向上更新颜色，直到c为根 或则 c的父亲为黑色。

  2. 无方向——p、u是g的左右都可以，c是p的左右都可以，处理方式都是一样的。

if (uncle && uncle->_col == Red) //情况一：叔叔存在且为红->无方向(p、u为g的任意边，c为p的任一边)
{  //cur可能为新增节点，也可能一开始为黑色，cur的子树(下一层为红，下一层为新插入节点)在调整过程中将cur由黑变为红
	parent->_col = uncle->_col = Black; //p、u变为黑，g变为红
	grandfather->_col = Red;

	//g可能为根节点(更新结束)，也可能为子树(继续向上更新)
	cur = grandfather;   
	parent = cur->_parent; 
}

红黑树插入情况一.png

10.2.情况二

  1. 叔叔不存在 或者 叔叔存在且为黑色——旋转(有方向，4种) + 颜色处理。

  2. a. p为g的左孩子，c为p的左孩子，左左，右单旋。b. p为g的右孩子，c为p的右孩子，右右，左单旋，将p变为黑色，将g变为红色—》将p变为黑色，将g变为红色。c. p为g的左孩子，c为p的右孩子，左右旋。d. p为g的右孩子，c为p的左孩子，右左旋——》将c变为黑色，g变为红色。

  3. 若叔叔不存在，c只可以是新增节点，因为若c不是新增节点，该树最短路径长度为1，最长路径长度为4，在插入前就已经违反了红黑树性质3。若叔叔存在且为红，c只能是原来为黑色，经子树调整由黑色变为红色。

  4. 情况二在插入前最短路径长度：最短路径长度=1：2，插入后，违反了红黑树性质4，所以需要做旋转处理。

if (parent->_left == cur)  //左左——右单旋
{
	RotateR(grandfather);
	parent->_col = Black; //p变为黑，g变为红
	grandfather->_col = Red;
}
else    //左右——左右单旋 
{
	RotateL(parent); 
	RotateR(grandfather);
	cur->_col = Black;  //c变黑，g变红
	grandfather->_col = Red;
}
break;  //更新结束：3.旋转+颜色处理后就是红黑树了

红黑树插入情况二.png

11. 红黑树的验证

方法：先验证其为二叉搜索树(中序遍历得到有序序列），再验证其是否满足红黑树的性质。

void Inorder() //验证其为二叉搜索树，中序遍历
{
	_Inorder(_root);
}

bool Balance() //验证其是否满足红黑树的性质
{
	if (_root && _root->_col == Red) //红黑树性质2，跟节点为黑色
		return false;

	int refvalue = 0;  //红黑树性质4，每条路径具有相同数量的黑节点
	Node* cur = _root; 
	while (cur)
	{
		if (cur->_col == Black)
			refvalue++;   //找参考值
		cur = cur->_left;
	}

	_Balance(_root, 0, refvalue);
}

//前序遍历，将每条路径黑色节点的数量于参考值比较，验证性质4
bool _Balance(Node* root, int blackcount, int& refvalue)
{
	if (root == nullptr)
	{
		if (blackcount != refvalue)
			return false;

		return true;
    }

	if (root->_col == Red && root->_parent->_col == Red)
		return false;   //验证红黑性质3，没有连续的红节点，孩子找爹

	if (root->_col == Black) //blackcount没有用引用，因为下层不能影响上次，blackcount表示的是当前节点到根节点路径上黑色节点的数量
    	blackcount++;
    return _Balance(root->_left, blackcount, refvalue) && _Balance(root->_right, blackcount, refvalue); //放在后面，从前往后
}

void _Inorder(Node* root) //中序遍历
{
	if (root == nullptr)
		return;

	_Inorder(root->_left);
	cout << root->_kv.first <<  endl;
	_Inorder(root->_right);
}

#define _CRT_SECURE_NO_WARNINGS 1
#include"RBTree.h"

void test1()
{
	int a[] = { 5, 4, 8, 6, 2, 9, 1, 3, 7 };
 	RBTree<int, int> rb;
	for (auto& e : a)
	{
		rb.insert(make_pair(e, e));
	}
	rb.Inorder();

	cout << rb.Balance() << endl;
}

int main()
{
	test1();
	return 0;
}

image.png
image.png

12. 红黑树与AVL树的比较

  • 红黑树和AVL树都是高效的平衡二叉搜索树，增删查改的时间复杂度都为O(longn)，但红黑树不要求绝对平衡，只需保证最长路径的长度不超过最短路径长度的两倍，相对而言，降低了插入、删除时旋转的次数，所以在经常进行增删查改的结构中红黑树的性能更优，在实际应用红黑树的更多。

  • AVL树的高度接近于longn,红黑树的高度接近于2longn,所以搜索效率AVL树略优于红黑树，但是几乎可以忽略不记，因为n足够大时，longn就足够小，两者的差距微乎其微。当插入同样得数据，AVL树的高度更低，通过多次旋转达到的。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/641245.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

HTTP 请求的完整过程

HTTP 请求的完整过程

HTTP 请求的完整过程 当用户在浏览器输入网址回车之后&#xff0c;网络协议都做了哪些工作呢? 首先工作的是 浏览器应用程序&#xff0c;他要解析出 URL中的域名 根据域名获取对应的ip地址&#xff0c;首先从浏览器缓存中査看&#xff0c;如下可以査看浏览器中域名对应ip的解…
阅读更多...
Python游戏编程：一步步用Python打造经典贪吃蛇小游戏

Python游戏编程：一步步用Python打造经典贪吃蛇小游戏

贪吃蛇作为一款极其经典且广受欢迎的小游戏&#xff0c;是早期 Windows 电脑和功能手机&#xff08;特别是诺基亚手机&#xff09;流行度极高的小游戏&#xff0c;是当时功能手机时代最具代表性的游戏之一。游戏的基本规则和目标十分简单&#xff0c;但却极具吸引力&#xff0c…
阅读更多...
C# 正则表达式使用小计

C# 正则表达式使用小计

此文档用于记录平时使用正则表达式的心得&#xff0c;不定期更新 基础 实例 替换实例一 //这里匹配以 “( 开头,以 )” 结尾的字符串 private static Regex REGEX_ARG_CONTENT new Regex("""(.*?)""");//此方法用于在匹配到的结果前添加字符…
阅读更多...
C#【进阶】特殊语法

C#【进阶】特殊语法

特殊语法、值和引用类型 特殊语法 文章目录 特殊语法1、var隐式类型2、设置对象初始值3、设置集合初始值4、匿名类型5、可空类型6、空合并操作符7、内插字符串8、单句逻辑简略写法 值和引用类型1、判断值和引用类型2、语句块3、变量的生命周期4、结构体中的值和引用5、类中的值…
阅读更多...
STM32+CubeMX移植SPI协议驱动W25Q16FLash存储器

STM32+CubeMX移植SPI协议驱动W25Q16FLash存储器

STM32CubeMX移植SPI协议驱动W25Q16FLash存储器 SPI简介拓扑结构时钟相位&#xff08;CPHA&#xff09;和时钟极性&#xff08; CPOL&#xff09; W25Q16简介什么是Flash&#xff0c;有什么特点&#xff1f;W25Q16内部块、扇区、页的划分引脚定义通讯方式控制指令原理图 CubeMX配…
阅读更多...
【Linux】Linux下centos更换国内yum源

【Linux】Linux下centos更换国内yum源

&#x1f331;博客主页&#xff1a;青竹雾色间 &#x1f331;系列专栏&#xff1a;Linux &#x1f618;博客制作不易欢迎各位&#x1f44d;点赞⭐收藏➕关注 目录 1. 备份旧的 YUM 源文件2. 下载国内的 YUM 源文件阿里云&#xff1a;网易&#xff1a; 3. 清理 YUM 缓存4. 更新…
阅读更多...
【C语言】走进指针世界（下卷）

【C语言】走进指针世界（下卷）

前言 在“走进指针世界&#xff08;上卷&#xff09;”中&#xff0c;我们已经说过&#xff1a;什么是指针、内存和地址&#xff0c;指针的使用、声明、初始化&#xff0c;取地址运算符、解引用运算符以及这两者关系&#xff0c;还有指针赋值。 在正式使用指针进行各种代码的…
阅读更多...
海外动态IP代理如何提高效率？

海外动态IP代理如何提高效率？

动态住宅IP代理之所以能够有效提升数据爬取的效率和准确性&#xff0c;主要归功于其提供的IP地址具有高度的匿名性和真实性。这些IP地址来自于真实的用户网络&#xff0c;因此相比于数据中心IP&#xff0c;它们更不容易被网站的安全系统标识为爬虫。此外&#xff0c;由于IP地址…
阅读更多...
C：通过fwrite和fread读写数据结构

C：通过fwrite和fread读写数据结构

1.头文件 #include <stdio.h> 2.fopen()函数 调用fopen()函数可以打开或创建一个文件。 FILE *fopen(const char *path, const char *mode); path &#xff1a; 参数 path 指向文件路径&#xff0c;可以是绝对路径、也可以是相对路径。 mode &#xff1a; 参数 mode …
阅读更多...
React useState数组新增和删除项

React useState数组新增和删除项

在React中&#xff0c;我们可以使用useState钩子来管理组件的状态&#xff0c;其中包括数组。如何在React函数组件中对数组进行增加和删除项的操作&#xff1f; 新增项时&#xff1a;我们可以对原数组进行解构&#xff0c;并把新增项一起加入到新数组&#xff1b; 删除项时&…
阅读更多...
JDBC(Java DataBase Connectivity)Java数据库连接

JDBC(Java DataBase Connectivity)Java数据库连接

JDBC(Java DataBase Connectivity) Java 语言连接数据库 再本模块中,java提供里一组用于连接数据库的类和接口Java 语言开发者,本身没有提供如何具体连接数据库的功能只是定义了一组java程序连接数据库的访问接口 连接到数据库向数据库发送增,修改,删除这一类的sql发送查询sq…
阅读更多...
CATIA入门操作——为什么大佬的工具栏是水平的？如何把工具栏变水平？

CATIA入门操作——为什么大佬的工具栏是水平的？如何把工具栏变水平？

目录 引出工具栏怎么变成水平&#xff1f;总结发生肾么事了&#xff1f;&#xff1f;鼠标中键旋转不了解决&#xff1a;特征树不显示参数关系 我的窗口去哪了&#xff1f;插曲&#xff1a;草图工具的调出插曲&#xff1a;颜色工具栏显示 弹窗警告警告&#xff1a;创建约束是临时…
阅读更多...
linux系统介绍

linux系统介绍

Linux是一种免费使用和自由传播的类Unix操作系统&#xff0c;它是一个基于POSIX和Unix的多用户、多任务、支持多线程和多CPU的操作系统。Linux起源于1991年&#xff0c;由芬兰程序员林纳斯托瓦兹&#xff08;Linus Torvalds&#xff09;创建&#xff0c;并迅速获得了全球开发者…
阅读更多...
香橙派华为昇腾CANN架构编译opencv4.9

香橙派华为昇腾CANN架构编译opencv4.9

香橙派华为升腾AI盒子 为啥要编译opencv4.9.0&#xff0c; 因为在4.9.0 中增加了华为昇腾CANN的外接开发库&#xff0c;下图为盒子外观&#xff0c;此次一接到这个盒子&#xff0c;立刻开始开箱操作&#xff0c;首先就是要编译opencv4.9&#xff0c;以前在香橙派3588 的盒子中…
阅读更多...
抖音极速版：抖音轻量精简版本，新人享大福利

抖音极速版：抖音轻量精简版本，新人享大福利

和快手一样&#xff0c;抖音也有自己的极速版&#xff0c;可视作抖音的轻量精简版&#xff0c;更专注于刷视频看广告赚钱&#xff0c;收益比抖音要高&#xff0c;可玩性更佳。 抖音极速版简介 抖音极速版是一个提供短视频创业和收益任务的平台&#xff0c;用户可以通过观看广…
阅读更多...
当前时机是否适合进入 AIGC 行业：行业发展与市场需求分析

当前时机是否适合进入 AIGC 行业：行业发展与市场需求分析

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…
阅读更多...
下一代Docker会让部署更丝滑吗

下一代Docker会让部署更丝滑吗

下一代Docker会让部署更丝滑吗 如何通俗易懂的理解DockerDocker有什么缺点Docker与AI结合&#xff0c;会让部署更加丝滑吗 随着互联网技术的不断发展&#xff0c;单机系统已经无法满足日益正常的用户量以及正常处理用户请求&#xff0c;这个时候就需要进行多机部署&#xff0c;…
阅读更多...
贝锐向日葵打造农机设备远程运维支持方案

贝锐向日葵打造农机设备远程运维支持方案

当物联网“万物互联”的概念向第一产业赋能&#xff0c;农机设备的智能化程度也越来越高。 所谓农业物联网&#xff0c;即在应用层将大量的传感器节点构成监控网络&#xff0c;通过各种传感器采集信息&#xff0c;以帮助农民及时发现问题&#xff0c;并准确地判定发生问题的位…
阅读更多...
1099: 希尔排序算法实现

1099: 希尔排序算法实现

解法&#xff1a; 希尔增量选定n/2&#xff0c; #include<iostream> #include<vector> using namespace std; int main() {int n;cin >> n;vector<int> vec(n);for (int i 0; i < n; i) cin >> vec[i];int d n / 2;for (int i 0; i <…
阅读更多...
【C语言】指针运算

【C语言】指针运算

前言 前面在“走进指针世界”中我已经讲解过指针相关的很多前置知识&#xff0c;其实还有一个很重要的部分就是指针的运算。这篇博客&#xff0c;就让我们一起了解一下指针的运算吧&#xff01; 指针作为变量&#xff0c;是可以进行算术运算的&#xff0c;只不过情况会和整型…
阅读更多...
最新文章

Copyright @ 2022~2023