华为等五家公司,南昌关键词优化平台,做app开发,假冒建设银行网站目录 一.红黑树的概念二.插入操作三.与AVL树的比较 一.红黑树的概念
在之前的学习中#xff0c;我们了解了二叉搜索平衡树#xff0c;AVL树通过控制每个结点中的平衡因子的绝对值不超过1#xff0c;实现了一个高性能的树。而相较于AVL的高度平衡#xff0c;红黑树觉得AVL为… 目录 一.红黑树的概念二.插入操作三.与AVL树的比较 一.红黑树的概念
在之前的学习中我们了解了二叉搜索平衡树AVL树通过控制每个结点中的平衡因子的绝对值不超过1实现了一个高性能的树。而相较于AVL的高度平衡红黑树觉得AVL为了平衡也付出了代价插入和删除时进行了多次旋转所以红黑树在控制平衡上面没有这么严格只是要求最长路径不超过最短路径的二倍。那红黑树又是如何控制实现的呢接下来了解一下红黑树的性质 每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的则它的两个孩子结点是黑色的(任何路径上没有连续两个红结点)对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点每个叶子结点都是黑色的(此处的叶子结点指的是空结点也称为NIL结点 二.插入操作
在我们了解红黑树的性质后就需要分析相关代码看他如何实现的。首先我们看红黑树结点的定义: 因为map和set的底层使用红黑树实现了为了之后方便这里红黑树用了两个模板参数。
#include iostreamusing namespace std;enum Colour
{RED, BLACK
};templateclass K,class V
class RBTreeNode
{
public:RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Colour _col;RBTreeNode(const pairK,V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};结点定义中与AVL树差距不大只是多了个用枚举定义的参数用来指定是红结点还是黑结点。接下来讲解重点的插入操作 首先因为红黑树也是二叉搜索树所以要满足二叉搜索树的基本性质再者是我们插入的结点的颜色先置为什么能让后面的调整更方便呢。如果黑色需要在后面依据性质4调整插入红色的话依据性质3调整。明显是4更为复杂所以我们插入颜色为红色。
bool Insert(const pairK, V kv)
{if(_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* cur _root;Node* parent nullptr;while (cur){if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);cur-_col RED;if (parent-_kv.first cur-_kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;///开始调整颜色///开始调整颜色_root-_col BLACK;return true;
}上段代码是不涉及调整颜色只保证二叉搜索树性质。下面开始分类讨论研究如何调整颜色。
如上图所示插入的cur结点是红色这时出现了连续的两个红结点所以就要进行调整。如果parent结点是黑色则不需要调整。我们把10结点和20结点称为parent和grandfather结点22为uncle结点。 1.当uncle结点为红色时变色然后继续向上调整 2.当uncle结点不存在时或者为黑时的处理方式相同 完整代码如下: bool Insert(const pairK, V kv){if(_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* cur _root;Node* parent nullptr;while (cur){if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);cur-_col RED;if (parent-_kv.first cur-_kv.first){parent-_left cur;}else{parent-_right 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){RevoR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RevoL(parent);RevoR(grandfather);cur-_col BLACK;grandfather-_col RED;}}}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-_left){RevoR(parent);RevoL(grandfather);cur-_col BLACK;grandfather-_col RED;}else{RevoL(grandfather);parent-_col BLACK;grandfather-_col RED;}}}}_root-_col BLACK;return true;}void RevoL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;parent-_right curleft;//无论curleft是否为空都要执行这一步if (curleft){curleft-_parent parent;}cur-_left parent;Node* ppnode parent-_parent;parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}}void RevoR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;parent-_left curright;if (curright){curright-_parent parent;}cur-_right parent;Node* ppnode parent-_parent;parent-_parent cur;if (_root parent)//等价于 ppnode nullptr{_root cur;cur-_parent nullptr;}else{cur-_parent ppnode;if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}}}三.与AVL树的比较
红黑树和AVL树的插入效率O(logN)只是红黑树不像AVL追求如此平衡所以旋转次数会少并且实现也较简单。所以在实践中大都使用红黑树。之后我们还是使用红黑树模拟实现map和set。
