红黑树复习

介绍、

红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。是一种对于AVL树和二叉查找树的改进，即使在最坏情况下都具有良好的时间复杂度 O（logn），是一种非常优秀的数据结构，广泛应用在很多地方，例如操作系统内核的进程队列。

特点、

（1）每个结点要么是红的要么是黑的。

（2）根结点是黑的。 

（3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。 

（4）如果一个结点是红的，那么它的两个儿子都是黑的。 

（5）对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度，从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为 O(logn) 这一结论成立的原因。

花了差不多一周时间区琢磨了红黑树，真tmd太难了！！！！下面的红黑树代码是我仿照SGI STL的红黑树源码简化过写的，但是有问题！！！插入操作经过验证没问题，但是删除操作有问题！！！我明明照抄着SGI STL的源码都有问题，检查了几遍没有抄错，然后debug后发现在删除操作中有空指针问题，但是我解决不了，抄都费劲何况还看不懂，歪日。

#ifndef _RB_TREE_CPP_
#define _RB_TREE_CPP_

#include<cassert>
#include<memory>

using std::swap,std::construct_at, std::destroy_at;


//声明红黑树的结构体
template <class Key, class Value>
class rb_tree;

//声明红黑树迭代器的结构体
template <class Key, class Value>
class _rb_tree_iterator;
//声明pair类型的结构体

template <class Key, class Value>
struct pair;

//声明红黑树节点的结构体
template <class Key, class Value>
struct _rb_tree_node;


//红色为0，黑色为1
bool red = false, black = true;

//pair类型,存储键值对
template<class key, class Value>
struct pair
{
	key key_field;
	Value value_field;
};

//红黑树节点类型
template<class Key, class Value>
struct _rb_tree_node
{
	bool color;         //节点颜色
	_rb_tree_node<Key, Value>* parent; //父指针
	_rb_tree_node<Key, Value>* left;   //左孩子指针
	_rb_tree_node<Key, Value>* right;  //右孩子指针
	pair<Key, Value> _pair;  //pair类型
};


//红黑树迭代器
template<class Key, class Value>
struct _rb_tree_iterator
{
public:

	friend class rb_tree<Key, Value>;

	using _pnode = _rb_tree_node<Key, Value>*;

	~_rb_tree_iterator()noexcept {}

	_rb_tree_iterator(_pnode pt = nullptr)noexcept :node(pt) {}

	_rb_tree_iterator(const _rb_tree_iterator& rhs)noexcept :node(rhs.node) {}

	const _rb_tree_iterator& operator=(const _rb_tree_iterator& rhs) noexcept
	{
		if (this != &rhs)
		{
			node = rhs.node;
		}
		return *this;
	}

	pair<Key, Value>& operator*() const noexcept
	{
		assert(node);
		return node->_pair;
	}

	pair<Key, Value>* operator->()const noexcept
	{
		assert(node);
		return &(operator*());
	}

        //迭代器自增，重点！！！
	_rb_tree_iterator& operator++()noexcept
	{
		//如果有右子树，那么就是右子树的最左边的节点，即最大节点
		if (node->right)
		{
			node = node->right;
			while (node->left)
			{
				node = node->left;
			}
		}
		else
		{
			_pnode y = node->parent;
			while (node == y->right)
			{
				node = y;
				y = y->parent;
			}
			if (node->right != y)
			{
				node = y;
			}
		}
		return *this;
	}

	const _rb_tree_iterator operator++(int) noexcept
	{
		_rb_tree_iterator tmp = *this;
		++(*this);
		return tmp;
	}

        //迭代器自减，重点！！！
	_rb_tree_iterator& operator--()noexcept
	{
		if (node->color == red && node->parent->parent == node)
		{
			node = node->right;
		}
		else if (node->left)
		{
			_pnode y = node->left;
			while (y->right)
			{
				y = y->right;
			}
			node = y;
		}
		else
		{
			_pnode y = node->parent;
			while (node == y->left)
			{
				node = y;
				y = y->parent;
			}
			node = y;
		}
		return *this;
	}

	const _rb_tree_iterator operator--(int) noexcept
	{
		_rb_tree_iterator tmp = *this;
		--(*this);
		return tmp;
	}

	bool operator==(const _rb_tree_iterator& rhs)const noexcept
	{
		return node == rhs.node;
	}

