红黑树(RBT)详细学习记录

# 1.什么是红黑树
- 红黑树(`Red Black Tree`)是一种`自平衡的二叉查找树`,是一种高效的查找树. 它是由 `Rudolf Bayer`于1978年发明，在当时被称为`对称二叉B 树(symmetric binary B-trees)`。后来，在1978年被`Leo J. Guibas`和`Robert Sedgewick`修改为如今的红黑树。
- `红黑树具有良好的效率，它可在 O(logN) 时间内完成查找,增加,删除等操作`.
- 红黑树在业界应用很广泛,比如 Java中的`TreeMap`,`JDK 1.8`中的`HashMap`,C++ STL 中的`map`和`set` 底层均是基于红黑树结构实现的.
- 虽然红黑树实现很复杂,但考虑到红黑树是一种被广泛应用的数据结构，所以我们很有必要去弄懂.

# 2.红黑树定义及性质
`红黑树(RBT)`的定义：它或者是一颗`空树`,或者是具有一下性质的`二叉查找树`:
```
1.节点非红即黑。

2.根节点是黑色。

3.所有NULL结点称为叶子节点，且认为颜色为黑。

4.所有红节点的子节点都为黑色。

5.从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点。
```
红黑树的基本操作和其他树形结构一样,一般都包括`查找,插入,删除等`操作.红黑树举例:
![title](https://leanote.com/api/file/getImage?fileId=5e844463ab64411b51002411)
# 3.旋转操作
旋转操作分为`左旋`和`右旋`,左旋是将某个节点旋转为其右孩子的左孩子,而右旋是节点旋转为其左孩子的右孩子.看图就很容易明白:
![title](https://leanote.com/api/file/getImage?fileId=5e8445f2ab64411d500024ef)
# 4.插入操作
红黑树的插入过程和二叉查找树插入过程基本类似,不同的地方在于,红黑树插入新节点后,需要进行调整,以满足红黑树的性质.为了调整简单,`插入节点应该红色的`,此时通过变色和旋转调整,使其满足红黑树的所有性质即可.
接下来,将分析插入红色节点后红黑树的调整情况.这里假设要插入的节点为 N,N 的父节点为 P,祖父节点为 G,叔叔节点为 U.插入红色节点后,会出现5种情况,分别如下:
## 4.1 情况一
- ` 插入的新节点 N 是红黑树的根节点`,
- 这种情况下，我们把节点 N 的颜色由红色变为黑色,所有性质满足,结束.
## 4.2 情况二
- `N 的父节点是黑色`,
- 这种情况下,性质4(每个红色节点必须有两个黑色的子节点)和性质5没有受到影响,不需要调整.
![title](https://leanote.com/api/file/getImage?fileId=5e844edcab64411d500026b5)
## 4.3 情况三
- `N 的父节点是红色（节点 P 为红色,其父节点必然为黑色),叔叔节点U也是红色`
- 由于 P 和 N 均为红色,所以性质4被打破,此时需要进行调整。这种情况下,先将 P 和 U 的颜色染成黑色,再将 G 的颜色染成红色。此时经过 G的路径上的黑色节点数量不变,性质5仍然满足。
- 但需要注意的是 G 被染成红色后,可能会和它的父节点形成连续的红色节点,此时,`如果P为根节点,那么直接将其变为黑丝,结束;否则需要将P当作新的插入点N而不断的递归向上调整`,而这过程中,则有可能出现其他情况。
![title](https://leanote.com/api/file/getImage?fileId=5e845014ab64411d500026ea)

## 4.4 情况四
- `N 的父节点为红色，叔叔节点为黑色。节点 N 是 P 的右孩子，且节点 P 是 G 的左孩子。`
- 此时先对节点 P 进行左旋,调整 N 与 P 的位置。接下来按照情况五进行处理,以恢复性质4。
![title](https://leanote.com/api/file/getImage?fileId=5e84553aab64411d500027fc)
## 4.5 情况五
- `N 的父节点为红色;叔叔节点为黑色。N 是 P 的左孩子;且节点 P 是 G 的左孩子。`
- 此时对 G 进行右旋，调整 P 和 G 的位置，并互换颜色。经过这样的调整后，性质4被恢复，同时也未破坏性质5。
![title](https://leanote.com/api/file/getImage?fileId=5e8455a4ab64411b51002775)

## 4.6 插入总结
- 上面五种情况中,情况一和情况二比较简单,情况三、四、五稍复杂。
- 但如果细心观察,会发现这三种情况的`区别在于叔叔节点的颜色,如果叔叔节点为红色,直接变色即可。如果叔叔节点为黑色,则需要先旋转,再交换颜色。`
- 当把这三种情况的图画在一起就区别就比较容易观察了,如下图:
![title](https://leanote.com/api/file/getImage?fileId=5e845667ab64411d50002834)

# 5.删除操作
##5.1 删除说明
 - 相较于插入操作,删除操作更为复杂. 
- 普通的二叉搜索树在删除时, 确定待删除节点有几个孩子; 如果有两个孩子, 不能直接删除该节点。而是要先找到该节点的前驱(该节点左子树中最大的节点)或者后继(该节点右子树中最小的节点), 然后将前驱或者后继的值复制到要删除的节点中, 最后再将前驱或后继删除. 由于前驱和后继至多只有一个孩子节点, 这样我们就`把原来要删除的节点有两个孩子的问题转化为只有一个孩子节点的问题`, 问题就被简化了。我们并不关心最终被删除的节点是否是我们开始想要删除的那个节点, 只要节点里的值最终被删除就行了, 至于树结构如何变化,这个并不重要.
- 注意,下面所说的`红黑树的删除`, 全是指的是删除`替代点`,可能是本应删除节点本身,或者其前驱节点,或者后继节点, 只要其满足至多有一个子节点就行(就相当于满足这个条件,就可以代替人家去死!).

- 红黑树删除操作的复杂度在于删除节点的颜色:
- **当删除的节点是红色时**, `直接拿其孩子节点(孩子节点至多只有一个,没有孩子则直接补NULL)补空位即可。`因为删除红色节点, 性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点）仍能够被满足。
- **当删除的节点是黑色时**，那么所有经过该节点的路径上的黑节点数量少了一个，破坏了性质5。`如果该节点的孩子为红色，直接拿孩子节点替换被删除的节点，并将孩子节点染成黑色，即可恢复性质5`。但如果孩子节点为黑色，处理起来就要复杂的多。分为6种情况，下面会展开说明。

- 在展开说明之前，我们先做一些假设，方便说明。
- 这里假设`最终被删除的节点为X(至多只有一个孩子节点), 其孩子节点为N，X的兄弟节点为S，S的左节点为 SL，右节点为 SR。`
- 接下来讨论是建立在节点 X 被删除，节点 N 替换X的基础上进行的。这里说明把被删除的节点X特地拎出来说一下的原因是防止读者误以为节点N会被删除，不然后面就会看不明白。

## 5.2 最终被删除点的子节点为黑的六种特殊情况:
### 5.2.1 情况一
`N 是新的根。`
在这种情形下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所以性质都保持着。
比如,要删除的节点 X 是根节点，且左右孩子节点均为空节点，此时将节点 X 用空节点替换完成删除操作。
### 5.2.2 情况二
`S 为红色, 其他节点为黑色。`
这种情况下可以对 N 的父节点进行左旋操作，然后互换 P 与 S 颜色。但这并未结束，经过节点 P 和 N 的路径删除前有3个黑色节点（P -> X -> N），现在只剩两个了（P -> N）。比未经过 N 的路径少一个黑色节点，性质5仍不满足，还需要继续调整。不过此时可以按照情况四、五、六进行调整。

![title](https://leanote.com/api/file/getImage?fileId=5e8464e2ab64411b51002aa4)

### 5.2.3 情况三
`N 的父节点P，兄弟节点 S 和 S 的孩子节点均为黑色。`
这种情况下可以简单的把 S 染成红色，所有经过 S 的路径比之前少了一个黑色节点，这样经过 N 的路径和经过 S 的路径黑色节点数量一致了。但经过 P 的路径比不经过 P 的路径少一个黑色节点，此时需要从情况一开始对 P 进行平衡处理(即把P当作新的N,再看属于那种情况)。
![title](https://leanote.com/api/file/getImage?fileId=5e846526ab64411d50002b28)

### 5.2.4 情况四
`N 的父节点P为红色，叔叔节点为黑色。节点 N 是 P 的左孩子，且叔叔节点 S的子节点Sl,Sr全为黑。`
此时先P和S变色,对节点 P 进行左旋，调整 N 与 P 的位置。接下来按照情况五进行处理，以恢复性质4。
![title](https://leanote.com/api/file/getImage?fileId=5e84664bab64411d50002b67)
上面图只画出了变色(变色后,就成为了情况二的一种特殊情况,此时可以通过左旋变为情况五),左旋未画出来.
### 5.2.5 情况五
`S 为黑色，S 的左孩子为红色，右孩子为黑色。N 的父节点颜色可红可黑，且 N 是 P 左孩子。`
这种情况下对 S 进行右旋操作，并互换 S 和 SL 的颜色。此时，所有路径上的黑色数量仍然相等，N 兄弟节点的由 S 变为了 SL，而 SL 的右孩子变为红色。接下来我们到情况六继续分析。

![title](https://leanote.com/api/file/getImage?fileId=5e84669bab64411b51002af1)

### 5.2.6 情况六
`S 为黑色，S 的右孩子为红色。N 的父节点颜色可红可黑，且 N 是其父节点左孩子。`

这种情况下，我们对 P 进行左旋操作，并互换 P 和 S 的颜色，并将 SR 变为黑色。因为 P 变为黑色，所以经过 N 的路径多了一个黑色节点，经过 N 的路径上的黑色节点与删除前的数量一致。对于不经过 N 的路径，则有以下两种情况：

- 该路径经过 N 新的兄弟节点 SL ，那它之前必然经过 S 和 P。而 S 和 P 现在只是交换颜色，对于经过 SL 的路径不影响。
- 该路径经过 N 新的叔叔节点 SR，那它之前必然经过 P、 S 和 SR，而现在它只经过 S 和 SR。在对 P 进行左旋，并与 S 换色后，经过 SR 的路径少了一个黑色节点，性质5被打破。另外，由于 S 的颜色可红可黑，如果 S 是红色的话，会与 SR 形成连续的红色节点，打破性质4（每个红色节点必须有两个黑色的子节点）。此时仅需将 SR 由红色变为黑色即可同时恢复性质4和性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。）。
![title](https://leanote.com/api/file/getImage?fileId=5e8466f1ab64411d50002b87)
## 5.3 删除总结
 - 把所有情况对应的图形画在一起,可以发现一定的规律:
- 情况二转成了情况四,五,六(主要看SL的左右子节点的颜色)
- 情况三可以转成情况二,三,四,五,六(注意,情况三变色后虽然看起来和情况二一样,但是是不同的,因为情况二P左右是不平衡的,而情况三P左右是平衡的,但经过P的路径上,黑点数目减少了一).
- 情况五可以转成情况六

![title](https://leanote.com/api/file/getImage?fileId=5e846737ab64411d50002b92)
# 6.C++代码实现RBT
插入时看"叔叔",删除时看"兄弟及其孩子",红黑树的C++实现,以及红黑树的控制台可视化:
```
#include<iostream>
#include<string>

#include<vector>
#include<algorithm>

#include<stack>
#include<queue>

using namespace std;
enum COLOR
{  /*The default value of the first enumeration member is 
    0 of the integer type, and the value of the subsequent 
	enumeration member is 1 added to the previous member*/
	RED,BLACK 
};
enum DIRECTION
{
	LEFT,RIGHT
};

template<class KEY,class VAL>
class RB_Node
{
public:
	RB_Node<KEY, VAL>()  //<KEY, VAL> can be removed!
	{
		wpos = 0;
		RB_COLOR = BLACK;
		right = NULL;
		left = NULL;
		parent = NULL;
	}
	RB_Node(KEY key, VAL val,COLOR color = RED)
	{
		this->key = key;
		this->val = val;

wpos = 0;
		RB_COLOR = color;
		right = NULL;
		left = NULL;
		parent = NULL;
	}

KEY key;
	VAL val;
	int wpos;

COLOR RB_COLOR; 
	RB_Node<KEY, VAL> *right; //<KEY, VAL> can't be removed here!
	RB_Node<KEY, VAL> *left;
	RB_Node<KEY, VAL> *parent;

};

template<class KEY,class VAL>
class RB_Tree
{
//private:
public:
	RB_Tree<KEY, VAL>(const RB_Tree<KEY, VAL> &input) { };
	const RB_Tree<KEY, VAL>& operator=(const RB_Tree<KEY, VAL> &input) { };

RB_Node<KEY, VAL> *nil;
	RB_Node<KEY, VAL> *rb_root;

public:
	/*constrtct function*/
	RB_Tree<KEY, VAL>()
	{  
		nil = new RB_Node<KEY, VAL>();
		rb_root = nil;

nil->right = rb_root;
		nil->left = rb_root;
		nil->parent = rb_root;
		nil->RB_COLOR = BLACK;
	}
	/*Determine whether the red black tree is empty*/
	bool empty() {
		return rb_root == nil;
	}
	/*find the key by recursion*/
	RB_Node<KEY,VAL>* find(KEY key,RB_Node<KEY, VAL>* node)
	{
		if (key == node->key) return node;
		else if (key < node->key) return find(key, node->left);
		else return find(key, node->right);
		//if not find the target
		return nil;
	}
	/*find the key by iteration*/
	RB_Node<KEY, VAL>* find(KEY key)
	{
		RB_Node<KEY, VAL>* curr = rb_root;
		while (curr != nil)
		{
			if (key == curr->key) return curr;
			else curr = key < curr->key ? curr->left : curr->right;
		}
		return nil;
	}
	/*insertion function,RB_Nodes with the same value are not allowed*/
	bool insert(KEY key, VAL val)
	{
		RB_Node<KEY, VAL> *insert_point = nil;
		RB_Node<KEY, VAL> *curr = rb_root;
		while(curr != nil)
		{
			insert_point = curr;
			if (key == curr->key) return false;//insertion failed!
			else curr = key < curr->key ? curr->left : curr->right;
		}
		RB_Node<KEY, VAL> *insert_node = new RB_Node<KEY, VAL>(key, val, RED);
		//insert_node->key = key;
		//insert_node->val = val;
		//insert_node->RB_COLOR = RED;
		insert_node->right = nil;
		insert_node->left = nil;

//empty RB_Tree,the insert RB_Node become rb_root
		if (insert_point == nil){
			/*case 1: empty RB_Tree*/
			rb_root = insert_node;
			rb_root->RB_COLOR = BLACK;

rb_root->parent = nil; //it is necessary.

nil->left = rb_root;
			nil->right = rb_root;
			nil->parent = rb_root;
			return true; 
		}
		else{
			if (key < insert_point->key) insert_point->left = insert_node;
			else insert_point->right = insert_node;
			insert_node->parent = insert_point;
		}
		//Adjust the red black tree to maintain its inherent properties
		/*case 2: insert_node's parent is black,do nothing!*/
		while (insert_node->parent->RB_COLOR == RED) //if insert_node's parent is red,then adjusting is needed!
		{   /*case 3,4,5:depending on insert_node's uncle!!!*/

if (insert_node->parent == insert_node->parent->parent->left)
			{
				/*case 3:uncle's color is red,just convert the color*/
				if (insert_node->parent->parent->right->RB_COLOR == RED)
				{
					insert_node->parent->RB_COLOR = BLACK;
					insert_node->parent->parent->RB_COLOR = RED;
					insert_node->parent->parent->right->RB_COLOR = BLACK;
					insert_node = insert_node->parent->parent;
				}
				else
				{   /*case 4 or 5:
					depending on insert_node is left child or right!*/
					
					//case 4:if right child,then need left rotate insert_node,turning into case 5 finally.
					if (insert_node == insert_node->parent->right)
					{
			            /*rotate(insert_node->parent, LEFT);
						insert_node = insert_node->left;*/
						
						insert_node = insert_node->parent;
						rotate(insert_node,LEFT);
						
					}
					//case 5:just right rotate insert_node's  grandparent.
					else
					{
						insert_node->parent->parent->RB_COLOR = RED;
						insert_node->parent->RB_COLOR = BLACK;
						rotate(insert_node->parent->parent, RIGHT);
					}
				}
			}
			else //just the same in opposite directions
			{
				//case 3
				if (insert_node->parent->parent->left->RB_COLOR == RED)
				{
					insert_node->parent->RB_COLOR = BLACK;
					insert_node->parent->parent->RB_COLOR = RED;
					insert_node->parent->parent->left->RB_COLOR = BLACK;
					insert_node = insert_node->parent->parent;
				}
				else
				{
					//case 4,turned into case 5;
					if (insert_node == insert_node->parent->left)
					{
						insert_node = insert_node->parent;
						rotate(insert_node, RIGHT);
						/*rotate(insert_node->parent, RIGHT);
						insert_node = insert_node->right;*/
					}
					//case 5
					else
					{
						insert_node->parent->parent->RB_COLOR = RED;
						insert_node->parent->RB_COLOR = BLACK;
						rotate(insert_node->parent->parent, LEFT);
					}
				}
			}
		}
		rb_root->RB_COLOR = BLACK;
		return true;
	}

bool remove(KEY key)
	{
		RB_Node<KEY,VAL>* delete_point = find(key);
		if (delete_point == nil)
		{
			return false;
		}
		if (delete_point->left != nil && delete_point->right != nil)
		{
			RB_Node<KEY,VAL>* successor = findSuccessor(delete_point);
			delete_point->val = successor->val;
			delete_point->key = successor->key;
			delete_point->wpos = successor->wpos;
			delete_point = successor;
		}

RB_Node<KEY,VAL>* delete_point_child;
		if (delete_point->right != nil)
		{
			delete_point_child = delete_point->right;
		}
		else if (delete_point->left != nil)
		{
			delete_point_child = delete_point->left;
		}
		else
		{
			delete_point_child = nil;
		}
		delete_point_child->parent = delete_point->parent;

if (delete_point->parent == nil)//delete root node  
		{
			rb_root = delete_point_child;
			nil->parent = rb_root;
			nil->left = rb_root;
			nil->right = rb_root;
		}
		else if (delete_point == delete_point->parent->right)
		{
			delete_point->parent->right = delete_point_child;
		}
		else
		{
			delete_point->parent->left = delete_point_child;
		}
		if (delete_point->RB_COLOR == BLACK && !(delete_point_child == nil && delete_point_child->parent == nil))
		{
			//DeleteFixUp(delete_point_child);
			//remove the delete_point,and given delete_point_child,adjusting RB_Tree;
			while (delete_point_child != rb_root && delete_point_child->RB_COLOR == BLACK)
			{
				if (delete_point_child == delete_point_child->parent->left)
				{
					RB_Node<KEY, VAL> *brother = delete_point_child->parent->right;
					//case 2
					if (brother->RB_COLOR == RED)
					{
						brother->RB_COLOR = BLACK;
						delete_point_child->parent->RB_COLOR = RED;
						rotate(delete_point_child->parent, LEFT);
					}
					else
					{
						//case 3 and 4
						if (brother->left->RB_COLOR == BLACK && brother->right->RB_COLOR == BLACK)
						{
							brother->RB_COLOR = RED;
							delete_point_child = delete_point_child->parent;
						}
						//case 5
						else if (brother->right->RB_COLOR == BLACK)
						{
							brother->RB_COLOR = RED;
							brother->left->RB_COLOR = BLACK;
							rotate(brother, RIGHT);
						}
						else if (brother->right->RB_COLOR == RED)
						{
							brother->RB_COLOR = delete_point_child->parent->RB_COLOR;
							delete_point_child->parent->RB_COLOR = BLACK;
							brother->right->RB_COLOR = BLACK;
							rotate(delete_point_child->parent, LEFT);
							delete_point_child = rb_root; //
						}
					}
				}
				else
				{
					RB_Node<KEY, VAL>* brother = delete_point_child->parent->left;
					if (brother->RB_COLOR == RED)
					{
						brother->RB_COLOR = BLACK;
						delete_point_child->parent->RB_COLOR = RED;
						rotate(delete_point_child->parent, RIGHT);
					}
					else
					{
						if (brother->left->RB_COLOR == BLACK && brother->right->RB_COLOR == BLACK)
						{
							brother->RB_COLOR = RED;
							delete_point_child = delete_point_child->parent;
						}
						else if (brother->left->RB_COLOR == BLACK)
						{
							brother->RB_COLOR = RED;
							brother->right->RB_COLOR = BLACK;
							rotate(brother, LEFT);
						}
						else if (brother->left->RB_COLOR == RED)
						{
							brother->RB_COLOR = delete_point_child->parent->RB_COLOR;
							delete_point_child->parent->RB_COLOR = BLACK;
							brother->left->RB_COLOR = BLACK;
							rotate(delete_point_child->parent, RIGHT);
							delete_point_child = rb_root;
						}
					}
				}
			}
		}

nil->parent = rb_root;
		//if delete_child is red,just turn into black;
		delete_point_child->RB_COLOR == BLACK;

rb_root->RB_COLOR = BLACK;
		delete delete_point;
		return true;
	}

/*level traverse to show the RB_Tree, including RB_Tree visual character display */
	void levelTraverseVisual()
	{
		if (this->rb_root == nil) return;
		long int pos = 0;
		setWidthPos(rb_root, pos);

queue<RB_Node<KEY, VAL>*> que;
		que.push(rb_root);
		//queue<RB_Node<KEY, VAL>*> temp_que;
		queue<int> temp_que;
		RB_Node<KEY, VAL>* p = rb_root;
		int node_pos = 0;
		int right_dis = 0;
		int cursor_pos = 0;

int node_sum = 1;
		int child_sum = 0;

int val_len = 4;
		while (!que.empty())
		{
			p = que.front();
			que.pop();
			--node_sum;
			node_pos = p->wpos;
			if (p->right != nil) right_dis = p->right->wpos;
			if (p->left != nil)
			{
				for (int i = cursor_pos; i <= p->left->wpos + (to_string(p->left->key).size() + 3) / 2; ++i)
				{
					cout << " ";
					++cursor_pos;
				}
				//to print "|";
				temp_que.push(cursor_pos - 1);
				for (int i = cursor_pos; i < node_pos; ++i)
				{
					cout << "_";
					++cursor_pos;
				}
			}
			else
			{
				for (int i = cursor_pos; i < node_pos; ++i)
				{
					cout << " ";
					++cursor_pos;
				}
			}

/*string s = p->RB_COLOR == RED ? "R" : "B";
			std::cout << "<" << p->key << s << ">";*/
			if (p->RB_COLOR == RED)
			{
				std::cout << "(" << p->key  << "R)";
			}
			else 
			{
				std::cout << "<" << p->key << "B>";
			}

cursor_pos += to_string(p->key).size() + 3;
			if (p->right != nil)
			{
				for (int i = cursor_pos; i < p->right->wpos + (to_string(p->right->key).size() + 3) / 2; ++i)
				{
					cout << "_";
					++cursor_pos;
				}
				//to print "|";
				temp_que.push(cursor_pos);
			}

if (p->left != nil) {
				que.push(p->left);
				++child_sum;
			}
			if (p->right != nil) {
				que.push(p->right);
				++child_sum;
			}

//next line,cout endl;
			if (node_sum == 0)
			{
				std::cout << endl;// << endl;
				for (int i = 0; (!temp_que.empty()) && i <= (int)temp_que.back(); ++i)
				{
					if (i == temp_que.front())
					{
						cout << "|";
						temp_que.pop();
					}
					else
					{
						cout << " ";
					}
				}
				cout << endl;
				cursor_pos = 0;

node_sum = child_sum;
				child_sum = 0;
			}
		}
	}

void preOrderTraverse(RB_Node<KEY, VAL>* node)
	{
		//if (node == nil)
		//{
		//	return;
		//}
		//else
		//{
		//	string s = node->RB_COLOR == RED ? "R" : "B";
		//	cout << node->key << s << endl;
		//	preOrderTraverse(node->left);
		//	preOrderTraverse(node->right);
		//}

if (this->rb_root == nil) return;

stack<RB_Node<KEY, VAL>*> stk;
		stk.push(rb_root);

RB_Node<KEY, VAL>* p = rb_root;
		while (!stk.empty())
		{
			p = stk.top();
			stk.pop();
			string s = p->RB_COLOR == RED ? "R" : "B";
			std::cout << p->key << ":" << s << endl;
			if (p->right != nil) stk.push(p->right);
			if (p->left != nil) stk.push(p->left);
		}
	}

private:
	bool rotate(RB_Node<KEY,VAL>* node, DIRECTION direction)
	{
		/*left rotate*/
		if (direction == LEFT)
		{
			if (node == nil || node->right == nil) return false; //can't rotate!
			
			RB_Node<KEY,VAL> *right_node = node->right;
			
			node->right = right_node->left;

if (right_node->left != nil) right_node->left->parent = node;//shoulde be "=node" rather than "=node->left";
			else right_node->left->parent = rb_root; //can be removed,because nil's parent is defined as root.
			
			//if rotate node is root,then right_node become root.
			if (node == rb_root)
			{
				rb_root = right_node;
				rb_root->parent = nil;

nil->left = rb_root;
				nil->right = rb_root;
				nil->parent = rb_root;
				
				//watch out!!! Don't forget about this!!!
				right_node->left = node;
				node->parent = right_node;
			}
			else
			{
				if (node == node->parent->left)
				{
					node->parent->left = right_node;
				}
				else
				{
					node->parent->right = right_node;
				}
				//handle right_node and node's parents.
				right_node->parent = node->parent;

right_node->left = node;
				node->parent = right_node;
			}
		}
		/*right rotate*/
		else
		{
			if (node == nil || node->left == nil) return false; 
			RB_Node<KEY, VAL> *left_node = node->left;

node->left = left_node->right;
			if (left_node->right != nil) left_node->right->parent = node;//shoulde be "=node" rather than "=node->left";
			
			if (node == rb_root)
			{
				rb_root = left_node;
				rb_root->parent = nil;

nil->left = rb_root;
				nil->right = rb_root;
				nil->parent = rb_root;

//watch out!!! Don't forget about this!!!
				left_node->right = node;
				node->parent = left_node;

}
			else
			{
				if (node == node->parent->left) node->parent->left = left_node;
				else node->parent->right = left_node;

left_node->parent = node->parent;

left_node->right = node;
				node->parent = left_node;
			}
		}
		return true;
	}

RB_Node<KEY,VAL>* findPredecessor(RB_Node<KEY, VAL>* node)
	{
		if (node == nil) return nil;
		RB_Node *predecessor = node->left;
		if (predecessor == nil) return nil;
		else {
			while (predecessor->right != nil)
			{
				predecessor = predecessor->right;
			}
		}
		return predecessor;
	}

RB_Node<KEY, VAL>* findSuccessor(RB_Node<KEY, VAL>* node)
	{
		if (node == nil)       //null node has no successor  
		{
			return nil;
		}
		RB_Node<KEY,VAL>* result = node->right;   //get node's right node  
		while (result != nil && result->left!=nil)        //try to find node's right subtree's left most node  
		{
			result = result->left;
		}                              
		
		//after while loop result==null or result's left child is null  
		if (result == nil && node->left!=nil)
		{
			result = node->left;
		}

//if (result == nil)
		//{
		//	RB_Node<KEY,VAL>* index = node->parent;
		//	result = node;
		//	while (index != nil && result == index->right)
		//	{
		//		result = index;
		//		index = index->parent;
		//	}
		//	result = index;         //first parent's left or null  
		//}

cout << endl;
		return result;
	}

int getHeight(RB_Node<KEY, VAL> *node)
	{
		int h = 0;
		if (node == nil) return 0;
		h = 1 + max(getHeight(node->left), getHeight(node->right));
		return h;
	}

int getWidth(RB_Node<KEY, VAL> *node)
	{
		if (node == nil) return 0;
		return 1 + getWidth(node->left) + getWidth(node->right);
	}

/*inOrderTraverse to set horizontal position*/
	void setWidthPos(RB_Node<KEY,VAL> *node,long int &pos)
	{
		if (node == nil) return;
		
		setWidthPos(node->left,pos);
		node->wpos = pos;
		//increased by length of key
		pos+=to_string(node->key).size() + 3;
		setWidthPos(node->right,pos);
	}
};

int main()
{
	cout << "The Red Black Tree is visualized as follows:" << endl;

RB_Tree<int, int> rbtree;
	vector<int> v = { -3,4,602313,-1,223760,1000,23,-43,76,2,9,700,67 };

for (int i = 1; i<=19; ++i)
	{
		v.push_back(i);
	}

random_shuffle(v.begin(), v.end());

for (unsigned int i = 0; i < v.size(); ++i)
	{
		rbtree.insert(v[i],i);
		//cout << "insert "<< v[i] <<":" << i<< endl;   //添加结点
	}

rbtree.levelTraverseVisual();

//rbtree.preOrderTraverse(rbtree.rb_root);

rbtree.remove(10);
	rbtree.remove(15);
	rbtree.levelTraverseVisual();
	
	system("pause");
	return 0;
}
```
# 7.参考链接
- https://www.360kuai.com/pc/90d78fa6c732d1176?cota=3&kuai_so=1&sign=360_57c3bbd1&refer_scene=so_1

- https://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html

- 源码 https://blog.csdn.net/v_JULY_v/article/details/6285620
- 源码:二叉树可视化
- https://blog.csdn.net/copica/article/details/39291141

lee-romantic 's Blog

导航

最近发表

友情链接