C++数据结构之红黑树的实现

目录
  • 一、什么是红黑树
  • 二、红黑树的约定
  • 三、红黑树vsAVL
  • 四、红黑树的实现
    • 1.找到插入的位置
    • 2.控制平衡
    • 3.测试代码
  • 五、完整代码
    • 1.test.c
    • 2.RBTree.h

一、什么是红黑树

红黑树在表意上就是一棵每个节点带有颜色的二叉搜索树,并通过对节点颜色的控制,使该二叉搜索树达到尽量平衡的状态。所谓尽量平衡的状态就是:红黑树确保没有一条路径比其他路径长两倍。

和AVL树不同的是,AVL树是一棵平衡树,而红黑树可能平衡也可能不平衡(因为是尽量平衡的状态)

二、红黑树的约定

要实现一棵红黑树,即要红黑树确保没有一条路径比其他路径长两倍。通过对节点颜色的约定来实现这一目标。

1.根节点是黑色的。

2.如果一个节点是红色的,则它的两个孩子都是黑色的。

3.对于每个节点,从该节点到其所有后代节点的简单路径上,均包含相同数量的黑色节点。

实现了这三条颜色规则的二叉搜索树,即也实现了没有一条路径比其他路径长两倍,即实现了一棵红黑树。

三、红黑树vsAVL

1、调整平衡的实现机制不同

红黑树根据节点颜色(同一父节点出发到叶子节点,所有路径上的黑色节点数目一样),一些约定和旋转实现。

AVL根据树的平衡因子(所有节点的左右子树高度差的绝对值不超过1)和旋转决定。

2、红黑树的插入效率更高

红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内解决,红黑树并不追求“完全平衡”,它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能

而AVL是严格平衡树(高度平衡的二叉搜索树),因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多。所以红黑树的插入效率更高

3、AVL查找效率高

如果你的应用中,查询的次数远远大于插入和删除,那么选择AVL树,如果查询和插入删除次数几乎差不多,应选择红黑树。即,有时仅为了排序(建立-遍历-删除),不查找或查找次数很少,R-B树合算一些。

四、红黑树的实现

实现一棵红黑树,本质是实现它的插入函数,使插入函数可以实现红黑树的颜色约定,它的实现分为两步,即先找到插入的位置,再控制平衡。插入函数返回值设计为bool,插入成功返回true,失败返回false。控制平衡时,需要关注四个节点,即新插入的节点,它的父节点,它的叔叔节点,它的祖父节点。

1.找到插入的位置

当为第一个节点的时候,颜色设为黑,直接插入。

当插入的不是第一个节点时,颜色设为红,需要根据二叉搜索树的性质找到插入位置。并实现三叉链。

        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 < kv.first)
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_left = cur;
            cur->_parent = parent;
        }

2.控制平衡

(1)当父节点为黑

当父节点为黑的时候,由于插入的子节点的颜色为红,对三个约定没有任何影响,因此不需要调整平衡。

(2)判断父节点在祖父节点的位置

通过判断父节点在祖父节点的位置,来定义叔叔节点的位置,以及之后的旋转方向的判断。

while (parent && parent->_col == Red)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
   Node* uncle = grandfather->_right;
   //三种情况的处理
}
else
{
   Node* uncle = grandfather->_left;
   //三种情况的处理
}

首先需要使用大循环,这个循环是为情况1而准备的,情况2和3直接跳出循环即可,因为只有情况1对上层循环有影响。
下面我们以父节点在祖父节点的左侧为例,右侧同理。

(3)叔叔节点存在且为红

解决方案:将父节点和叔叔节点设为黑,将祖父节点设为红。然后将祖父节点作为新节点继续向上平衡。如果祖父节点是根节点,那么需要再将其置为黑。

注意,这种情况和其他情况不同的是,需要将祖父节点作为新插入的节点继续向上遍历,这说明需要一个循环。而其他类型的情况直接break跳出这个循环即可。

//第一种情况
if (uncle && uncle->_col == Red)
{
    parent->_col = uncle->_col = Black;
    grandfather->_col = Red;
    cur = grandfather;
    parent = cur->_parent;
}

这种情况只需要控制颜色即可,但是要继续向上循环。

(4)父节点为红,叔叔不存在或存在且为黑,新插入的节点在父节点左侧

解决方案:对祖父节点右旋操作,并将祖父节点置为红,父节点置为黑。

关于旋转的细节,我在AVL树中有详细的解释:C++手撕AVL树

//第二种情况,右单旋
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = Black;
grandfather->_col = Red;
}

(5)父节点为红,叔叔不存在或存在且为黑,新插入的节点在父节点右侧

