[C++]从0

您所在的位置：网站首页 › set红黑树 › [C++]从0

[C++]从0

2024-07-17 08:28:58| 来源: 网络整理| 查看: 265

红黑树

红黑树是一种树形数据结构，其是由AVL树改良而得的。

AVL树的缺陷：

对于AVL树，他的发明人真的十分厉害，它通过调整平衡因子使树达到平衡，从而使高度达到最低，大大加快了遍历速度。但是有一种开销却在不知不觉中产生：调整平衡因子过程中的旋转开销。

而红黑树通过减少旋转次数来使这种构造开销降低，但是从理论上来讲，红黑树的遍历肯定没有AVL树快，但是他的构造相比AVL树就少了数次的旋转，开销大大降低。

由于其根本上还是一个平衡二叉树的属性，所以他的旋转操作与AVL树大差不差，整体思路也大致相同，唯一不同的就是其旋转的条件。这一点就不过多叙述。假设我们已经有了一个红黑树的数据结构，那么我们如何将其封装成map、set呢？

//代码稍长，通过注释标出了重点 //标记节点的颜色 enum Color { RED, BLACK }; //每个节点的数据 template struct RBTreeNode { //具有指向左、右和父亲的指针，方便调整平衡 RBTreeNode* _left; RBTreeNode* _right; RBTreeNode* _parent; T _data; Color _col; RBTreeNode(const T& data=T()) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_data(data) ,_col(RED) { } }; template class RBTree { typedef RBTreeNode Node; public: RBTree() { _pHead = new Node; _pHead->_left = _pHead; _pHead->_right = _pHead; } // 在红黑树中插入值为data的节点，插入成功返回true，否则返回false // 注意：为了简单起见，本次实现红黑树不存储重复性元素 bool Insert(const T& data) { //节点的插入操作 Node* newnode = new Node(data); if (_pHead->_left == _pHead) { _pHead->_left = newnode; _pHead->_right = newnode; newnode->_col = BLACK; newnode->_parent = _pHead; return true; } Node* cur = _pHead->_left; Node* parent = _pHead; while (cur) { parent = cur; if (data > cur->_data) { cur = cur->_right; } else if (data < cur->_data) { cur = cur->_left; } else { return false; } } if (data < parent->_data) { parent->_left = newnode; } else { parent->_right = newnode; } newnode->_parent = parent; cur = newnode; //红黑树的操作 while (parent!=_pHead && parent->_col == RED) { Node* grandfather = parent->_parent; if (parent==grandfather->_left)//p是g的左孩子 { Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED)//叔叔存在且为红 { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else//叔叔不存在,或叔叔为黑 { if (cur == parent->_left)//g，p，c同侧---单旋 { RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else//g，p，c不同侧---双旋 { RotateL(parent); RotateR(grandfather); grandfather->_col = RED; cur->_col = BLACK; } break; } } else//p是g的右孩子 { Node* uncle = grandfather->_left; if (uncle && uncle->_col == RED)//叔叔存在且为红 { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else//叔叔不存在,或叔叔为黑 { if (cur==parent->_right)//g，p，c同侧---单旋 { RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else//g，p，c不同侧---双旋 { RotateR(parent); RotateL(grandfather); grandfather->_col = RED; cur->_col = BLACK; } break; } } } _pHead->_left->_col = BLACK; return true; } // 检测红黑树中是否存在值为data的节点，存在返回该节点的地址，否则返回nullptr Node* Find(const T& data) { return _Find(_pHead, data); } // 获取红黑树最左侧节点 Node* LeftMost() { if (_pHead->_left == _pHead) { assert(0); return nullptr; } Node* cur = _pHead->_left; while (cur->_left) { cur = cur->_left; } return cur; } // 获取红黑树最右侧节点 Node* RightMost() { if (_pHead->_left == _pHead) { assert(0); return nullptr; } Node* cur = _pHead->_right; while (cur->_right) { cur = cur->_right; } return cur; } // 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测 bool IsValidRBTRee() { Node* cur = GetRoot(); if (cur == _pHead) return true; if (cur->_col == RED) return false; int blackCount = 0; while (cur) { if(cur->_col==BLACK) blackCount++; cur = cur->_left; } int pathBlack = 0; return _IsValidRBTRee(_pHead->_left,blackCount,pathBlack); } private: Node* _Find(Node* cur, const T& data) { if (cur == nullptr) return nullptr; if (cur->_data == data) return cur; Node* retl = _Find(cur->_left, data); if (retl != nullptr) return retl; Node* retr = _Find(cur->_right, data); if (retr != nullptr) return retr; return nullptr; } bool _IsValidRBTRee(Node* cur, size_t blackCount, size_t pathBlack) { if (cur == nullptr) { if (pathBlack == blackCount) return true; else return false; } if (cur->_col == RED && cur->_parent->_col == RED) return false; if (cur->_col == BLACK) pathBlack++; return _IsValidRBTRee(cur->_left, blackCount, pathBlack) && _IsValidRBTRee(cur->_right, blackCount, pathBlack); } // 左单旋 void RotateL(Node* pParent) { Node* subR = pParent->_right; Node* subRL = subR->_left; Node* grandfather = pParent->_parent; if (subRL) { subRL->_parent = pParent; } pParent->_right = subRL; subR->_left = pParent; pParent->_parent = subR; if (grandfather == _pHead) { _pHead->_left = _pHead->_right = subR; } else if(grandfather->_left == pParent) { grandfather->_left = subR; } else { grandfather->_right = subR; } subR->_parent = grandfather; } // 右单旋 void RotateR(Node* pParent) { Node* subL = pParent->_left; Node* subLR = subL->_right; Node* grandfather = pParent->_parent; if (subLR) { subLR->_parent = pParent; } pParent->_left = subLR; subL->_right = pParent; pParent->_parent = subL; if (grandfather == _pHead) { _pHead->_left = _pHead->_right = subL; } else if (grandfather->_left == pParent) { grandfather->_left = subL; } else { grandfather->_right = subL; } subL->_parent = grandfather; } // 为了操作树简单起见：获取根节点 Node*& GetRoot() { return _pHead->_left; } private: Node* _pHead; }; map&set 底层实现存储元素存储元素的位置map红黑树K(key),V(value)根据K的比较方式有规律存储set红黑树K根据K的比较方式有规律存储unordered_map哈希桶K,V根据K的哈希映射存储到对应位置unordered_set哈希桶K根据K的哈希映射存储到对应位置封装前的准备

