紅黑樹

紅黑樹的概念

紅黑樹，是一種二叉搜尋樹，但在每個結點上增加一個存儲位表示結點的顔色，可以是Red或Black。 通過 對任何一條從根到葉子的路徑上各個結點着色方式的限制，紅黑樹確定沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的。

紅黑樹的性質

1. 每個結點不是紅色就是黑色
2. 根節點是黑色的
3. 如果一個節點是紅色的，則它的兩個孩子結點是黑色的
4. 對于每個結點，從該結點到其所有後代葉結點的簡單路徑上，均包含相同數目的黑色結點
5. 每個葉子結點都是黑色的(此處的葉子結點指的是空結點)

思考：為什麼滿足上面的性質，紅黑樹就能保證：其最長路徑中節點個數不會超過最短路徑節點個數的兩倍？

紅黑樹節點的定義

// 節點的顔色      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<ValueType>* _pLeft;   // 節點的左孩子               RBTreeNode<ValueType>* _pRight;  // 節點的右孩子               RBTreeNode<ValueType>* _pParent; // 節點的雙親(紅黑樹需要旋轉，為了實作簡單給出該字段)               ValueType _data;            // 節點的值域               Color _color;               // 節點的顔色 };           

紅黑樹結構

為了後續實作關聯式容器簡單，紅黑樹的實作中增加一個頭結點，因為跟節點必須為黑色，為了與根節點進 行區分，将頭結點給成黑色，并且讓頭結點的 pParent 域指向紅黑樹的根節點，pLeft域指向紅黑樹中小的節點，_pRight域指向紅黑樹中大的節點。

紅黑樹的代碼：

#define _CRT_SECURE_NO_WARNINGS 1     #include<iostream>     #include<stdlib.h>     #pragma once     enum Color     {     	RED,     	BLA,     };     template<class K, class V>     class RBTreeNode     {     	RBTreeNode<K, V>* _left;     	RBTreeNode<K, V>* _right;     	RBTreeNode<K, V>* _parent;     	std::pair<K, V> _kv;     	Color _col;     };     template<class K, class V>     class RBTree     {     	typedef  RBTreeNode<K, V> Node;     public:     	bool Insert(const std::pair<K, V>& kv)     	{     		if (_root == nullptr)     		{     			_root = new Node(kv);     			_root->_col = BLA;     			return true;     		}     		Node* parent = nullptr;     		Node* cur = _root;     		while (cur)     		{     			parent = cur;     			if (cur->_kv.first < kv.first)     			{     				cur = cur->_right;     			}     			else if (cur->_kv.first > kv.first)     			{     				cur = cur->_left;     			}     			else     			{     				return false;     			}     		}     		cur = new Node(kv);     		cur->_col = RED;//這不能選黑色，因為每條路徑的黑結點都是一樣的，如果插入黑的會違反規則     		if (parent->_kv.first < kv.first)     		{     			parent->_right = cur;     			cur->_parent = parent;     		}     		else     		{     			parent->_left = cur;     			cur->_parent = parent;     		}     		//達到平衡     		while (parent && parent->_col == RED)     		{     			Node* grandfather = parent->_parent;     			if (parent = grandfather->_left)     			{     				Node* uncle = grandfather->_right;     				if (uncle && uncle->_col == RED)     				{     					//第一種情況：變色     					parent->_col = BLA;     					uncle->_col = BLA;     					grandfather->_col = RED;     					cur = granffather;     					parent = cur->_parent;     				}     				else//uncle不存在或者存在且為黑     				{     					//第三種情況：雙旋->單旋     					if (cur == parent->_right)//單旋     					{     						RotateL(parent);     						swap(cur, parent);//旋轉之後cur和parent的位置發生了改變     					}     					//第二種情況：單旋＋變色     					RotateR(grandfather);     					parent->_col = BLA;     					grandfather->_col = RED;     				}     			}     			else//parent = grandfarher->_right     			{     				Node* uncle = grandfather->_left;     				if (uncle && uncle->_col == RED)     				{     					//變色     					parent->_col = BLA;     					uncle->_col = BLA;     					grandfather->_col = RED;     					cur = grandfather;     					parent = cur->_parent;     				}     				else     				{     					if (cur == parent->_left)     					{     						RotateR(parent);     						swap(cur, parent);     					}     					RotateL(grandfather);     					parent->_col = BLA;     					grandfather->_col = RED;     				}     			}     		}     		_root->_col = BLA;     		return true;     	}     private:     	Node* _root = nullptr;     };     int main()     {     	system("pause");     	return 0;     }