map和set的实现(2)——红黑树_随笔

map和set的实现(2)——红黑树

文章目录

1.红黑树的概念2.红黑树的性质与原理3.红黑树节点的定义4.红黑树的插入

4.1情况一4.2情况二4.3情况三4.4代码实现4.5小结 5.红黑树的检查6.红黑树的删除

1.红黑树的概念

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

实际当中进行搜索一般使用红黑树，和AVL树相比较并不是质的变化。

那么AVL树和红黑树有什么区别呢？

AVLTREE：

二叉搜索树每个子树的左右高度不超过1

AVLTREE是严格平衡。

红黑树：最长路径最多是最短路径的2倍。

红黑树是近似平衡。

那为什么近似平衡比严格平衡好呢?

考虑最坏情况，AVLTREE查找 l o g ( N ) log(N) log(N)次，而红黑树查找 2 ∗ l o g ( N ) 2*log(N) 2∗log(N)次。而这种情况没有什么效率区别，而AVLTREE构建的旋转比红黑树多。综合而言红黑树的效率并不比AVLTREE树差，但是旋转比AVLTREE少。

2.红黑树的性质与原理

每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的，则它的两个孩子结点是黑色的对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

为什么满足前4个性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍呢？（严格来说主要规则是第三条规则和第四条规则）

如果一个节点是红色的，则它的两个孩子结点是黑色的 -> 树中没有连续的红色节点（可以红黑相间或者连续黑）

对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 -> 每条路径上都包含相同数量的黑色节点

最短路径：全部由黑色结点构成。

既然第四点说对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。我们大可以先把每条路径上的黑色节点全部抽离出来构造成一棵树，此时必然是满二叉树。此时不能再追加黑色节点，只能追加红色节点，不加红色节点的话就是此时路径就是最短的。

最长路径：在全部由黑色结点构成的树上添加红色节点进行构造最长路径。

由于红色是不能连续的，因此只能间隔。构造出的最长路径为一黑一红的状态，而这条最长路径的黑的数量和最短路径的黑的数量相同，因此最多为2倍状态。

因此假设黑色结点有N个，则最短路径长度为 O ( l o g N ) O(logN) O(logN),最长路径长度为 2 ∗ O ( l o g N ) 2*O(logN) 2∗O(logN)。

那么第五点怎么理解？是针对如这种情况下满足第四点的条件。

Tips:正常红黑树中，不一定有全黑的最短路径和一黑一红最长路径

3.红黑树节点的定义

enum Color
{
    RED,
    BLACK
};
template
struct RBTreeNode
{
      RBTreeNode(const pair& kv)
          :_left(nullptr),
    	   _right(nullptr),
    	   _parent(nullptr),
    	   _kv(key_value),
    	   _col(RED)
           {}
    
  	  RBTreeNode* _left;
      RBTreeNode* _right;
      RBTreeNode* _parent;
    
      pair _kv;
	  Color _col;
};

template
class RBTree
{
    typedef RBTreeNode Node;
    public:
    	RBTree()
            :_root(nullptr)
            {	}
    	pair Insert(const pair& kv)
        {
            
        }
    private:
    	Node* _root;
}

4.红黑树的插入

只要控制了这四条规则

每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的，则它的两个孩子结点是黑色的对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

就能控制住红黑树的近似平衡。

插入新节点的颜色是黑的好，还是红的好？

插入红色破坏规则3，插入黑色破坏规则4。

插入红色节点，因为红色节点可能破坏规则三，影响不大。

插入黑色节点，一定破坏规则4，并且影响其他路径，影响面很大。

比如在一个路径上插入黑色节点，那么和剩下的路径中都冲突了。而破坏规则三只破坏一个分叉。

因此插入新节点的时候插入红色节点。

对插入情况进行讨论：

parent颜色是黑色，不需要调整，插入完成。（结束了）parent颜色是红色，违反了规则3，需要处理。（关键看叔叔）

如果parent是红色的，则grandfather一定是黑的。这时候看uncle。

对违反规则3的情况进行讨论：

注意：以下看到的图，可能是一颗完整的树，也可能是一棵子树

4.1情况一

情况一：cur为红，p为红，g为黑，u存在且为红。

情况一对叔叔的讨论是叔叔存在且为红。

处理方案：p和u变黑，g变红。处理后如果g是root，则变回黑处理结束。->如果g的父亲是红，则继续往上处理

g变红的原因：因为当前部分可能是在子树中。比如这种情况，如果g不变红，该子树的两个路径就会各自多出一个黑色，与子树外的路径造成了规则4的冲突。

