数据结构之红黑树

转x33g5p2x  于2022-03-18 转载在 其他  
字(8.4k)|赞(0)|评价(0)|浏览(373)

红黑树

本篇博文只讲解了红黑树的插入操作，下面我们来了解一下什么是红黑树。

红黑树的概念

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

NIL是空结点，这里显示出来是为了表示路径

红黑树和AVLTree不同点：

AVLTree：左右高度差不超过1，严格平衡

红黑树：最长路径不超过最短路径的2倍，近似平衡

严格来说红黑树的效率没有AVLTree高，当AVLTree的旋转多时，此时红黑树的效率就高于AVLTree

红黑树的性质

  1. 每个结点不是红色就是黑色

  2. 根节点是黑色的

  3. 如果一个节点是红色的，则它的两个孩子结点必须是黑色的
    树里面没有连续的红色节点

  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
    每条路径都有相同数量的黑色节点(路径不是走到叶子节点，而是走到空节点)

  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)，就像图中的NIL节点

那么是红黑树是如何做到平衡的呢？

通过性质3和4：
由性质四可知，每条路径都有相同的黑色节点，假设有一条路径上都是黑色节点，那么一棵红黑树的最短路径就是这条路径

由性质三可知，红黑树中没有连续的红色节点，那么一棵红黑树的最长路径就是一黑一红，交替出现，因为每条路径的黑色节点是相同的，最长路径不会超过最短路径的两倍

红黑树节点的定义

红黑树节点的颜色我们可以用枚举来定义，我们将红黑树实现成三叉链的结构：

#pragma once
enum Colour
{
    BLACK,
    RED
};
template<class K,class V>
struct RBTreeNode
{
    RBTreeNode<K,V>* _left;
    RBTreeNode<K,V>* _right;
    RBTreeNode<K,V>* _parent;
    
    Colour _col;//颜色
    
    pair<K,V> _kv;//键值对
    
    //构造函数
    RBTreeNode(const pair<K,V>& kv)
        :_left(nullptr),
        :_right(nullptr),
        :_parent(nullptr),
        :col(RED),
        :_kv(kv)
	{}
};

有一个问题：为什么颜色初始化，初始化成红色呢？

插入红色可能破坏规则3，但是插入黑色的话一定破坏规则4，因为如果插入黑色节点，该路径黑色节点的数目肯定发生了变化，为了保证所有路径黑色节点数目相同，所有路径都需要做调整，而插入红色，如果父亲节点是黑色节点，那么就不需要做调整，即使出现了连续的红色节点，破坏了规则3，只是破坏了这一条路径，只需要调整该路径，所以选择红色节点

红黑树的插入情况操作

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

  • 插入情况一: cur为红，p为红，g为黑，u存在且为红

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

插入cur时，已经出现了连续的红节点，所以需要将p变黑，为了保证不同路径的黑色节点数目不变，u也得变黑，那么为什么最后将g改为红呢？因为这棵树可能只是局部的子树，那么要保持他的每条路径黑色节点的数量不变，p和u变黑以后，路径上的黑色节点多了，所以g得变红，g变红一会就得继续往上处理

具象图1：

处理结果：

具象图二(需要继续往上处理的场景)：

如果g是根节点，调整完成后，需要将g改为黑色
如果g是子树，g一定有双亲，且g的双亲如果是红色，需要继续向上调整

  • 插入情况二：cur为红，p为红，g为黑，u不存在/u存在且为黑
    关键看叔叔，情况二相比情况一，只变了叔叔

u存在且为黑：

u存在且为黑的情况时，cur一定不是新增，cur原来是黑的，保证了规则4，cur之所以是红色，是因为cur是作为子树的祖父，是由第一种情况变化过来的

该情况是由情况一转变过来的：

u不存在：

u不存在，那么cur就是新增，因为cur不是新增的话，那么p和cur当中一定有一个黑色节点，此时黑色节点就多了，不满足规则4：每条路径黑色节点数目相同

处理方法：

叔叔不存在时：
p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转，p、g变色–p变黑，g变红

叔叔存在且为黑：

  • 插入情况三：cur为红，p为红，g为黑，u不存在/u存在且为黑

插入情况三相比于插入情况二不一样的是，p如果是p的左边，那么cur就是p的右边，p如果是p的右边，那么cur就是p的左边

这种情况做一次旋转是解决不了问题的，需要做两次旋转：
p为g的左孩子，cur为p的右孩子时，则针对p做左单旋转，然后再针对g做右单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转，再针对g做左单旋转

u不存在：

u存在且为黑：

红黑树的插入代码

