【数据结构】：红黑树（RB Tree）

红黑树是近似平衡的二叉搜索树。
红黑树的性质:
1，每个节点不是红色就是黑色
2，根节点必须是黑色
3，没有连续的红节点
4，每条路径上黑色节点数目相等

红黑树保证最长路径不超过最短路径的两倍。那么，为什么满足以上这些条件就能保证呢？
最短路径一定是节点全黑，要保证每条路径的黑节点数量相等，只能在两个黑节点之间添加红节点，所以最长路径不会超过最短路径的两倍。
红黑树保证效率为log2^N

如上图所示是一棵简单的红黑树，红黑树的插入要通过旋转和变色来调节平衡。

当parent是grandfather的左孩子，uncle是grandfather的右孩子时，插入可分为以下情况：

1，叔叔节点存在且为红色

Node@H_502_29@* grandfther @H_502_29@= parent@H_502_29@->_parent;
            if (parent @H_502_29@== grandfther@H_502_29@->_left)
            {
                Node@H_502_29@* uncle @H_502_29@= grandfther@H_502_29@->_right;
                if (uncle @H_502_29@&& uncle@H_502_29@->_col @H_502_29@== RED)
                {
                    parent@H_502_29@->_col @H_502_29@= BLACK;
                    uncle@H_502_29@->_col @H_502_29@= BLACK;
                    grandfther@H_502_29@->_col @H_502_29@= RED;

                    cur @H_502_29@= grandfther;
                    parent @H_502_29@= cur@H_502_29@->_parent;
                }

2，叔叔节点不存在或存在且为黑

将parent变黑，grandfather变红，进行右单旋

else // u 不存在 u黑
                {
                    if(cur @H_502_29@== parent@H_502_29@->_right) // 双旋
                    {
                        RotateL(parent);
                        swap(cur,parent);
                    }

                    RotateR(grandfther);
                    parent@H_502_29@->_col @H_502_29@= BLACK;
                    grandfther@H_502_29@->_col @H_502_29@= RED;
                    break;
                }

3，cur是parent的右孩子，需要双旋

当parent是grandfather的右时，需要分析的情况还是以上三种，只是方向相反而已。

完整代码：

#pragma once
#include@H_502_29@<iostream@H_502_29@>
using namespace std;

enum Colour
{
    RED,BLACK,};

template@H_502_29@<class K,class V@H_502_29@>
struct RBTreeNode
{
    K _key;
    K _value;

    RBTreeNode@H_502_29@<K,V@H_502_29@>* _left;
    RBTreeNode@H_502_29@<K,V@H_502_29@>* _right;
    RBTreeNode@H_502_29@<K,V@H_502_29@>* _parent;

    Colour _col;

    RBTreeNode(const K@H_502_29@& key,const V@H_502_29@& value)
        :_key(key),_value(value),_left(NULL),_right(NULL),_parent(NULL),_col(RED)
    {}
};


template@H_502_29@<class K,class V@H_502_29@>
class RBTree
{
    typedef RBTreeNode@H_502_29@<K,V@H_502_29@> Node;
public:
    RBTree()
        :_root(NULL)
    {}

    RBTree(const RBTree@H_502_29@<K,V@H_502_29@>& tree)
    {
        _Copy(tree._root);
    }


    ~RBTree()
    {
        _Destroy(_root);
    }

    RBTree@H_502_29@<K,V@H_502_29@>& operator @H_502_29@= (const RBTree@H_502_29@<K,V@H_502_29@>& tree)
    {
        RBTree@H_502_29@<K,V@H_502_29@> tmp(tree);
        swap(_root,tree._root);
        return @H_502_29@*this;
    }


    bool Insert(const K@H_502_29@& key,const V@H_502_29@& value)
    {
        if (_root @H_502_29@== NULL)
        {
            _root @H_502_29@= new Node(key,value);
            _root@H_502_29@->_col @H_502_29@= BLACK;
            return true;
        }

        Node@H_502_29@* parent @H_502_29@= NULL;
        Node@H_502_29@* cur @H_502_29@= _root;
        while (cur)
        {
            if (cur@H_502_29@->_key @H_502_29@< key)
            {
                parent @H_502_29@= cur;
                cur @H_502_29@= cur@H_502_29@->_right;
            }
            else if (cur@H_502_29@->_key @H_502_29@> key)
            {
                parent @H_502_29@= cur;
                cur @H_502_29@= cur@H_502_29@->_left;
            }
            else
            {
                return false;
            }
        }

        cur @H_502_29@= new Node(key,value);
        if (parent@H_502_29@->_key @H_502_29@< key)
        {
            parent@H_502_29@->_right @H_502_29@= cur;
            cur@H_502_29@->_parent @H_502_29@= parent;
        }
        else
        {
            parent@H_502_29@->_left @H_502_29@= cur;
            cur@H_502_29@->_parent @H_502_29@= parent;
        }

        while (parent @H_502_29@&& parent@H_502_29@->_col @H_502_29@== RED)
        {
            Node@H_502_29@* grandfather @H_502_29@= parent@H_502_29@->_parent;
            if (parent @H_502_29@== grandfather@H_502_29@->_left)
            {
                Node@H_502_29@* uncle @H_502_29@= grandfather@H_502_29@->_right;
                if (uncle @H_502_29@&& uncle@H_502_29@->_col @H_502_29@== RED)
                {
                    parent@H_502_29@->_col @H_502_29@= BLACK;
                    uncle@H_502_29@->_col @H_502_29@= BLACK;
                    grandfather@H_502_29@->_col @H_502_29@= RED;

                    cur @H_502_29@= grandfather;
                    parent @H_502_29@= cur@H_502_29@->_parent;
                }
                else // u 不存在 u黑
                {
                    if (cur @H_502_29@== parent@H_502_29@->_right) // 双旋
                    {
                        RotateL(parent);
                        swap(cur,parent);
                    }

                    RotateR(grandfather);
                    parent@H_502_29@->_col @H_502_29@= BLACK;
                    grandfather@H_502_29@->_col @H_502_29@= RED;
                    break;
                }
            }
            //parent = grandfather->right
            else if (parent @H_502_29@== grandfather@H_502_29@->_right)
            {
                Node@H_502_29@* uncle @H_502_29@= grandfather@H_502_29@->_left;
                if (uncle @H_502_29@&& uncle@H_502_29@->_col @H_502_29@== RED)
                {
                    parent@H_502_29@->_col @H_502_29@= BLACK;
                    uncle@H_502_29@->_col @H_502_29@= BLACK;
                    grandfather@H_502_29@->_col @H_502_29@= RED;

                    cur @H_502_29@= grandfather;
                    parent @H_502_29@= cur@H_502_29@->_parent;
                }
                else
                {
                    if (cur @H_502_29@== parent@H_502_29@->_right)
                    {
                        RotateR(parent);
                        swap(parent,cur);
                    }
                    RotateL(grandfather);
                    parent@H_502_29@->_col @H_502_29@= BLACK;
                    grandfather@H_502_29@->_col @H_502_29@= RED;
                    break;
                }
            }
        }
        _root@H_502_29@->_col @H_502_29@= BLACK;
        return true;
    }

    void InOrder()
    {
        _InOrder(_root);
    }

    bool IsBalance()
    {
        Node@H_502_29@* cur @H_502_29@= _root;
        if (_root @H_502_29@== NULL)
        {
            return true;
        }
        //根节点是黑色
        if (_root@H_502_29@->_col @H_502_29@== RED)
        {
            return false;
        }
        int BlackNode @H_502_29@= 0;
        //统计最左路径上黑色节点的数量
        while (cur)
        {
            if (cur@H_502_29@->_col @H_502_29@== BLACK)
            {
                @H_502_29@++BlackNode;
            }
            cur @H_502_29@= cur@H_502_29@->_left;
        }
        //一条路径上黑色节点的数量
        int num @H_502_29@= 0;
        return _IsBlance(_root,BlackNode,num);
    }
protected:
    void _Copy(Node@H_502_29@* root)
    {
        Node@H_502_29@* newNode @H_502_29@= NULL;
        Node@H_502_29@* cur @H_502_29@= root;
        while (cur)
        {
            newNode @H_502_29@= new Node(cur@H_502_29@->_key,cur@H_502_29@->_value);
            newNode@H_502_29@->_left @H_502_29@= _Copy(cur@H_502_29@->_left);
            newNode@H_502_29@->_right @H_502_29@= _Copy(cur@H_502_29@->_right);
        }
    }

    void _Destroy(Node@H_502_29@* root)
    {
        Node@H_502_29@* cur @H_502_29@= root;
        if (root @H_502_29@== NULL)
            return;
        _Destroy(cur@H_502_29@->_left);
        _Destroy(cur@H_502_29@->_right);
        delete cur;
        cur @H_502_29@= NULL;
    }


    bool _IsBlance(Node@H_502_29@* root,const int BlackNode,int num)
    {
        //一条路径已经走完
        if (root @H_502_29@== NULL)
        {
            if (num @H_502_29@!= BlackNode)
            {
                cout @H_502_29@<< "黑色节点数量不相等" @H_502_29@<< endl;
                return false;
            }
            else
            {
                return true;
            }
        }
        if (root@H_502_29@->_col @H_502_29@== BLACK)
        {
            @H_502_29@++num;
        }
        if((root@H_502_29@->_col @H_502_29@== RED) @H_502_29@&& (root@H_502_29@->_parent) @H_502_29@&& (root@H_502_29@->_parent@H_502_29@->_col @H_502_29@== RED))
        {
            cout @H_502_29@<< "有连续的红节点" @H_502_29@<< root@H_502_29@->_key @H_502_29@<< endl;
            return false;
        }
        return _IsBlance(root@H_502_29@->_left,num)
            @H_502_29@&& _IsBlance(root@H_502_29@->_right,num);
    }

    //右旋
    void RotateR(Node@H_502_29@* parent)
    {
        Node@H_502_29@* subL @H_502_29@= parent@H_502_29@->_left;
        Node@H_502_29@* subLR @H_502_29@= subL@H_502_29@->_right;
        parent@H_502_29@->_left @H_502_29@= subLR;
        if (subLR)
            subLR@H_502_29@->_parent @H_502_29@= parent;

        subL@H_502_29@->_right @H_502_29@= parent;
        Node@H_502_29@* ppNode @H_502_29@= parent@H_502_29@->_parent;
        parent@H_502_29@->_parent @H_502_29@= subL;

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

    //左旋
    void RotateL(Node@H_502_29@* parent)
    {
        Node@H_502_29@* subR @H_502_29@= parent@H_502_29@->_right;
        Node@H_502_29@* subRL @H_502_29@= subR@H_502_29@->_left;

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

        subR@H_502_29@->_left @H_502_29@= parent;
        Node@H_502_29@* ppNode @H_502_29@= parent@H_502_29@->_parent;
        parent@H_502_29@->_parent @H_502_29@= subR;

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

    void _InOrder(Node@H_502_29@* root)
    {
        Node@H_502_29@* cur @H_502_29@= root;
        if (cur @H_502_29@== NULL)
            return;
        _InOrder(cur@H_502_29@->_left);
        cout @H_502_29@<< cur@H_502_29@->_key @H_502_29@<< " ";
        _InOrder(cur@H_502_29@->_right);
    }
private:
    Node@H_502_29@* _root;
};

void TestRBTree()
{
    RBTree@H_502_29@<int,int@H_502_29@> t;
    int a[] = { 16,3,7,11,9,26,18,14,15 }; for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) { t.Insert(a[i],i); } t.InOrder(); cout << endl; cout << "IsBalance?" << t.IsBalance() << endl; }

我们知道，红黑树是近似平衡的二叉树，那么为什么不直接使用平衡二叉树呢？
原因是红黑树最坏的情况也是log2^N,但它不像平衡二叉树需要严格控制平衡因子，红黑树只需控制节点的颜色，因此它的旋转次数相对于平衡二叉树能少一些，因此，实际中，红黑树的应用更为广泛。

红黑树的应用： 1. C++ STL库 – map 2. Java 库 3. linux内核 4. 其他一些库

【数据结构】：红黑树（RB Tree）

猜你在找的数据结构相关文章