这时候要考虑如果到g的父亲如果是黑色的，就没有问题了。

不然如果g的父亲是红，此时就出现了两个红色的，要继续往上处理。

对于情况一来说，即使换个方向，依然能够变色处理完成。

4.2情况二

情况二：cur为红，p为红，g为黑，u不存在/u存在且为黑

处理方式：单旋+变色

情况二的u存在且为黑理论上是从情况1处理后变化得到的。

因此u存在且为黑需要以情况一的处理一次后为基础。

u不存在的情况

红黑树中但凡触发旋转一定是最长路径超过了最短路径的二倍

u存在且为黑的情况

情况二方向反了进行另一种单旋+变色。

4.3情况三

红黑树中但凡触发旋转一定是最长路径超过了最短路径的二倍

情况三是情况二的变形，不同的是情况二是直线，是单旋；情况三是曲线，是双旋。

情况三方向反了进行另一种双旋+变色。

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

注意下图p左端的黑色节点是一定要存在的，不然没法满足每条路径的黑色节点个数相同的规则

4.4代码实现

对于上述三种情况反旋的图。见小结部分

template
class RBTree
{
    typedef RBTreeNode Node;
    public:
    	RBTree()
            :_root(nullptr)
            {	}
   		void Destroy(Node* root)
        {
            if(root == nullptr ) return ;
            Destroy(root -> _left );
            Destroy(root -> _right);
        	delete root;
        }
    	~RBTree()
        {
            Destroy(root);
            _root = nullptr;
        }
    	//拷贝构造和operator[]赋值
    
    	Node* Find(const K& key)
        {
            Node* cur = _root;
            while( cur )
            {
                if( cur -> _kv.first > key)
                {
                    cur = cur -> _left;
                }
                else if( cur -> _kv.first < key)
                {
                    cur = cur -> _right;
                }
                else{
                    return cur;
                }
            }
            return nullptr;
        }
        void RotateR(Node* parent)
        {
            Node* subL = parent -> _left;
            Node* subLR = subL -> _right;
            parent -> _left = subLR;

            if( subLR ) subLR -> _parent = parent;
            subL -> _right = parent ;

            Node* grandParent = parent -> _parent; 

            parent -> _parent = subL;

            if( parent == _root )
            {
                _root = subL;
                _root  -> _father = nullptr;
            }
            else{
                if( grandParent -> _left == parent )
                {
                    grandParent -> _left = subL;
                }
                else{
                    grandParent -> _right =subL;
                }
                subL -> _father = grandParent;
            }
        }
        void RotateL(Node* parent)
        {
            Node* subR = parent -> _right;
            Node* subRL = subR -> _left;

            parent -> _right = subRL;
            if( subRL != nullptr ) {
                subRL -> _parent =parent ;
            }
            subR -> _left = parent;
            Node* grandparent = parent -> _parent;
            parent -> _parent = subR;
            if( parent == _root )
            {
                _root = subR;
                _root -> _parent = nullptr;
            }
            else{
                if(grandparent -> _left == parent)
                {
                    grandparent -> _left = subR;
                }
                else{
                    grandparent -> _right = subR;
                }

                subR -> _parent = grandparent;
            }

            subR -> _bf = parent -> _bf =0;
        }
    	pair Insert(const pair& kv)
        {
  			if(_root == nullptr)
            {
				_root = new Node(kv);
                _root = BLACK;
                return make_pair(_root,true);
            }
            Node* parent = nullptr;
            Node* cur = _root;
            while(cur)
            {
                if( cur -> _kv.first < kv.first)//如果实现的是multimap这里使用的是<=
                {
                   parent = cur ;
                   cur = cur -> _right;
                }
                else if( cur -> _kv.first > kv.first)
                {
                    parent =cur ;
                    cur = cur -> _left;
                }
                else{
                    return make_pair(cur ,false);
                }
            }
            Node* newnode = new Node(kv);
            newnode -> _col = RED;
            if( parent -> _kv.first < kv.first)
            {
                parent -> _right = newnode;
                newnode -> _parent = parent;
            }
            else{
                parent -> _left = newnode ;
                newnode -> _parent = parent;
            }
			cur = newnode;
            
            //如果父亲存在，且颜色为红色，则需要处理
            while( parent && parent -> _col ==RED)
            {
                //关键看叔叔
                Node* grandfather = parent -> _parent ; //当前进来的逻辑情况下grandfather一定存在,因为根不能是红
                
                if(parent == grandfather -> _left)
                {
                    Node* uncle = grandfather -> _right;
                    
                    //情况一：uncle存在且为红
                    if( uncle && uncle -> _col ==RED)
                    {
                        parent -> _col = uncle -> _col = BLACK;
                        grandfather -> _col = RED;
                        
                        //继续往上处理
                        cur = grandfather;
                        parent = cur -> _parent;
                    }
                    else{ //情况 2+3  uncle不存在/uncle存在且为黑
                        if( cur ==  parent -> _left ) // 情况2: 单旋
                        {
                            RotateR(grandfather);
                            grandfather -> _col = RED;
                            parent -> _col = BLACK;
                        }
                        else{ //情况三:双旋
                            RotateL(parent);
                            RotateR(grandfather);
                            
                            cur -> _col = BLACK;
                            grandfather -> _col = RED;
                        }
                        
                        break;//旋转完就整棵树变成红黑树了
                    }
                }
                else// parent == grandfather -> _right;
                {
 						Node* uncle = grandfather -> _left;
                    	if(uncle && uncle -> _col == RED)//情况一:叔叔存在且为红
                        {
                            uncle -> _col = BLACK;
                            parent -> _col = BLACK;
                            grandfather -> _col =RED;
                            
                            cur = grandfather ;
                            parent = cur -> _father;
                        }
                    	else{//情况二+三:叔叔存在且为黑或者不存在
                            if( cur == parent -> _right )//情况二:单旋+变色
                            {
                                RotateL(grandfather);
                                grandfather -> _col =RED;
                                parent -> _col =BLACK;
                            }
                            else{
                                RotateR(parent);
                                RotateL(grandfather);
                                cur -> _col = BLACK;
                                grandfater -> _col = RED;
                            }
                            
                            break;//旋转完必定搞定
                        }
                }
            }
            
            _root -> _col = BLACK;
            return make_pair(newnode ,true);
        }
    private:
    	Node* _root;
}

