赞
踩
红黑树,是一种平衡二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是 Red 或 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出2倍,因而是接近平衡的。
AVL树和红黑树:
- AVL树:严格平衡(左右子树高度差不超过1),所以AVL树的查找、插入、删除效率高:O(logN),但插入和删除节点后,要维持树的平衡状态,做的旋转处理还是很多的。
- 红黑树:近似平衡(控制最长路径不超过最短路径的2倍),变了一种方式来控制树的平衡,相较于AVL树,没有那么严格。
红黑树更多是一种折中的选择,它舍弃平衡二叉树的严格平衡,换取节点插入时尽可能少的调整。
因为红黑树的旋转情况少于AVL树,使得红黑树整体性能略优于AVL树,不然map和set底层怎么会用红黑树呢,包括很多语言的库里面都用了红黑树。
如果发明AVL树的人是天才的话,那么发明红黑树的人就是天才中的天才,太妙了。
【核心 & 重要】
每个结点不是红色就是黑色
根节点是黑色的
如果一个节点是红色的,则它的两个孩子结点必须是黑色的(这就约束了红黑树里面没有连续的红色节点)
对于每个结点,从该结点到其所有可到达的叶结点的路径中,均包含相同数目的黑色结点
(即==每条路径都有相同数量的黑色节点==,注意:路径是走到 NIL 空节点)
每个 NIL 叶子结点都是黑色的(此处的叶子结点指的是空结点)
如图,这颗红黑树有11条路径,每条路径都有两个黑节点(不包括NIL)
【思考】
为什么满足以上性质后,就能保证 最长路径中节点个数不会超过最短路径中节点个数的2倍 了呢(不包括NIL)
当某条路径最短时,这条路径必然都是由黑色节点构成。当某条路径长度最长时,这条路径必然是由红色和黑色节点交替构成的(性质3限定了不能出现两个连续的红色节点)。
而性质4又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点,这么来说最长路径上的黑节点的数目和最短路径上的黑节点的数目相等。
最短路径:全是黑节点,最长路径:一黑一红,交替出现,所以最长路径刚好是最短路径的2倍。
对于一棵拥有 n 个内部结点(不包括NIL叶子结点)的红黑树,树的最大高度为 h = 2log2(n + 1)
当红黑树是一颗满二叉树时,高度最小 h = log2(n+1),当红黑树中最长路径刚好是最短路径2倍的时候,红黑树的高度最大 h = 2log2(n+1)
如果数据量是10亿:
查找效率 | 查找次数(约等于) |
---|---|
AVL树:log2n | 30 |
红黑树:2log2n | 60 |
【结论】:
和AVL树类似。
1、定义红黑树的节点结构
// 定义红黑颜色 enum Colour // 枚举类型,枚举值默认从0开始,往后逐个加1(递增) { BLACK, RED }; // 红黑树节点的定义(KV模型) template<class K, class V> struct RBTreeNode { pair<K, V> _kv; // 键值对 Colour _col; // 用来标记节点颜色 RBTreeNode<K, V>* _left; // 三叉链结构 RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; // 构造函数 RBTreeNode(const pair<K, V>& kv) : _kv(kv) , _col(RED) , _left(nullptr) , _right(nullptr) , _parent(nullptr) {} };
2、定义红黑树结构
// 红黑树的定义(KV模型) template<class K, class V> class RBTree { typedef RBTreeNode<K, V> Node; private: Node* _root; public: RBTree() :_root(nullptr) {} // 构造函数 bool Insert(const pair<K, V>& kv); // 插入节点 void RotateLeft(Node* parent); // 左单旋 void RotateRight(Node* parent); // 右单旋 bool IsBalance(); // 检测红黑树是否平衡 void InOrder(); // 中序遍历 // ...... private: void _InOrder(Node* root); // 中序遍历子函数 // ...... };
【思考】:在节点的定义中,为什么要将节点的默认颜色给成红色的?
红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:
思考:插入的新节点是红色好还是黑色好呢?
红色好,如果插入黑色,一定会破坏性质4(每条路径的黑色节点数量相等);如果插入红色,可能会破坏性质3(树中不能出现两个连续的红色节点)
插入一个红色新节点后,检测红黑树的性质是否遭到破坏,分为2种情况:
如果其父节点颜色是黑色,没有违反红黑树任何性质,则不需要调整;
如果其父节点颜色是红色,则违反了性质3(树中不能出现两个连续的红色节点),此时需要对红黑树进行平衡化操作,分为以下几种情况来讨论
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/437750
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。