解决方案:进行双旋,即对父节点进行左单旋,祖父节点进行右单旋。将子节点置为黑,将祖父节点置为红。

else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = Black;
grandfather->_col = Red;
}

(6)最后置黑

每一次插入都对根节点置为黑操作,因为第一种情况可能导致根节点不是黑。同时对根节点置黑也并不违反三条规定。

3.测试代码

当我们处理完父节点在祖父节点的左侧后,处理父节点在祖父节点的右侧。

全部处理之后,我们的插入代码就完成了,接下来要对整个树进行测试,即对三个约定来进行测试:

1.当根节点为红时,返回false。

2.判断一个节点和其父节点的颜色是否都为红,若都为红返回false。

3.以最左的一条路径上的根节点数量为基准,通过递归遍历每一条路径上的根节点的数量,当每条路径遍历节点到空时,将两者进行比较,如果最终结果不相等则返回false。

    bool IsBalance()
    {
        if (_root && _root->_col == Red)
        {
            cout << "根节点不是黑色的" << endl;
            return false;
        }
        int banchmark = 0;
        //以最右边一条路径为基准
        Node* left = _root;
        while (left)
        {
            if (left->_col == Black)
            {
                ++banchmark;
            }
            left = left->_left;
        }
        int blackNum = 0;
        return _IsBalance(_root, banchmark, blackNum);
    }
    bool _IsBalance(Node* root, int banchmark, int blackNum)
    {
        if (root == nullptr)
        {
            if (banchmark != blackNum)
            {
                cout << "黑色根节点数目不相等" << endl;
                return false;
            }
            return true;
        }
        if (root->_col == Red && root->_parent->_col == Red)
        {
            cout << "出现连续的红色节点" << endl;
            return false;
        }
        if (root->_col == Black)
        {
            ++blackNum;
        }
        return _IsBalance(root->_left, banchmark, blackNum) && _IsBalance(root->_right, banchmark, blackNum);
    }

五、完整代码

1.test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"RBtree.h"
#include<vector>
int main()
{
    RBTree<int, int> t;
    vector<int> v;
    srand(time(0));
    int N = 100000;
    int count = 0;
    for (int i = 0; i < N; i++)
    {
        v.push_back(rand());
    }
    for (auto e : v)
    {
        pair<int,int> kv(e, e);
        t.insert(kv);
        if (t.IsBalance())
        {
            cout << "insert" << e << endl;
            count++;
            cout << count << endl;
        }
        else
        {
            cout << e << "插入失败" << endl;
            cout << "不是平衡的" << endl;
            break;
        }
    }
}

2.RBTree.h

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
enum Color
{
    Red,
    Black
};
template<class K,class V>
struct RBTreeNode
{
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    pair<K, V> _kv;
    Color _col;
    RBTreeNode(pair<K, V>& kv)
        :_left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _col(Red)
        , _kv(kv)
    {}
};
template<class K,class V>
struct RBTree
{
    typedef RBTreeNode<K, V> Node;
private:
    Node* _root;
public:
    RBTree()
        :_root(nullptr)
    {}
    bool IsBalance()
    {
        if (_root && _root->_col == Red)
        {
            cout << "根节点不是黑色的" << endl;
            return false;
        }
        int banchmark = 0;
        //以最右边一条路径为基准
        Node* left = _root;
        while (left)
        {
            if (left->_col == Black)
            {
                ++banchmark;
            }
            left = left->_left;
        }
        int blackNum = 0;
        return _IsBalance(_root, banchmark, blackNum);
    }
    bool _IsBalance(Node* root, int banchmark, int blackNum)
    {
        if (root == nullptr)
        {
            if (banchmark != blackNum)
            {
                cout << "黑色根节点数目不相等" << endl;
                return false;
            }
            return true;
        }
        if (root->_col == Red && root->_parent->_col == Red)
        {
            cout << "出现连续的红色节点" << endl;
            return false;
        }
        if (root->_col == Black)
        {
            ++blackNum;
        }
        return _IsBalance(root->_left, banchmark, blackNum) && _IsBalance(root->_right, banchmark, blackNum);
    }
    //右单旋
    void RotateR(Node* parent)
    {
        Node* cur = parent->_left;
        Node* curL = cur->_left;
        Node* curR = cur->_right;
        Node* parentParent = parent->_parent;
        parent->_left = curR;
        if (curR)
            curR->_parent = parent;
        cur->_right = parent;
        parent->_parent = cur;
        if (parent == _root)
        {
            _root = cur;
            _root->_parent = nullptr;
        }
        else
        {
            if (parentParent->_left == parent)
            {
                parentParent->_left = cur;
                cur->_parent = parentParent;
            }
            else if (parentParent->_right == parent)
            {
                parentParent->_right = cur;
                cur->_parent = parentParent;
            }
            else
            {
                assert(false);
            }
        }
    }
    //左单旋
    void RotateL(Node* parent)
    {
        Node* cur = parent->_right;
        Node* curL = cur->_left;
        Node* parentParent = parent->_parent;
        parent->_right = curL;
        if (curL)
            curL->_parent = parent;
        cur->_left = parent;
        parent->_parent = cur;
        if (parent == _root)
        {
            _root = cur;
            _root->_parent = nullptr;
        }
        else
        {
            if (parentParent->_left == parent)
            {
                parentParent->_left = cur;
                cur->_parent = parentParent;
            }
            else if (parentParent->_right == parent)
            {
                parentParent->_right = cur;
                cur->_parent = parentParent;
            }
            else
            {
                assert(false);
            }
        }
    }
    bool insert(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 < 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->_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 (cur == parent->_left)
                    {
                        RotateR(grandfather);
                        parent->_col = Black;
                        grandfather->_col = Red;
                    }
                    //第三种情况,左右双旋
                    else
                    {
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = Black;
                        grandfather->_col = Red;
                    }
                    break;
                }
                _root->_col = Black;
            }
            else
            {
                Node* uncle = grandfather->_left;
                //第一种情况
                if (uncle && uncle->_col == Red)
                {
                    parent->_col = uncle->_col = Black;
                    grandfather->_col = Red;
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else
                {
                    //第二种情况,左单旋
                    if (cur == parent->_right)
                    {
                        RotateL(grandfather);
                        parent->_col = Black;
                        grandfather->_col = Red;
                    }
                    //第三种情况,右左双旋
                    else
                    {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = Black;
                        grandfather->_col = Red;
                    }
                    break;
                }
                _root->_col = Black;
            }
        }
    }
};

