M的编程备忘录之C++——map和set

bool Insert(const T& data)
	{
		if (_pRoot == nullptr)
		{
			_pRoot = new Node(data);
			_pRoot->_bf = 0;
			return true;
		}
 
		Node* parent = nullptr;
		Node* cur = _pRoot;
		while (cur)
		{
			if (cur->_data < data)
			{
				parent = cur;
				cur = cur->_pRight;
			}
			else if (cur->_data > data)
			{
				parent = cur;
				cur = cur->_pLeft;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(data);
		if (parent->_data > data)
		{
			parent->_pLeft = cur;
		}
		else
		{
			parent->_pRight = cur;
		}
		cur->_pParent = parent;
 
		while (parent)
		{
			if (cur == parent->_pRight)
			{
				parent->_bf++;
			}
			else
			{
				parent->_bf--;
			}
 
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = cur->_pParent;
				parent = parent->_pParent;
			}
			else if (parent->_bf == 2 || parent->_bf == -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);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}

5.1.4、AVL树的旋转

         1. 新节点插入较高左子树的左侧---左左：右单旋

void RotateR(Node* pParent)
	{
		Node* subL = pParent->_pLeft;
		Node* subLR = subL->_pRight;
 
		pParent->_pLeft = subLR;
		if (subLR)
		{
			subLR->_pParent = pParent;
		}
 
		Node* ppNode = pParent->_pParent;
 
		subL->_pRight = pParent;
		pParent->_pParent = subL;
 
		if (pParent == _pRoot)
		{
			_pRoot = subL;
			_pRoot->_pParent = nullptr;
		}
		else
		{
			if (ppNode->_pLeft == pParent)
			{
				ppNode->_pLeft = subL;
			}
			else
			{
				ppNode->_pRight = subL;
			}
			subL->_pParent = ppNode;
		}
		subL->_bf = pParent->_bf = 0;
	}

void RotateL(Node* pParent)
	{
		Node* subR = pParent->_pRight;//父节点的右孩子
		Node* subRL = subR->_pLeft;//subR的左孩子
 
		pParent->_pRight = subRL;
		if (subRL)//若subRL不为空，将subRL的父亲改成pParent
		{
			subRL->_pParent = pParent;
		}
 
		Node* ppNode = pParent->_pParent;//记录父节点的父节点
		
		subR->_pLeft = pParent;//将pParent设为subR的左孩子
		pParent->_pParent = subR;//将pParent的父节点设为subR
 
		if (pParent == _pRoot)//如果是根节点
		{
			_pRoot = subR;
			_pRoot->_pParent = nullptr;
		}
		else
		{
			if (pParent == ppNode->_pLeft)
			{
				ppNode->_pLeft = subR;
			}
			else
			{
				ppNode->_pRight = subR;
			}
			subR->_pParent = ppNode;
		}
		pParent->_bf = 0;
		subR->_bf = 0;
	}

        3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋

	void RotateLR(Node* pParent)
	{
		Node* subL = pParent->_pLeft;
		Node* subLR = subL->_pRight;
		int bf = subLR->_bf;
 
		RotateL(pParent->_pLeft);
		RotateR(pParent);
 
		if (bf == 0)
		{
			pParent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == -1)
		{
			pParent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			pParent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

        4. 新节点插入较高右子树的左侧---右左：先右单旋再左单旋

void RotateRL(Node* pParent)
	{
		Node* subR = pParent->_pRight;
		Node* subRL = subR->_pLeft;
		int bf = subRL->_bf;
 
		RotateR(pParent->_pRight);
		RotateL(pParent);
 
		if (bf == 0)
		{	
			subRL->_bf = 0;
			pParent->_bf = 0;
			subR->_bf = 0;
			
		}
		else if (bf == -1)
		{	subRL->_bf = 0;
			pParent->_bf = 0;
			subR->_bf = 1;
			
		}
		else if (bf == 1)
		{	subRL->_bf = 0;
			pParent->_bf = -1;
			subR->_bf = 0;
			
		}
		else
		{
			assert(false);
		}
	}

5.2、红黑树

5.2.1、概念

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

5.2.2、性质 

5.2.3、红黑树节点定义

// 节点的颜色
enum Color
{
    RED, 
    BLACK
};
// 红黑树节点的定义
template<class ValueType>
struct RBTreeNode
{
     RBTreeNode(const ValueType& data = ValueType()，Color color = RED)
     : _pLeft(nullptr)
     , _pRight(nullptr)
     , _pParent(nullptr)
     , _data(data)
     , _color(color)
     {}
     RBTreeNode* _pLeft;   // 节点的左孩子
     RBTreeNode* _pRight;  // 节点的右孩子
     RBTreeNode* _pParent; // 节点的双亲(红黑树需要旋转，为了实现简单给出该字段)
     ValueType _data;            // 节点的值域
     Color _color;               // 节点的颜色
};