红黑树的插入及查找-创新互联

红黑树：首先是一棵二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是Red或Black。通过对任何一条从根到叶子简单路径上的颜色来约束，红黑树保证最长路径不超过最短路径的两倍，因而近似于平衡。

红黑树满足的性质：

1. 根节点是黑色的

2. 如果一个节点是红色的，则它的两个子节点是黑色的(没有连续的红节点)

3. 每条路径的黑色节点的数量相等

红黑树保证最长路径不超过最短路径的两倍，如下图所示

插入节点时的三种情况

1. 
   

2. cur为红，p为红，g为黑，u存在且为红

   

3. cur为红，p为红，g为黑，u不存在/u为黑，p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转

   p、g变色--p变黑，g变红

   

4. cur为红，p为红，g为黑，u不存在/u为黑，p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转

#pragma once

#include 
using namespace std;
enum Color
{
	RED,
	BALCK
};

template
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	K _key;
	V _value;
	Color _col;
	RBTreeNode(const K& key, const V& value)
		:_left(NULL)
		, _right(NULL)
		, _parent(NULL)
		, _key(key)
		, _value(value)
		, _col(RED)
	{}
};

template
class RBTree
{
	typedef RBTreeNode Node;
public:
	RBTree()
		:_root(NULL)
	{}
	Node* Find(const K& key)
	{
		if (_root == NULL)
			return NULL;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key == key)
				return cur;
			else if (cur->_key < key)
				cur = cur->_right;
			else
				cur = cur->_left;
		}
		return NULL;
	}
	bool Insert(const K& key, const V& value)
	{
		if (_root == NULL)
		{
			_root = new Node(key, value);
			_root->_col = BALCK;
			return true;
		}
		Node* cur = _root;
		Node* parent = NULL;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key>key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				cout << "该节点已存在" << endl;
				return false;
			}
		}
		cur = new Node(key, value);
		if (parent->_key > key)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		//调整节点颜色
		while (cur != _root&&parent->_col == RED)
		{//规定根节点必须为黑色，若parent的颜色为红色，则它一定不为根节点，它的父节点也一定存在
			Node* ppNode = parent->_parent;//不用判空
			Node* uncle = NULL;
			
			if (parent == ppNode->_left)
			{//parent为它的父节点的左孩子，则叔节点若存在，肯定在右边
				uncle = ppNode->_right;
				if (uncle&&uncle->_col == RED)
				{//1.cur为红，parent为红，ppNode为黑，u存在且为红
					parent->_col = uncle->_col = BALCK;
					ppNode->_col = RED;
					cur = ppNode;
					ppNode = cur->_parent;
				}
				else
				{//2.cur为红，parent为红，uncle不存在或者为黑
					if (cur == parent->_right)
					{
						RotateL(parent);
						swap(cur, parent);
					}
					parent->_col = BALCK;
					ppNode->_col = RED;
					RotateR(ppNode);
				}
			}
			else
			{//另一边
				uncle = ppNode->_left;
				if (uncle&&uncle->_col == RED)
				{//1.cur为红，parent为红，ppNode为黑，u存在且为红
					parent->_col = uncle->_col = BALCK;
					ppNode->_col = RED;
					cur = ppNode;
					ppNode = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						RotateR(parent);
						swap(cur, parent);
					}
					parent->_col = BALCK;
					ppNode->_col = RED;
					RotateL(ppNode);
				}
			}

		}
	}
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		Node* ppNode = parent->_parent;
		subL->_right = parent;
		if (parent == _root || ppNode == NULL)//若要调整的节点为根节点
		{
			_root = subL;
			subL->_parent = NULL;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}
		Node* ppNode = parent->_parent;
		subR->_left = parent;
		if (parent == _root || ppNode == NULL)//若要调整的节点为根节点
		{
			_root = subR;
			subR->_parent = NULL;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
	}
	bool IsBalance()
	{
		int BlackNodeCount = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BALCK)
			{
				BlackNodeCount++;
			}
			cur = cur->_left;
		}
		int count = 0;
		return _IsBalance(_root, BlackNodeCount, count);
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	~RBTree()
	{}
protected:
	bool _IsBalance(Node* root, const int BlackNodeCount, int count)
	{
		if (root == NULL)
			return false;
		if (root->_parent)
		{
			if (root->_col == RED && root->_parent->_col == RED)
			{
				cout << "不能有两个连续的红节点" << endl;
				return false;
			}
		}
		if (root->_col == BALCK)
			++count;
		if (root->_left == NULL&&root->_right == NULL&&count != BlackNodeCount)
		{
			cout << "该条路径上黑色节点数目与其它不相等" << endl;
			return false;
		}
		return _IsBalance(root->_left, BlackNodeCount,count) &&
			_IsBalance(root->_right, BlackNodeCount,count);
	}
	void _InOrder(Node* root)
	{
		if (root == NULL)
			return;
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
protected:
	Node* _root;
};

void Test()
{
	RBTree bt;
	int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)
	{
		bt.Insert(arr[i], i);
	}
	bt.IsBalance();
	bt.InOrder();
	cout << bt.Find(6) << endl;;
	cout<
红黑树与AVL树的异同：
红黑树和AVL树都是高效的平衡二叉树，增删查改的时间复杂度都是O(lg(N))
红黑树的不追求完全平衡，保证最长路径不超过最短路径的2倍，相对而言，降低了旋转的要求，所以性能跟AVL树差不多，但是红黑树实现更简单，所以实际运用中红黑树更多。
红黑树的应用：
STL库中的map、set
多路复用epoll模式在linux内核的实现
JAVA的TreeMap实现
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
                

                文章标题：红黑树的插入及查找-创新互联                

                文章出自：http://wjwzjz.com/article/dgeess.html