到此这篇关于C++数据结构之红黑树的实现的文章就介绍到这了,更多相关C++红黑树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现红黑树应用实例代码

    红黑树的应用: 1.利用key_value对,快速查找,O(logn) socket与客户端id之间,形成映射关系(socket, id) 内存分配管理 一整块内存,不断分配小块 每分配一次,就加入到红黑树 释放的时候,在红黑树找到相应的块,然后去释放 2.利用红黑树中序遍历是顺序的特性 进程的调度 进程处于等待状态,每个进程都有等待的时间,在未来某个时刻会运行,将这些进程利用红黑树组织起来 在某个时刻,找到对应时刻的节点,然后中序遍历,就可以把该节点之前的节点全部运行到. 3.nginx定时器

  • C++详细实现红黑树流程详解

    目录 红黑树的概念 红黑树的性质 红黑树的定义与树结构 插入 新增结点插入后维护红黑树性质的主逻辑 旋转 验证 红黑树与AVl树的比较 红黑树的应用 红黑树的概念 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black. 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的 概念总结: 红黑树是二叉搜索树的升级,结点里面存放的成员col标记当前结点的颜色,它的最长路径最多是最短路径的二倍,红黑

  • C++数据结构红黑树全面分析

    目录 概念和性质 红黑树的实现

  • C++ STL容器详解之红黑树部分模拟实现

    目录 一.红黑树的概念 二.红黑树的性质 三.红黑树节点的定义 四.红黑树结构  五. 红黑树的插入操作 六.代码 总结 一.红黑树的概念 红黑树(Red Black Tree),是在计算机科学中用到的一种数据结构,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black. 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的. 二.红黑树的性质 1. 每个结点不是红色就是黑色: 2. 根节点是黑色的:

  • C++超详细分析红黑树

    目录 红黑树 红黑树的概念 红黑树的性质 红黑树结点的定义 红黑树的插入操作 情况一 情况二 情况三 红黑树的验证 用红黑树封装map.set 红黑树的迭代器 封装map 封装set 红黑树 红黑树的概念 红黑树的概念 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black. 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的. 红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是

  • C++数据结构之红黑树的实现

    目录 一.什么是红黑树 二.红黑树的约定 三.红黑树vsAVL 四.红黑树的实现 1.找到插入的位置 2.控制平衡 3.测试代码 五.完整代码 1.test.c 2.RBTree.h 一.什么是红黑树 红黑树在表意上就是一棵每个节点带有颜色的二叉搜索树,并通过对节点颜色的控制,使该二叉搜索树达到尽量平衡的状态.所谓尽量平衡的状态就是:红黑树确保没有一条路径比其他路径长两倍. 和AVL树不同的是,AVL树是一棵平衡树,而红黑树可能平衡也可能不平衡(因为是尽量平衡的状态) 二.红黑树的约定 要实现一

  • Java数据结构之红黑树的原理及实现

    目录 为什么要有红黑树这种数据结构 红黑树的简介 红黑树的基本操作之旋转 红黑树之添加元素 红黑树之删除结点 删除结点没有儿子的情况 删除结点仅有一个儿子结点的情况 删除结点有两个儿子结点 红黑树动态可视化网站 红黑树参考代码 为什么要有红黑树这种数据结构 我们知道ALV树是一种严格按照定义来实现的平衡二叉查找树,所以它查找的效率非常稳定,为O(log n),由于其严格按照左右子树高度差不大于1的规则,插入和删除操作中需要大量且复杂的操作来保持ALV树的平衡(左旋和右旋),因此ALV树适用于大量

  • Java数据结构之红黑树的真正理解

    真正的帮助大家理解红黑树: 一.红黑树所处数据结构的位置: 在JDK源码中, 有treeMap和JDK8的HashMap都用到了红黑树去存储 红黑树可以看成B树的一种: 从二叉树看,红黑树是一颗相对平衡的二叉树 二叉树-->搜索二叉树-->平衡搜索二叉树--> 红黑树 从N阶树看,红黑树就是一颗 2-3-4树 N阶树-->B(B-)树 故我提取出了红黑树部分的源码,去说明红黑树的理解 看之前,理解红黑树的几个特性,后面的操作都是为了让树符合红黑树的这几个特性,从而满足对查找效率的O

  • 数据结构之红黑树详解

    1.简介 红黑树是一种自平衡二叉查找树.它的统计性能要好于平衡二叉树(AVL树),因此,红黑树在很多地方都有应用.在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及对set操作的支持).它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除等操作. 本文介绍了红黑树的基本性质和基本操作. 2.红黑树

  • 红黑树的插入详解及Javascript实现方法示例

    红黑树的性质 一棵满足以下性质的二叉搜索树是一棵红黑树 每个结点或是黑色或是红色. 根结点是黑色的. 每个叶结点(NIL)是黑色的. 如果一个结点是红色的,则它的两个子结点都是黑色的. 对每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点. 性质1和性质2,不用做过多解释. 性质3,每个叶结点(NIL)是黑色的.这里的叶结点并不是指上图中结点1,5,8,15,而是指下图中值为null的结点,它们的颜色为黑色,且是它们父结点的子结点. 性质4,如果一个结点是红色的(图中用白

  • 数据结构 红黑树的详解

    数据结构 红黑树的详解 红黑树是具有下列着色性质的二叉查找树: 1.每一个节点或者着红色,或者着黑色. 2.根是黑色的. 3.如果一个节点是红色的,那么它的子节点必须是黑色. 4.从一个节点到一个NULL指针的每一条路径必须包含相同数目的黑色节点. 下面是一棵红黑树. 1.自底向上插入 通常把新项作为树叶放到树中.如果我们把该项涂成黑色,那么违反条件4,因为将会建立一条更长的黑节点路径.因此这一项必须涂成红色.如果它的父节点是黑色的,插入完成.如果父节点是红色的,那么违反条件3.在这种情况下我们

  • Java 数据结构与算法系列精讲之红黑树

    目录 概述 红黑树 红黑树的实现 Node类 添加元素 左旋 右旋 完整代码 概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 红黑树 红黑树 (Red Black Tree) 是一种自平衡二叉查找树. 如图: 红黑树的特征: 研究红黑树的每个节点都是由颜色的, 非黑即红 根节点为黑色 每个叶子节点都是黑色的 如果一个子节点是红色的, 那么它的孩子节点都是黑色的 从任何一个节点到叶子节点, 经过的黑色节点是一样的 红黑树的实现 Node 类 // Node类 pri

  • Java红黑树的数据结构与算法解析

    目录 红黑树的介绍 红黑树的实现 1.节点 2.查找 3.平衡化 颜色反转 插入的实现 红黑树的复杂度– 总结 红黑树的介绍 红黑树(Red-Black Tree,简称R-B Tree),它一种特殊的二叉查找树. 红黑树是特殊的二叉查找树,意味着它满足二叉查找树的特征:任意一个节点所包含的键值,大于等于左孩子的键值,小于等于右孩子的键值. 除了具备该特性之外,红黑树还包括许多额外的信息. 红黑树的每个节点上都有存储位表示节点的颜色,颜色是红(Red)或黑(Black). 红黑树的特性: (1)

  • java中treemap和treeset实现红黑树

    TreeMap 的实现就是红黑树数据结构,也就说是一棵自平衡的排序二叉树,这样就可以保证当需要快速检索指定节点. TreeSet 和 TreeMap 的关系 为了让大家了解 TreeMap 和 TreeSet 之间的关系,下面先看 TreeSet 类的部分源代码: public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializab

随机推荐