红黑树的实现——插入

电玩女神 2022-08-05 08:52 158阅读 0赞

红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

写红黑树只需要了解以下性质

性质1. 节点是红色或黑色。

性质2. 根节点是黑色。

性质3 每个叶节点（NIL节点，空节点）是黑色的。

性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

<span style="font-size:18px;">#include "stdafx.h"
    #include<deque>
    #include<iostream>
    
    
    #define  KeyType int
    #define MAX -1000000
    #define MIN 1000000
    
    /*性质1. 节点是红色或黑色。
    性质2. 根节点是黑色。
    性质3 每个叶节点（NIL节点，空节点）是黑色的。
    性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
    性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。*/
    class RBTree
    {
    public:
    	const static enum Color{
    		red, black
    	};
    
    	const static struct RBNode
    	{
    		Color color;
    		KeyType ele;
    		RBNode*lnode, *rnode, *parent;
    	};
    
    private:
    	RBNode*root;
    	RBNode* findnode(const KeyType val);
    	RBNode*findminmax(const KeyType val);
    	void destroy();
    	void inorder(RBNode*node);
    	void insert_adjust(RBNode*node);
    	bool isfullblack(RBNode*node);
    
    public:
    	RBTree()
    	{
    		root = NULL;
    	}
    	bool insert(const KeyType val);
    	bool erase(const KeyType val);
    	bool find(const KeyType val){ return findnode(val) != NULL; }
    	RBNode*getRoot();//测试用
    	~RBTree()
    	{
    		destroy();
    	}
    };
    std::deque<RBTree::RBNode*>aa;
    
    void RBTree::inorder(RBTree::RBNode*nn)
    {
    	if (nn == NULL)
    		return;
    	inorder(nn->lnode);
    	aa.push_back(nn);
    	inorder(nn->rnode);
    }
    
    RBTree::RBNode*RBTree::getRoot()
    {
    	return root;
    }
    RBTree::RBNode*RBTree::findnode(const KeyType val)
    {
    	if (root == NULL)
    		return NULL;
    	RBNode*nn = root;
    	while (nn != NULL)
    	{
    		if (nn->ele == val)
    			return nn;
    		if (nn->ele > val)
    			nn = nn->lnode;
    		else
    			nn = nn->rnode;
    	}
    	return NULL;
    }
    
    RBTree::RBNode*RBTree::findminmax(const KeyType val)//找到插入节点的位置
    {
    	_ASSERTE(val > MAX&&val < MIN);
    	std::deque<RBNode*>aa;
    	aa.push_back(root);
    	RBNode*minmax = NULL;
    
    	int near = MIN;
    	while (!aa.empty())//非递归先根遍历
    	{
    		RBNode*node = aa.back();
    		aa.pop_back();
    		if (node->ele - val > 0 && node->ele - val < near)
    		{
    			minmax = node;
    			near = node->ele - val;
    		}
    		if (node->rnode != NULL)
    			aa.push_back(node->rnode);
    		if (node->lnode != NULL)
    			aa.push_back(node->lnode);
    	}
    	return minmax;
    }
    
    void RBTree::destroy()
    {
    	if (root == NULL)
    		return;
    	std::deque<RBNode*>aa, bb;
    	aa.push_back(root);
    	while (!aa.empty())//非递归先根遍历
    	{
    		RBNode*node = aa.back();
    		aa.pop_back();
    		bb.push_back(node);
    		if (node->rnode != NULL)
    			aa.push_back(node->rnode);
    		if (node->lnode != NULL)
    			aa.push_back(node->lnode);
    	}
    	for (int i = 0; i < bb.size(); i++)
    	{
    		delete bb[i];
    	}
    }
    
    void RBTree::insert_adjust(RBTree::RBNode*node)
    {
    	while (node->parent != NULL)
    	{
    		if (node->parent->color == black)
    		{
    			return;
    		}
    		RBNode*parent = node->parent;
    		RBNode*grandpa = node->parent->parent;
    		if (parent->rnode == node&&grandpa->lnode == parent)
    		{
    
    			RBNode*node_lnode = node->lnode;
    			RBNode*node_rnode = node->rnode;
    			RBNode*gg = grandpa->parent;
    			bool isleft = true;
    			if (gg != NULL&&gg->rnode == grandpa)
    				isleft = false;
    			node->lnode = parent;
    			node->rnode = grandpa;
    			parent->parent = node;
    			grandpa->parent = node;
    			parent->rnode = node_lnode;
    			if (node_lnode != NULL)
    				node_lnode->parent = parent;
    			grandpa->lnode = node_rnode;
    			if (node_rnode != NULL)
    				node_rnode->parent = grandpa;
    			node->lnode->color = black;
    			if (gg == NULL)
    			{
    				node->parent = NULL;
    				root = node;
    				node->color = black;
    				return;
    			}
    			node->parent = gg;
    
    			if (isleft)
    				gg->lnode = node;
    			else
    				gg->rnode = node;
    
    		}
    		else if (parent->lnode == node&&grandpa->rnode == parent)
    		{
    			RBNode*node_lnode = node->lnode;
    			RBNode*node_rnode = node->rnode;
    			RBNode*gg = grandpa->parent;
    			bool isleft = true;
    			if (gg != NULL&&gg->rnode == grandpa)
    				isleft = false;
    			node->rnode = parent;
    			node->lnode = grandpa;
    			parent->parent = node;
    			grandpa->parent = node;
    			parent->lnode = node_rnode;
    			if (node_rnode != NULL)
    				node_rnode->parent = parent;
    			grandpa->rnode = node_lnode;
    			if (node_lnode != NULL)
    				node_lnode->parent = grandpa;
    			node->rnode->color = black;
    			if (gg == NULL)
    			{
    				node->parent = NULL;
    				root = node;
    				node->color = black;
    				return;
    			}
    			node->parent = gg;
    
    			if (isleft)
    				gg->lnode = node;
    			else
    				gg->rnode = node;
    		}
    		else if (parent->rnode == node&&grandpa->rnode == parent)
    		{
    			RBNode*node_lnode = node->lnode;
    			RBNode*node_rnode = node->rnode;
    			RBNode*parent_lnode = parent->lnode;
    			RBNode*gg = grandpa->parent;
    			bool isleft = true;
    			if (gg != NULL&&gg->rnode == grandpa)
    				isleft = false;
    
    			KeyType temp = node->ele;
    			node->ele = parent->ele;
    			parent->ele = temp;
    			node->rnode = parent;
    			node->lnode = grandpa;
    			parent->parent = node;
    			grandpa->parent = node;
    			parent->rnode = node_rnode;
    			if (node_rnode != NULL)
    				node_rnode->parent = parent;
    			parent->lnode = node_lnode;
    			grandpa->rnode = parent_lnode;
    			if (parent_lnode != NULL)
    				parent_lnode->parent = grandpa;
    			if (node_lnode != NULL)
    				node_lnode->parent = parent;
    			node->rnode->color = black;
    			if (gg == NULL)
    			{
    				node->parent = NULL;
    				root = node;
    				node->color = black;
    				return;
    			}
    			node->parent = gg;
    			if (isleft)
    				gg->lnode = node;
    			else
    				gg->rnode = node;
    		}
    		else if (parent->lnode == node&&grandpa->lnode == parent)
    		{
    			RBNode*node_rnode = node->rnode;
    			RBNode*node_lnode = node->lnode;
    			RBNode*parent_rnode = parent->rnode;
    			RBNode*gg = grandpa->parent;
    			bool isleft = true;
    			if (gg != NULL&&gg->rnode == grandpa)
    				isleft = false;
    			KeyType temp = node->ele;
    			node->ele = parent->ele;
    			parent->ele = temp;
    			node->lnode = parent;
    			node->rnode = grandpa;
    			parent->parent = node;
    			grandpa->parent = node;
    			parent->rnode = node_rnode;
    			if (node_rnode != NULL)
    				node_rnode->parent = parent;
    			parent->lnode = node_lnode;
    			if (node_lnode != NULL)
    				node_lnode->parent = parent;
    			grandpa->lnode = parent_rnode;
    			if (parent_rnode != NULL)
    				parent_rnode->parent = grandpa;
    			node->lnode->color = black;
    			if (gg == NULL)
    			{
    				node->parent = NULL;
    				root = node;
    				node->color = black;
    				return;
    			}
    			node->parent = gg;
    			if (isleft)
    				gg->lnode = node;
    			else
    				gg->rnode = node;
    		}
    		else
    			_ASSERTE(1 < 0);
    	}
    }
    bool RBTree::insert(const KeyType val)
    {
    	if (root == NULL)
    	{
    		root = new RBNode;
    		root->color = black;
    		root->ele = val;
    		root->lnode = root->rnode = root->parent = NULL;
    		return true;
    	}
    
    	RBNode*pos = findminmax(val);
    	if (pos == NULL)//要插入的值比当前树中所有的都大
    	{
    		RBNode*nn = root;
    		while (nn->rnode != NULL)
    		{
    			nn = nn->rnode;
    		}
    
    		if (nn->color == black)//包含nn==root的情况
    		{
    			RBNode*node = new RBNode;
    			node->ele = val;
    			node->color = red;
    			node->lnode = node->rnode = NULL;
    			node->parent = nn;
    			nn->rnode = node;
    			return true;
    		}
    		if (nn->color == red)
    		{
    			_ASSERTE(nn->lnode == NULL);
    			//此时nn的父亲颜色一定是黑色
    			if (nn->parent->lnode == NULL)
    			{
    				int temp = nn->parent->ele;
    				nn->parent->ele = nn->ele;
    				nn->ele = val;
    				RBNode*node = new RBNode;
    				node->ele = temp;
    				node->color = red;
    				node->lnode = node->rnode = NULL;
    				node->parent = nn->parent;
    				nn->parent->lnode = node;
    				return true;
    			}
    			//如果nn->parent->lnode != NULL
    			_ASSERTE(nn->parent->lnode->color == red);
    			if (nn->parent == root)
    			{
    				RBNode*node = new RBNode;
    				node->ele = val;
    				node->color = red;
    				node->lnode = node->rnode = NULL;
    				node->parent = nn;
    				nn->rnode = node;
    				nn->color = black;
    				root->lnode->color = black;
    				return true;
    			}
    			RBNode*pp = nn->parent;
    			_ASSERTE(pp != NULL);
    			RBNode*mm = pp;
    			_ASSERTE(mm != NULL);
    			int n = 1;
    			while (mm->rnode != NULL)
    			{
    				mm = mm->rnode;
    				n++;
    			}
    			RBNode*node = new RBNode;
    			node->ele = val;
    			node->color = red;
    			node->lnode = node->rnode = NULL;
    			node->parent = nn;
    			nn->rnode = node;
    			insert_adjust(node);
    			return true;
    		}
    	}
    
    	if (pos != NULL)
    	{
    		if (pos->lnode == NULL)
    		{
    			RBNode*node = new RBNode;
    			node->ele = val;
    			node->color = red;
    			node->lnode = node->rnode = NULL;
    			node->parent = pos;
    			pos->lnode = node;
    			insert_adjust(node);
    			return true;
    		}
    		RBNode*kk = pos->lnode;
    		while (kk->rnode != NULL)
    		{
    			kk = kk->rnode;
    		}
    		RBNode*node = new RBNode;
    		node->ele = val;
    		node->color = red;
    		node->lnode = node->rnode = NULL;
    		node->parent = kk;
    		kk->rnode = node;
    		insert_adjust(node);
    		return true;
    	}
    }
    
    bool RBTree::isfullblack(RBTree::RBNode*node)
    {
    	std::deque<RBNode*>aa, cc;
    	int k = 0;
    	aa.push_back(node);
    	while (true)
    	{
    		while (!aa.empty())
    		{
    			RBNode*bb = aa.back();
    			aa.pop_back();
    			if (bb->color == red)
    				return false;
    			if (bb->lnode != NULL)
    				cc.push_back(bb->lnode);
    			if (bb->rnode != NULL)
    				cc.push_back(bb->rnode);
    		}
    		if (cc.empty())
    			return true;
    		if (cc.size() != (2 << k))
    			return false;
    		aa = cc;
    		cc.clear();
    		k++;
    	}
    }
    
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	RBTree rbt;
    	RBTree::RBNode*root;
    	rbt.insert(100);
    	root = rbt.getRoot();
    	rbt.insert(700);
    	root = rbt.getRoot();
    	rbt.insert(500);
    	root = rbt.getRoot();
    	rbt.insert(1000);
    	root = rbt.getRoot();
    	rbt.insert(1500);
    	root = rbt.getRoot();
    	rbt.insert(600);
    	root = rbt.getRoot();
    	rbt.insert(300);
    	root = rbt.getRoot();
    	rbt.insert(800);
    	root = rbt.getRoot();
    	rbt.insert(3000);
    	root = rbt.getRoot();
    	rbt.insert(900);
    	root = rbt.getRoot();
    	rbt.insert(1300);
    	root = rbt.getRoot();
    	rbt.insert(1800);
    	root = rbt.getRoot();
    
    
    
    
    	system("pause");
    
    	return 0;
    }</span>