我们根据STL中map、set的标准对红黑树进行简单的封装，其中主要实现插入操作和迭代器。

改造红黑树

由于map和set的类模板参数个数不同，传参也不同，所以如果我们想要只写一个红黑树来实现复用，那么我们必须对红黑树进行改造，使其能同时接受map、set的传参

template < class Key, // map::key_type class T, // map::mapped_type class Compare = less, // map::key_compare class Alloc = allocator // map::allocator_type > class map; template < class T, // set::key_type/value_type class Compare = less, // set::key_compare/value_compare class Alloc = allocator // set::allocator_type > class set;

我们先来看map、set的几个需求：

对数据进行插入

对于set，我们需要插入的是key；而对于map，我们需要插入的是(key,value)。这就决定了红黑树中插入的元素要写成模板参数，且这个模板参数应该是由map、set传进来的（思考一下，我们需要几个模板参数来接受）。

但是这时候就会产生一个问题，我们的插入操作需要对其key值进行比较，而set的key好比较（直接key1>key2比较就行），但是map的是pair（采用不了pair1 > pair2的操作），所以我们用传统的比较是解决不了的。这就决定了我们需要提供一个玩意来获取其中用来比较的值（这个玩意可以让我们传set时用他的key，而传map时又能获取他的key）。

对数据进行查找

假设：红黑树的类模板是template ，这个T是要插入的数据。那么当我要查找某个数据时，对于set，我可以直接用T，因为T就是我要查找的key值；但是对于map，我不能直接用T（因为其是pair），我想要查找的是其中的key，所以注定不能用T找到目标，这就决定了需要传给红黑树一个参数来告诉他我的key是什么类型的。

主要就是以上两点，而对于比较器，由于std中有less、greater且map、set都可以给默认的class Compare=less，所以我们实现不实现都可以。

①插入的数据如何传入

我们不可能为了map而去增加一个模板参数，这样我们的set就会很为难，而存储数据的时候更为难，如下：