bool Insert(const pair<K, V>& kv)
{
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_col = BLACK;//根节点必须是黑色
        return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_kv.first < kv.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else
        {
            //相等
            return false;
        }
    }

    cur = new Node(kv);
    cur->_col = RED;//默认给红色

    //链接
    if (parent->_kv.first < cur->_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->_right)
        {
            //找到叔叔
            Node* uncle = grandfather->_left;
            //情况一：uncle存在且为红，进行变色处理即可,并且继续往上更新处理
            if (uncle && uncle->_col == RED)
            {
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;

                cur = grandfather;
                parent = cur->_parent;
            }
            //情况二+三：uncle不存在，uncle存在且为黑，进行旋转+变色处理
            else
            {
                //情况二：单旋+变色
                if (cur == parent->_left)
                {
                    RotateR(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                }
                else
                {
                    //情况三：双旋+变色
                    RotateL(parent);
                    RotateR(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        }
        else//parent == greandfather->_left
        {
            Node* uncle = grandfather->_right;
            if (uncle && uncle->col == RED)
            {
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;

                cur = grandfather;
                parent = cur->_parent;
            }
            else
            {
                if (parent->_right == cur)
                {
                    RotateL(grandfather);
                    parent->_col = BLACK;
                    grandfather->COL = RED;
                }
                else//parent->_left == cur
                {
                    //双旋+变色
                    RotateR(parent);
                    RotateL(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                //不用再继续了，不会有连续红色和黑色个数不一样
                break;
            }
        }
    }
    _root->_col = BLACK;
}
void RotateR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = subL->_right;

    parent->_left = subLR;
    if (subLR)
        subLR->_parent = parent;

    Node* ppNode = parent->_parent;

    subL->_right = parent;
    parent->_parent = subL;

    if (parent == _root)
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    else
    {
        if (ppNode->_left == parent)
            ppNode->_left = subL;
        else
            ppNode->_right = subL;

        subL->_parent = ppNode;
    }
}

void RotateL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    parent->_right = subRL;
    if (subRL)
        subRL->_parent = parent;

    Node* ppNode = parent->_parent;

    subR->_left = parent;
    parent->_parent = subR;

    if (parent == _root)
    {
        _root = subR;
        subR->_parent = nullptr;
    }
    else
    {
        if (ppNode->_left == parent)
        {
            ppNode->_left = subR;
        }
        else
        {
            ppNode->_right = subR;
        }

        subR->_parent = ppNode;
    }
}

红黑树测试代码

void TestRBTree1()
{
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	const int n = 1000000;
	vector<int> a;
	a.reserve(n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		a.push_back(rand());
	}

	RBTree<int, int> t1;
	for (auto e : a)
	{
		t1.Insert(make_pair(e, e));
	}

	cout << t1.IsBalance() << endl;
	//t1.InOrder();
}
void _InOrder(Node* root)
{
    if(root == nullptr)
    {
        return;
    }
    _InOrder(root->_left);
    cout<<root->_kv.first<<endl;
    _InOrder(root->_right);
}
void InOrder(Node* root)
{
    _InOrder(_root);
}
bool CheckRR(Node* cur)
{
    if(cur == nullptr)
    {
        return true;
    }
    if(cur->_col == RED && cur->_parent == RED)
    {
        cout<<"违反规则三，存在连续的红色节点"<<endl;
        return false;
    }
    return CheckRR(cur->_left)
        && CheckRR(cur->_right);
}

bool CheckBlackNum(Node* cur,int blackNum,int benchmark)
{
    if(cur == nullptr)
    {
        if(blackNum != benchmark)
        {
            cout<<"违反规则四：黑色节点的数量不相等"<<endl;
            return false;
        }
        return true;
    }
    if(cur->_col == BLACK)
    {
        ++blackNum;
    }
    return CheckBlackNum(cur->_left,balckNum,benchmark);
    	&& CheckBlackNum(cur->_right,balckNum,benchmark);
}
bool IsBalance()
{
    if(_root == nullptr)
    {
        return true;
    }
    if(_root->_col == RED)
    {
        cout<<"根节点是红色，违反规则二"<<endl;
        return false;
    }
    //算出最左路径的黑色节点的个数作为基准值
    int benchmark = 0;
    Node* cur = _root;
    while(cur)
    {
        if(cur->_col == BLACK)
        {
            ++benchmark;
        }
        cur = cur->_left;
    }
    int blackNum = 0;
    //检查规则三
    return CheckRR(_root) && CheckBlackNum(root,blackNum,benchmark);
    //每条路径的黑色节点都求出来，提前算出一个基准值进行比较
}

红黑树整体代码

template<class K,class V>
class RBTree
{
    typedef RBTreeNode<K,V> Node;
public:
    RBTree()
        :_root(nullptr)
    {}
    bool Insert(const pair<K,V>& kv)
    {
        if(_root == nullptr)
        {
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while(cur)
        {
            if(cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                //相等了，已经有了
                return false;
            }
        }
        //插入红色可能破坏规则3，插入黑色一定破坏规则4,破坏规则4比较难处理
        //新增节点就新增一个红色节点
        //1、如果新增节点的父亲是黑色，没有影响
        //2、如果新增节点的父亲是红色，则产生了连续的红色节点，破坏了规则3，需要分情况处理：
        
        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->_right)
            {
                //找到叔叔
                Node* uncle = grandfather->_left;
                //情况一：uncle存在且为红，进行变色处理即可,并且继续往上更新处理
                if(uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    
                    cur = grandfather;
                    parent = cur->_parent;
                }
                //情况二+三：uncle不存在，uncle存在且为黑，进行旋转+变色处理
                else
                {
                    //情况二：单旋+变色
                    if(cur == parent->_left)
                    {
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        //情况三：双旋+变色
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
            else//parent == greandfather->_left
            {
                Node* uncle = grandfather->_right; 
                if(uncle && uncle ->col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else
                {
                    if(parent->_right == cur)
                    {
                        RotateL(grandfather);
                        parent->_col = BLACK;
                        grandfather->COL = RED;
                    }
                    else//parent->_left == cur
                    {
                        //双旋+变色
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    //不用再继续了，不会有连续红色和黑色个数不一样
                    break;
                }
            }
        }
        _root->_col = BLACK;
    }
    void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* ppNode = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
				ppNode->_left = subL;
			else
				ppNode->_right = subL;

			subL->_parent = ppNode;
		}
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		Node* ppNode = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}

			subR->_parent = ppNode;
		}
	}
private:
    Node* _root;
}

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/attemptendeavor/article/details/123577393

内容来源于网络，如有侵权，请联系作者删除！

数据结构算法红黑树

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com