	bool operator!=(const _rb_tree_iterator& rhs)const noexcept
	{
		return node != rhs.node;
	}

private:
	_pnode node;
};


//红黑树类型
template<class Key, class Value>
class rb_tree
{
public:

	using iterator = _rb_tree_iterator<Key, Value>;

	rb_tree() noexcept :node_count(0)
	{
		header = _allocate_node();
		header->parent = nullptr;
		header->left = header;
		header->right = header;
		header->color = red;
	}

	rb_tree(const rb_tree& rhs) = delete;

	rb_tree& operator = (const rb_tree& rhs) = delete;

	~rb_tree()noexcept
	{
		clear();
		free(header);
	}


	iterator begin()const noexcept
	{
		return iterator(header->left);
	}

	iterator end()const noexcept
	{
		return iterator(header);
	}

	bool empty()const noexcept
	{
		return node_count == 0;
	}

	size_t size() const noexcept
	{
		return node_count;
	}

	iterator max() const noexcept
	{
		_pnode x = header->parent;
		if (x)
		{
			x = _maximum(x);
		}
		return iterator(x);
	}

	iterator min() const noexcept
	{
		_pnode x = header->parent;
		if (x)
		{
			x = _minimum(x);
		}
		return iterator(x);
	}

	void clear() noexcept
	{
		_clear(header->parent);
		header->parent = nullptr;
		header->left = header;
		header->right = header;
		node_count = 0;
	}

	iterator insert(const Key& k, const Value& v) noexcept
	{
		return insert(pair<Key, Value>(k, v));
	}

	iterator insert(const pair<Key, Value>& v) noexcept
	{
		_pnode y = header;
		_pnode x = header->parent;
		bool _comp = true;
		while (x != nullptr)                //从根节点开始往下找插入点
		{
			y = x;
			_comp = v.key_field < x->_pair.key_field;
			x = _comp ? x->left : x->right;
		}

		iterator j = iterator(y);   //循环结束后y是插入点的父节点，必然是叶子节点
		if (_comp)                   //表示遇到大的节点，插入点应该在y的左边
		{
			if (j == begin())
			{
				return _insert_(x, y, v);
			}
			else
			{
				--j;
			}
		}

		//插入点在y右边
		if (j->key_field < v.key_field)
		{
			return _insert_(x, y, v);
		}

		//进行到这里说明有key重复的节点,就析构value值，重新构造
		destroy_at(&j->value_field);
		construct_at(&j->value_field, v.value_field);

		return end();
	}


	iterator find(const Key& key) const noexcept
	{
		_pnode x = header->parent;
		while (x != nullptr)
		{
			if (x->_pair.key_field < key)
			{
				x = x->right;
			}
			else if (x->_pair.key_field > key)
			{
				x = x->left;
			}
			else
			{
				return iterator(x);
			}
		}
		return end();
	}

	Value& operator[](const Key& key) noexcept
	{
		iterator j = find(key);
		assert(j != end());
		return j->value_field;
	}

        //这里有问题，但是解决不了。。。。。。
	void erase(iterator position) noexcept
	{
		_pnode y = _rb_tree_rebalance_for_erase(position.node, header->parent, header->left, header->right);
		_destroy_node(y);
		--node_count;
	}


	bool is_rb_tree() const noexcept
	{
		return _is_rb_tree();
	}



protected:

	using _pnode = _rb_tree_node<Key, Value>*;


	void _clear(_pnode x) noexcept
	{
		if (x == nullptr)
		{
			return;
		}
		_clear(x->left);
		_clear(x->right);
		_destroy_node(x);
	}

	_pnode _allocate_node() noexcept
	{
		_pnode pt = static_cast<_pnode>(calloc(1, sizeof(_rb_tree_node<Key, Value>)));
		assert(pt);
		return pt;
	}

	_pnode _create_node(const Key& k, const Value& v) noexcept
	{
		_pnode pt = _allocate_node();
		construct_at(&pt->_pair.value_field, v);
		construct_at(&pt->_pair.key_field, k);
		return pt;
	}

	void _destroy_node(_pnode x) noexcept
	{
		destroy_at(&x->_pair.value_field);
		destroy_at(&x->_pair.key_field);
		free(x);
	}

