昆山移动网站建设,网站架构设计师月薪多少,太原王建设,建设网站以后#x1f525;个人主页#xff1a; Forcible Bug Maker #x1f525;专栏#xff1a; C || 数据结构 目录 #x1f308;前言#x1f525;红黑树的概念#x1f525;手撕红黑树红黑树结点的定义红黑树主体需要实现的成员函数红黑树的插入findEmpty和Size拷贝构造析构函数和…
个人主页 Forcible Bug Maker 专栏 C || 数据结构 目录 前言红黑树的概念手撕红黑树红黑树结点的定义红黑树主体需要实现的成员函数红黑树的插入findEmpty和Size拷贝构造析构函数和clear检测是否为合法红黑树Begin和End 红黑树的迭代器接口* 解引用和 - 访问operator()operator- - ()迭代器比较相等 结语 前言 本篇博客主要内容红黑树的介绍以及底层代码逻辑和实现。 刚刚接触编程的时候就听说有的大厂HR会让手撕红黑树。心中一直对这个数据结构保持着敬畏和向往今天在将其撕出来后用本篇博客加以记录望周知。
红黑树的概念
红黑树也是一种二叉搜索树但再每个结点上增加一个存储位置表示结点的颜色可以是RED红或BLACK黑。通过对任何一条根到叶子的路径上各个结点的着色方式的限制红黑树确保没有一条路径会比其他路径长出两倍因而是接近平衡的。 一颗红黑树是具有如下性质的二叉搜索树
每个结点不是红色就是黑色根结点是黑色的如果一个结点是红色则它的两个孩子结点是黑色即不会有连续的红结点对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点每个叶子结点都是黑色的此处的叶子结点指的是空结点NIL 其中3和4是最重要的两点。 手撕红黑树
红黑树结点的定义
红黑树的结点包含四个成员变量模板类型T可以存储K或者pairK,V类型便于后期封装三个指针分别为指向左孩子结点的指针指向右孩子结点的指针指向父结点的指针最后变量_col枚举类型可以存RED和BLACK。
enum Color
{RED,BLACK
};templateclass T
struct RBTreeNode
{RBTreeNodeT(const T t): _data(t), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}T _data;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Color _col;
};红黑树主体需要实现的成员函数
// T: 可能是键值对key,value
// 可能是一个key
// 不论节点中存储的是key, value || key, 都是按照key来进行比较的
// KeyOfValue: 提取data中的Key
templateclass K, class T, class KeyOfValue
class RBTree
{typedef RBTreeNodeT Node;
public:typedef RBTreeIteratorT, T, T* iterator;typedef RBTreeIteratorT, const T, const T* const_iterator;
public:RBTree() default;RBTree(const RBTreeK, T, KeyOfValue t);// 插入值为data的节点// 返回值含义iterator代表新插入节点 bool代表释放插入成功std::pairiterator, bool Insert(const T data);// Begin和End迭代器iterator Begin();iterator End();// 红黑树是否为空是返回true否则返回falsebool Empty()const;// 返回红黑树中有效节点的个数size_t Size()const;// 将红黑树中的有效节点删除void Clear();// 检测红黑树是否为有效的红黑树注意其内部主要依靠_IsValidRBTRee函数检测bool IsValidRBTRee()// 在红黑树中查找data存在赶回该节点对应的迭代器否则返回End()iterator Find(const T data);~RBTree();
private:Node* _root;
};红黑树的插入
红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步
首先是按照二叉搜索树的方式插入结点检测插入结点后红黑树的性质是否遭到破坏 因为新结点的默认颜色是红色因此如果父结点的颜色是黑色就没有违反性质不需调整担当插入结点的父节点也是红色时就违反了性质3不能有连在一起的红结点此时需要对红黑树分情况讨论调整 约定cur为当前结点p为父节点g为祖父结点u为叔叔结点。 情况一cur为红p为红g为黑u存在且为红 解决方式将pu变成黑色g变成红色然后把g改成cur继续向上调整。
情况二cur为红p为红g为黑u不存在/u存在且为黑这里需要做的其实就和AVL树中的单旋很像了我们需要把u结点旋转下来以维持平衡 p为g的左孩子cur为p的左孩子进行右单旋相反p为g的右孩子cur为p的右孩子则进行左单旋。p变黑色g变红色。 情况三情况二的变体cur为红p为红g为黑u不存在/u存在且为黑其实就是双旋除了不用调整平衡因子其他的和AVL树的双旋并无差别 p为g的左孩子cur为p的右孩子则针对p做左单旋转相反p为g的右孩子cur为p的左孩子则针对p做右单旋转。然后就转换成了情况2。 针对每种情况进行相应的处理即可
// 插入值为data的节点
// 返回值含义iterator代表新插入节点 bool代表释放插入成功
std::pairiterator, bool Insert(const T data)
{if (_root nullptr) {_root new Node(data);_root-_col BLACK;return std::make_pair(iterator(_root, _root), true);}KeyOfValue kov;Node* parent nullptr;Node* cur _root;while (cur) {if (kov(cur-_data) kov(data)) {parent cur;cur cur-_right;}else if (kov(cur-_data) kov(data)) {parent cur;cur cur-_left;}else return std::make_pair(iterator(cur, _root), false);}cur new Node(data);Node* InsertNode cur;if (kov(parent-_data) kov(data)) {parent-_right cur;cur-_parent parent;}else {parent-_left cur;cur-_parent parent;}while (parent parent-_col RED cur-_col RED) {Node* grandParent parent-_parent;Node* uncle nullptr;// g// p uif (grandParent-_left parent) {uncle grandParent-_right;if (uncle nullptr || uncle-_col BLACK) {if (parent-_left cur) {RotateR(grandParent);parent-_col BLACK;grandParent-_col RED;}else {RotateL(parent);RotateR(grandParent);cur-_col BLACK;grandParent-_col RED;}break;}else {parent-_col BLACK;grandParent-_col RED;uncle-_col BLACK;cur grandParent;parent grandParent-_parent;}}// g// u pelse {uncle grandParent-_left;if (uncle nullptr || uncle-_col BLACK) {if (parent-_right cur) {RotateL(grandParent);parent-_col BLACK;grandParent-_col RED;}else {RotateR(parent);RotateL(grandParent);cur-_col BLACK;grandParent-_col RED;}break;}else {parent-_col BLACK;grandParent-_col RED;uncle-_col BLACK;cur grandParent;parent grandParent-_parent;}}}_root-_col BLACK;return std::make_pair(iterator(InsertNode, _root), true);
}在红黑树中由于不用调节平衡因子双旋的复杂度大大降低直接使用单旋并在插入过程中调整结点颜色即可。 旋转的具体内容在AVL树中【数据结构进阶】AVL树讲解过这里就不赘述了。
// 左单旋
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;Node* parentParent parent-_parent;if (subRL)subRL-_parent parent;subR-_left parent;subR-_parent parentParent;parent-_right subRL;parent-_parent subR;if (parentParent nullptr) {_root subR;}else {if (parentParent-_left parent) {parentParent-_left subR;}elseparentParent-_right subR;}
}// 右单旋
void RotateR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;Node* parentParent parent-_parent;if (subLR)subLR-_parent parent;subL-_right parent;subL-_parent parentParent;parent-_left subLR;parent-_parent subL;if (parentParent nullptr) {_root subL;}else {if (parentParent-_left parent) {parentParent-_left subL;}elseparentParent-_right subL;}
}find
和二叉搜索树的查找规则相同。
// 在红黑树中查找data存在赶回该节点对应的迭代器否则返回End()
iterator Find(const T data)
{KeyOfValue kov;Node* cur _root;while (cur) {if (kov(cur-_data) kov(data))cur cur-_right;else if (kov(cur-_data) kov(data))cur cur-_left;else return iterator(cur, _root);}return iterator(nullptr, _root);
}Empty和Size
Empty接口函数用来判断树是否为空Size用来计算返回树结点的个数。
// 红黑树是否为空是返回true否则返回false
bool Empty()const
{return _root nullptr;
}
// 返回红黑树中有效节点的个数
size_t Size()const
{return _Size(_root);
}size_t _Size(Node* root)
{return root nullptr ? 0 : _Size(root-_left) _Size(root-_right) 1;
}拷贝构造
RBTree(const RBTreeK, T, KeyOfValue t)
{_root _Copy(t._root);
}Node* _Copy(Node* root)
{if (root nullptr)return nullptr;Node* newRoot new Node(root-_data);newRoot-_left _Copy(root-_left);newRoot-_right _Copy(root-_right);return newRoot;
}析构函数和clear
// 将红黑树中的有效节点删除
void Clear()
{_Destroy(_root);_root nullptr;
}~RBTree()
{_Destroy(_root);_root nullptr;
}void _Destroy(Node* root)
{if (root nullptr)return;_Destroy(root-_left);_Destroy(root-_right);delete root;
}检测是否为合法红黑树
在IsValidRBTRee中首先算出一条路径上的黑结点个数digit_black然后在每条路径递归到空结点时判断黑结点个数是否相等即可验证性质4所有路径上黑结点个数相等递归的过程中判断当前结点和父节点的颜色是否同时为红即可验证性质3没有连续的红结点
// 检测红黑树是否为有效的红黑树注意其内部主要依靠_IsValidRBTRee函数检测
bool IsValidRBTRee()
{if (_root nullptr)return true;Node* cur _root;size_t digit_black 0;while (cur) {if (cur-_col BLACK)digit_black;cur cur-_left;}return _IsValidRBTRee(_root, digit_black, 0);
}bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack)
{if (pRoot nullptr) {if (blackCount pathBlack)return true;else return false;}if (pRoot-_col RED pRoot-_parent-_col RED) {return false;}if (pRoot-_col BLACK) {return _IsValidRBTRee(pRoot-_left, blackCount, pathBlack 1) _IsValidRBTRee(pRoot-_right, blackCount, pathBlack 1);}else {return _IsValidRBTRee(pRoot-_left, blackCount, pathBlack) _IsValidRBTRee(pRoot-_right, blackCount, pathBlack);}
}Begin和End
这两个函数用于获取红黑树的头对象和尾迭代器。
// Begin和End迭代器
iterator Begin()
{return iterator(_LeftMost(), _root);
}
iterator End()
{return iterator(nullptr, _root);
}// 获取红黑树最左侧节点
Node* _LeftMost()
{if (_root nullptr)return nullptr;Node* parent _root;Node* cur parent-_left;while (cur) {parent cur;cur cur-_left;}return parent;
}红黑树的迭代器接口
迭代器的好处是可以方便遍历使数据结构的底层实现变的透明从而降低代码编写的复杂程度。
templateclass T, class Ref, class Ptr
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT, Ref, Ptr Self;RBTreeIterator(Node* pNode,Node* root): _pNode(pNode),_root(root){}// 让迭代器具有类似指针的行为Ref operator*();Ptr operator-();// 然迭代器可以移动前置/后置 Self operator();Self operator(int);// 然迭代器可以移动前置/后置-- Self operator--();Self operator--(int);// 让迭代器可以比较bool operator!(const Self s)const;bool operator(const Self s)const;private:Node* _pNode;Node* _root;
};* 解引用和 - 访问
// 让迭代器具有类似指针的行为
Ref operator*()
{return _pNode-_data;
}
Ptr operator-()
{return (_pNode-_data);
}operator()
二叉树的中序遍历并不难实现但是要实现从任意一个结点按中序遍历跑到下一个结点这就有相当难度了。 具体逻辑为
右子树不为空访问右子树的最左结点。右子树为空代表当前结点所在子树访问完了沿着到根节点的路线孩子是父亲左的那个祖先结点就是下一个要访问的结点。
// 迭代器可以移动前置/后置
Self operator()
{if (_pNode-_right) {_pNode _pNode-_right;while (_pNode-_left) _pNode _pNode-_left;}else {Node* cur _pNode;Node* parent cur-_parent;while (parent cur parent-_right) {cur parent;parent parent-_parent;}_pNode parent;}return *this;
}Self operator(int)
{Node* rem _pNode;if (_pNode-_right) {_pNode _pNode-_right;while (_pNode-_left)_pNode _pNode-_left;}else {Node* cur _pNode;Node* parent cur-_parent;while (parent cur parent-_right) {cur parent;parent parent-_parent;}_pNode parent;}return Self(rem);
}operator- - ()
这时候要判断当前迭代器是否指向尾End()同时判断树是否为空这就要用到传入迭代器对象中的_root了。在找到End()的前一个结点之后按照和operator()相反的逻辑即可实现operator--()。 具体逻辑为
左子树不为空访问左子树的最右结点。左子树为空代表当前结点所在子树访问完了沿着到根结点的路线孩子是父亲右的那个祖先结点就是下一个要访问的结点。
// 迭代器可以移动前置/后置--
Self operator--()
{if (_pNode nullptr) {if (_root nullptr)assert(false);Node* parent _root;Node* cur parent-_right;while (cur) {parent cur;cur cur-_right;}_pNode parent;return *this;}if (_pNode-_left) {_pNode _pNode-_left;while (_pNode-_right)_pNode _pNode-_right;}else {Node* cur _pNode;Node* parent cur-_parent;while (parent cur parent-_left) {cur parent;parent-_parent;}_pNode parent;}return *this;
}Self operator--(int)
{if (_pNode nullptr) {if (_root nullptr)assert(false);Node* parent _root;Node* cur parent-_right;while (cur) {parent cur;cur cur-_right;}_pNode parent;return Self(nullptr);}Node* rem _pNode;if (_pNode-_left) {_pNode _pNode-_left;while (_pNode-_right)_pNode _pNode-_right;}else {Node* cur _pNode;Node* parent cur-_parent;while (parent cur parent-_left) {cur parent;parent-_parent;}_pNode parent;}return Self(rem);
}迭代器比较相等
底层就是用指针作比较。
// 让迭代器可以比较
bool operator!(const Self s)const
{return _pNode ! s._pNode;
}bool operator(const Self s)const
{return _pNode s._pNode;
}结语
红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。 红黑树的底层实现到这里就要结束了本篇的数据结构较为复杂模板的使用也有很多容易出错的点需要多加体会。感谢大家的支持♥