4.5小结

新增节点(红色) ps：插入红色只会影响当前路径

1、如果插入节点父亲如果是黑色，插入结束
2、如果插入节点父亲如果是红色，那么违反不能连续有红色节点的规则

先讨论 / / /的情况，再讨论曲线，接着讨论的情况，最后讨论曲线。

每种大情况通过对叔叔的讨论分为三种情况来处理：关键看叔叔。如果要旋转则当前情况一定是最长路径的长度>2*最短路径的长度

5.红黑树的检查

每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的，则它的两个孩子结点是黑色的 -->每条路径上的黑色节点数量相等对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

红黑树平衡的关键点在这几点规则，我们重点检查1、2、3规则。

第一点规则进入的时候就可以检查

对于第二点来说，如果检查儿子有一些麻烦，考虑只有一个儿子，两个儿子，没有儿子；不如遍历的时候检查父亲和当前是不是都是红色，因为红色节点理论上是有父亲的。

对于第三点来说，如果不开额外的空间就使用 O ( N 2 ) O(N^2) O(N2)的做法递归。或者开 O ( n ) O(n) O(n)的空间来存下每条路径的黑色节点数量。我们尝试 O ( n ) O(n) O(n)时间复杂度+ O ( 1 ) O(1) O(1)空间复杂度，利用一个搜出来的标准值。

	bool CheckBalance()
    {
        if( _root == nullptr )
        {
            return true;
        }
        
        if( _root == RED ) 
        {
            cout<< " 根节点是红色的 " < _col == BLACK)
            {
                blackNum ++;
            }
       		left = left -> _left;
        }
        int count = 0;
        return _CheckBalance(_root , blackNum,count )
     }
	 bool _CheckBalance(Node* root ,int blackNum ,int count)
     {
         if( root == nullptr )
         {
             if( count != blackNum )
             {
                 cout<<" 黑色节点的数量不相等 "< _col == RED && root -> _parent -> _col == RED ) return false;
         if(root -> _col == BLACK )  count ++;
         
         return _CheckBalance(root -> _left , blackNum ,count ) && _CheckBalance( root -> _right ,blackNum ,count );
     }

#include"RBTree.h"
void TestRBTree()
{
    int a[] = { 16 , 3, 7 ,11 ,9 ,26 ,18, 14 ,15};
    RBTree t;
    for(auto e:a)
    {
        t.insert(make_pair(a,a));
    }
    t.InOrder();
    cout<< t.CheckBlance()< 
6.红黑树的删除 
只讲原理不讲实现。同AVL。 
如果左为空右为空，直接删如果左右都不为空，找替代结点删除。 
实际删除的结点一定满足左为空或右为空。 
可以了解：http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5718463.html

map和set的实现(2)——红黑树

发表评论

评论列表（0条）