	//x_为新值插入点,y_为插入点父节点,v为值
	iterator _insert_(_pnode x_, _pnode y_, const pair<Key, Value>& v) noexcept
	{
		_pnode x = x_, y = y_, z = nullptr;
		if (y == header || x != nullptr || v.key_field < y->_pair.key_field)
		{
			z = _create_node(v.key_field, v.value_field);
			y->left = z;
			if (y == header)
			{
				header->parent = z;
				header->right = z;
			}
			else if (y == header->left)
			{
				header->left = z;
			}
		}
		else
		{
			z = _create_node(v.key_field, v.value_field);
			y->right = z;
			if (y == header->right)
			{
				header->right = z;
			}
		}
		z->parent = y;
		z->left = nullptr;
		z->right = nullptr;
		_rb_tree_rebalance(z, header->parent);
		++node_count;
		return iterator(z);
	}

	void _rb_tree_rebalance(_pnode x, _pnode& root) noexcept
	{
		x->color = red;  //新节点一定为红
		while (x != root && x->parent->color == red)
		{
			if (x->parent == x->parent->parent->left)
			{
				_pnode y = x->parent->parent->right;
				if (y && y->color == red)
				{
					x->parent->color = black;
					y->color = black;
					x->parent->parent->color = red;
					x = x->parent->parent;
				}
				else
				{
					if (x == x->parent->right)
					{
						x = x->parent;
						_rb_tree_rotate_left(x, root);
					}
					x->parent->color = black;
					x->parent->parent->color = red;
					_rb_tree_rotate_right(x->parent->parent, root);
				}
			}
			else
			{
				_pnode y = x->parent->parent->left;
				if (y && y->color == red)
				{
					x->parent->color = black;
					y->color = black;
					x->parent->parent->color = red;
					x = x->parent->parent;
				}
				else
				{
					if (x == x->parent->left)
					{
						x = x->parent;
						_rb_tree_rotate_right(x, root);
					}
					x->parent->color = black;
					x->parent->parent->color = red;
					_rb_tree_rotate_left(x->parent->parent, root);
				}
			}
		}
		root->color = black;
	}

	void _rb_tree_rotate_left(_pnode x, _pnode& root) noexcept
	{
		_pnode y = x->right;
		x->right = y->left;
		if (y->left)
		{
			y->left->parent = x;
		}
		y->parent = x->parent;
		if (x == root)
		{
			root = y;
		}
		else if (x == x->parent->left)
		{
			x->parent->left = y;
		}
		else
		{
			x->parent->right = y;
		}
		y->left = x;
		x->parent = y;
	}