template class map { RBTree _tree; }; template class set { RBTree _tree;//只能这样写，因为需要两个参数 }; template class RBTree { void insert1(const pair& kv)//用哪个呢？ { } void insert2(const K& k)//用哪个呢？ { } void insert3(const V& v)//用哪个呢？ { } };

如果用const pair& kv，那当使用insert1时，set就变成了k，v了；当使用insert2时，map右没了k，v了；insert3就更离谱了。所以应该改成如下格式：

template class map { RBTree _tree;//用一个pair传入k，v }; template class set { RBTree _tree; }; template class RBTree { void insert(const Data& data) { } };

我们只用一个模板参数来接受他们的传参，而map传pair，set传key。那么问题又来了，当我传入map时，我能直接用data1>data2比较吗？显然不能！所以我们还需要传入一个小玩意（仿函数）是他们具有能比较的功能。于是乎，最终版本如下：

template class map { struct KeyOfmap() { const K& operator(const pair& kv) { return kv.first; } } RBTree _tree;//用一个pair传入k，v }; template class set { struct KeyOfset() { const K& operator(const K& k) { return k; } } RBTree _tree; }; template class RBTree { void insert(const Data& data) { KeyOfVal()(data1)>KeyOfVal()(data2);//使用临时对象来取出data中的key值，再用key值进行比较 } };

为map、set增加一个仿函数并传给红黑树，使其能通过该仿函数取出map、set中的key值

②数据如何查找

template class map { struct KeyOfmap() { const K& operator(const pair& kv) { return kv.first; } } bool find(K k) { _tree.find(k); } RBTree _tree;//用一个pair传入k，v }; template class set { struct KeyOfset() { const K& operator(const K& k) { return k; } } bool find(K k) { _tree.find(k); } RBTree _tree; }; template class RBTree { void insert(const Data& data) { KeyOfVal()(data1)>KeyOfVal()(data2);//使用临时对象来取出data中的key值 } bool find(const Data& data) { } };

如果使用这种方法，我们会发现红黑树的find()能当实参的类型只有Data，当然在，这样map就不能执行find操作了（因为我们要用key进行查找，而不是pair），所以我们必须要让红黑树知道我们要查找的类型是啥，所以如下就是最最最终版本。

我们就给红黑树类模板多加一个参数，告诉他我们要查找的类型。

如上我们的准备工作就做好了。

insert的实现

有了前期的准备，现在的insert就是如鱼得水，对于insert我们需要的步骤如下：

比较他们的key值，然后放入该二叉树中（这个key值的比较我们已经能够实现）插入完成后更新节点颜色如果达到需要旋转条件，则进行旋转

可见，这就是很简单的红黑树的插入，再接下来就是迭代器！

迭代器的实现

前提准备：

对于红黑树的遍历，我们往往都是采用中序遍历，这样得到的将会是一个有序数组。而该迭代器一般不需要–操作，所以其主要操作是operator++ operator-> operator* operator== operator!=。而其中operator++实现的就是中序遍历的找下一个要遍历位置

① ++是如何找到下一个位置的

8 6 15 3 9 17 1 4 如果从1出发，则++后访问到的是3如果从4出发，则++后访问到的是6如果从8出发，则++后访问到的是9

总结下来就一句话：先找右孩子的最左孩子，如果没有，就往父节点找，直到找到自己是某个节点的左孩子位置（如果一直走到根节点都不满足，就说明该节点已经是最后一个节点了，到end()了），该节点就是++后的节点

代码如下：

RBTreeIterator& operator++() { if (_node->_right)//如果有右孩子，就找右孩子的最左孩子 { Node* subLeft = _node->_right; while (subLeft->_left) { subLeft = subLeft->_left; } _node = subLeft; } else//如果没有右孩子，就找父亲 { Node* cur = _node; Node* parent = cur->_parent; while (parent && cur == parent->_right)//找到满足的节点或者个节点为止 { cur = parent; parent = cur->_parent; } _node = parent; } return *this; }

②begin()、end()方法

begin()直接找最左节点就行（没错！就是一直tmp=tmp->left就行）

end()直接找最右节点就行（没错！就是一直tmp=tmp->right就行）

最后我们将map、set中的begin(),end(),insert()…套一层红黑树中对应的函数就行了

完整代码：

//map： #include"RBTree.h" namespace sll { template class map { struct MapKeyOfT { const K& operator()(const pair& kv) { return kv.first; } }; public: typedef typename RBTree::iterator iterator; iterator begin() { return _tree.begin(); } iterator end() { return _tree.end(); } bool insert(const pair& kv) { return _tree.insert(kv); } private: typedef RBTree Node; Node _tree;//has-a关系 }; void mapTest() { map s1; int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; for (auto e : a) { s1.insert({e,e}); } map::iterator it = s1.begin(); while (it != s1.end()) { cout first _right; while (subLeft->_left) { subLeft = subLeft->_left; } _node = subLeft; } else { Node* cur = _node; Node* parent = cur->_parent; while (parent && cur == parent->_right) { cur = parent; parent = cur->_parent; } _node = parent; } return *this; } bool operator!=(const self& cmp) { return _node != cmp._node; } bool operator==(const self& cmp) { return _node == cmp._node; } }; //这里的模板参数，第一个用来做一些查找等系类操作，存储的类型是T //KOfT是取出存储模型中用于比较的函数 template class RBTree { typedef RBTreeNode Node; public: typedef RBTreeIterator iterator; iterator begin() { Node* cur = _root; while (cur && cur->_left) { cur = cur->_left; } return cur; } iterator end() { return nullptr; } bool insert(const T& data) { if (_root == nullptr) { _root = new Node(data); _root->_col = BLACK; return true; } KeyOfT kot; Node* cur = _root; Node* parent = nullptr; while (cur) { parent = cur; if (kot(data) > kot(cur->_data)) { cur = cur->_right; } else { cur = cur->_left; } } cur = new Node(data); if (kot(data)> kot(parent->_data)) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; //插入完毕，开始红黑树操作 while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; if (parent==grandfather->_left)//当插入节点在爷爷的左边 { Node* uncle = grandfather->_right; //情况1：舅舅是红色 if (uncle && uncle->_col == RED) { uncle->_col = BLACK; parent->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else//情况2：舅舅不是红色 { //单旋 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//当插入节点在爷爷的右边 { Node* uncle = grandfather->_left; //情况1：舅舅是红色 if (uncle && uncle->_col == RED) { uncle->_col = BLACK; parent->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else//情况2：舅舅不是红色 { //单旋 if (cur == parent->_right) { RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } else//双旋 { RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return true; } void print() { return _print(_root); } private: void _print(Node* cur) { if (cur == nullptr) return; _print(cur->_left); cout _kv.first _right); } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; Node* pparent = parent->_parent; parent->_parent = subL; subL->_right = parent; parent->_left = subLR; if (subLR) { subLR->_parent = parent; } if (!pparent) { _root = subL; subL->_parent = nullptr; } else { if (pparent->_left == parent) { pparent->_left = subL; } else { pparent->_right = subL; } subL->_parent = pparent; } } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; Node* pparent = parent->_parent; parent->_parent = subR; subR->_left = parent; parent->_right = subRL; if (subRL) { subRL->_parent = parent; } if (!pparent) { _root = subR; subR->_parent = nullptr; } else { if (pparent->_left == parent) { pparent->_left = subR; } else { pparent->_right = subR; } subR->_parent = pparent; } } Node* _root = nullptr; };

【本文地址】

公司简介

联系我们

今日新闻

点击排行

实验室常用的仪器、试剂和: 说到实验室常用到的东西，主要就分为仪器、试剂和耗

不用再找了，全球10大实验: 01、赛默飞世尔科技（热电）Thermo Fisher Scientif

三代水柜的量产巅峰T-72坦: 作者：寞寒最近，西边闹腾挺大，本来小寞以为忙完这

通风柜跟实验室通风系统有: 说到通风柜跟实验室通风，不少人都纠结二者到底是不

集消毒杀菌、烘干收纳为一: 厨房是家里细菌较多的地方，潮湿的环境、没有完全密

实验室设备之全钢实验台如: 全钢实验台是实验室家具中较为重要的家具之一，很多

图片新闻

实验室药品柜的特性有哪些: 实验室药品柜是实验室家具的重要组成部分之一，主要

小学科学实验中有哪些教学: 计算机计算器一般打孔器打气筒仪器车显微镜

实验室各种仪器原理动图讲: 1.紫外分光光谱UV分析原理：吸收紫外光能量，引起分

高中化学常见仪器及实验装: 1、可加热仪器：2、计量仪器：（1）仪器A的名称：量

微生物操作主要设备和器具: 今天盘点一下微生物操作主要设备和器具，别嫌我啰嗦

浅谈通风柜使用基本常识: 　众所周知，通风柜功能中最主要的就是排气功能。在

[C++]从0

[C++]从0

今日新闻

点击排行

推荐新闻

图片新闻

专题文章