	void _rb_tree_rotate_right(_pnode x, _pnode& root) noexcept
	{
		_pnode y = x->left;
		x->left = y->right;
		if (y->right)
		{
			y->right->parent = x;
		}
		y->parent = x->parent;
		if (x == root)
		{
			root = y;
		}
		else if (x == x->parent->right)
		{
			x->parent->right = y;
		}
		else
		{
			x->parent->left = y;
		}
		y->right = x;
		x->parent = y;
	}


 
        //这里有问题，但是解决不了。。。。。。
	_pnode _rb_tree_rebalance_for_erase(_pnode z, _pnode& root, _pnode& leftmost, _pnode& rightmost) noexcept
	{
		_pnode y = z, x = nullptr, x_parent = nullptr;
		if (y->left == nullptr)
		{
			x = y->right;
		}
		else
		{
			if (y->right == nullptr)
			{
				x = y->left;
			}
			else
			{
				y = y->right;
				while (y->left)
				{
					y = y->left;
				}
				x = y->right;
			}
		}
		if (y != z)
		{
			z->left->parent = y;
			y->left = z->left;
			if (y != z->right)
			{
				x_parent = y->parent;
				if (x)
				{
					x->parent = y->parent;
				}
				y->parent->left = x;
				y->right = z->right;
				z->right->parent = y;
			}
			else
			{
				x_parent = y;
			}
			if (root = z)
			{
				root = y;
			}
			else if (z->parent->left == z)
			{
				z->parent->left = y;
			}
			else
			{
				z->parent->right = y;
			}
			y->parent = z->parent;
			std::swap(y->color, z->color);
			y = z;
		}
		else
		{
			x_parent = y->parent;
			if (x)
			{
				x->parent = y->parent;
			}
			if (root == z)
			{
				root = x;
			}
			else
			{
				if (z->parent->left == z)
				{
					z->parent->left = x;
				}
				else
				{
					z->parent->right = x;
				}
			}
			if (leftmost == z)
			{
				if (z->right == nullptr)
				{
					leftmost = z->parent;
				}
				else
				{
					leftmost = _minimum(x);
				}
			}
			if (rightmost == z)
			{
				if (z->left == nullptr)
				{
					rightmost = z->parent;
				}
				else
				{
					rightmost = _maximum(x);
				}
			}
		}

		if (y->color != red)
		{
			while (x != root && (x == 0 || x->color == black))
			{
				if (x == x_parent->left)
				{
					_pnode w = x_parent->right;
					if (w->color == red)
					{
						w->color = black;
						x_parent->color = red;
						_rb_tree_rotate_left(x_parent, root);
						w = x_parent->right;
					}
					if ((w->left == 0 || w->left->color == black) &&
						(w->right == 0 || w->right->color == black))
					{
						w->color = red;
						x = x_parent;
						x_parent = x_parent->parent;
					}
					else
					{
						if (w->right == 0 || w->right->color == black)
						{
							if (w->left)
							{
								w->left->color = black;
							}
							w->color = red;
							_rb_tree_rotate_right(w, root);
							w = x_parent->right;
						}
						w->color = x_parent->color;
						x_parent->color = black;
						if (w->right)
						{
							w->right->color = black;
						}
						_rb_tree_rotate_left(x_parent, root);
						break;
					}
				}
				else
				{
					_pnode w = x_parent->left;
					if (w->color == red)
					{
						w->color = black;
						x_parent->color = red;
						_rb_tree_rotate_right(x_parent, root);
						w = x_parent->left;
					}
					if ((w->right == 0 || w->right->color == black) &&
						(w->left == 0 || w->left->color == black))
					{
						w->color = red;
						x = x_parent;
						x_parent = x_parent->parent;
					}
					else
					{
						if (w->left == 0 || w->left->color == black)
						{
							if (w->right)
							{
								w->right->color = black;
							}
							w->color = red;
							_rb_tree_rotate_left(w, root);
							w = x_parent->left;
						}
						w->color = x_parent->color;
						x_parent->color = black;
						if (w->left)
						{
							w->left->color = black;
						}
						_rb_tree_rotate_right(x_parent, root);
						break;
					}
				}
			}
			if (x)
			{
				x->color = black;
			}
		}

		return y;
	}



	_pnode _minimum(_pnode x) const noexcept
	{
                assert(x);
		while (x->left != nullptr)
		{
			x = x->left;
		}
		return x;
	}

	_pnode _maximum(_pnode x) const noexcept
	{
		assert(x);
		while (x->right != nullptr)
		{
			x = x->right;
		}
		return x;
	}


	bool _is_rb_tree() const noexcept
	{
		if (node_count == 0 || header->left == header)
		{
			return node_count == 0 && header->left == header && header->right == header;
		}

		size_t len = _black_count(header->left, header->parent);

		_pnode x = nullptr, L = nullptr, R = nullptr;
		for (iterator i = begin(); i != end(); ++i)
		{
			x = i.node;
			L = x->left;
			R = x->right;

			if (x->color == red)
			{
				if ((L && L->color == red) || (R && R->color == red))
				{
					return false;
				}
			}

			if (L && x->_pair.key_field < L->_pair.key_field)
			{
				return false;
			}

			if (R && x->_pair.key_field > R->_pair.key_field)
			{
				return false;
			}

			if (!L && !R && _black_count(x, header->parent) != len)
			{
				return false;
			}

			if (header->left != _minimum(header->parent))
			{
				return false;
			}

			if (header->right != _maximum(header->parent))
			{
				return false;
			}

		}
		return true;
	}

	size_t _black_count(_pnode node, _pnode root) const noexcept
	{
		if (node == nullptr)
		{
			return 0;
		}
		else
		{
			size_t bc = node->color == black ? 1 : 0;
			if (node == root)
			{
				return bc;
			}
			else
			{
				return bc + _black_count(node->parent, root);
			}
		}
	}

private:
	_pnode header;
	size_t node_count;
};

#endif