成都手机网站,新乡seo外包,台州网站关键字优化,重庆网站优化排名推广目录
前言
一#xff0c;概念
定义
二#xff0c;insert
情况一#xff1a;
情况二#xff1a;
情况三#xff1a;
insert代码
三#xff0c; 红黑树验证(面试题)
产生随机数验证 每日一图区#xff1a; 前言 AVL树是一棵绝对平衡的二叉搜索树#xff0c;其…目录
前言
一概念
定义
二insert
情况一
情况二
情况三
insert代码
三 红黑树验证(面试题)
产生随机数验证 每日一图区 前言
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即$log_2 (N)$。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。 因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。 红黑树相对于AVL树的优势包括 插入和删除操作更快红黑树相对于AVL树的平衡条件更加宽松因此在插入和删除节点时需要进行的旋转操作更少。这使得红黑树的插入和删除操作更快。 更好的平衡性能红黑树的平衡性能比AVL树稍差但是在实际应用中红黑树的平衡性能已经足够好了。红黑树的插入和删除操作相对较快这在某些场景下更重要。 更少的旋转操作红黑树的旋转操作比AVL树少。旋转操作是一种比较耗时的操作因此红黑树的插入和删除操作相对更快。 更好的空间效率红黑树相对于AVL树需要更少的额外空间来存储平衡因子或颜色信息。这使得红黑树的空间效率更高。 更广泛的应用红黑树相对于AVL树应用更广泛。红黑树在很多语言的标准库中都有实现而AVL树的应用相对较少。
需要注意的是红黑树和AVL树都是平衡二叉搜索树选择使用哪种树结构取决于具体的应用场景和需求。 一概念 红黑树是一种 二叉搜索树但 在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对 任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是 接近平衡的。 红黑树的性质 1. 每个结点不是红色就是黑色 2. 根节点是黑色的 3. 如果一个节点是红色的则它的两个孩子结点是黑色的 4. 对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 其中NIL表示一个路径的出口。
定义
enum color{RED, BLACK};template class data_type
struct RBT_Data
{data_type _kv;RBT_Datadata_type* left nullptr;RBT_Datadata_type* right nullptr;RBT_Datadata_type* parent nullptr;color _col; // 颜色RBT_Data(const data_type p):_kv(p),_col(RED) // 颜色默认红{}
};template class data_type
class RB_Tree
{typedef RBT_Datadata_type RBT_Data;RBT_Data* root;
};
关于创建新节点该怎么选颜色。
如果我们选择黑色那么我们一定会违反性质四对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点 我们为了保持红黑树的结构就需要调整其他所有的路径。如果我们选择红色我们可能会违法性质三如果一个节点是红色的则它的两个孩子结点是黑色的 而且影响的只是局部不会影响其他的兄弟树。
因此我们会选择红色作为默认颜色。 在AVL树中我们关注树之间的高度而到了红黑树我们需要关注节点之间的颜色。 二insert 插入新节点我们需要检测新节点是否破坏红黑树的性质。
因为 新节点的默认颜色是红色因此如果 其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整 但 当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论 情况一
特点uncle存在且为红parent为红色cur也为红 用一个模板图总结该情况 情况二 特征没有uncle, parent为红, cur为红 所以在情况二下比较重要的就是旋转方法变色旋转如果有忘记了可以参考本篇文章
保姆级认识AVL树【C】精讲AVL Insert-CSDN博客 情况三 特征没有uncle或者uncle是黑色parent为红cur为红。相比较于情况二情况三的旋转方法是双旋。 这里有一个区分情况二与情况三的小技巧那就是看grandfather , parent, cur 三节点的线路。如果是直线则情况二 折线则情况三。 insert代码
bool insert(const pairK, V p){RBT_Data* new_a_d new RBT_Data(p);if (!root){root new_a_d;root-_col BLACK; }else{RBT_Data* cur root;RBT_Data* parent nullptr;while (cur){if (p.first cur-_kv.first){parent cur;cur cur-left;}else if (p.first cur-_kv.first){parent cur;cur cur-right;}else{delete(new_a_d); // 插入失败删除新建结点return false;}}if (p.first parent-_kv.first){parent-left new_a_d;}else{parent-right new_a_d;}new_a_d-parent parent;// 调整颜色cur new_a_d;RBT_Data* par cur-parent;if (cur root){cur-_col BLACK;}while (par par-_col RED){RBT_Data* gf par-parent;RBT_Data* uncle nullptr;if (gf par gf-right){uncle gf-left;}else if (gf par gf-left){uncle gf-right;}else{assert(false);}if ( uncle uncle-_col RED)// 有u且为红{gf-_col RED;uncle-_col BLACK;par-_col BLACK;cur gf; // 切换为祖先进入循环向上par cur-parent;}else if (!uncle ||(uncle uncle-_col BLACK)){ // 情况2 3判断是否是折线还是直线if (gf-left par par-left cur){ // 右单选RotateR(gf);}else if (gf-right par par-right cur){ // 左单旋RotateL(gf);}else if (gf-left par par-right cur){ // 需要左双旋RotateLR(gf);}else if (gf-right par par-left cur){ // 需要右双旋RotateRL(gf);}else{assert(false);}break;}else{assert(false);}}if ( root-_col RED){root-_col BLACK;}return true;}
}
左右和双旋实现代码跟AVL章节中大差不差这里给出左单旋的实现大家照葫芦画瓢一下
void RotateL(RBT_Data* parent){assert(parent-right);RBT_Data* par parent;RBT_Data* par_R par-right;RBT_Data* par_RL par-right-left;RBT_Data* ppnode par-parent;par-right par_RL;if (par_RL)par_RL-parent par;par_R-left par;par-parent par_R;par_R-parent ppnode;if (!ppnode){root par_R;}else if (ppnode-left par){ppnode-left par_R;}else{ppnode-right par_R;}par-_col RED;par_R-_col BLACK;} 三 红黑树验证(面试题)
验证红黑树性质
目标
1. 根是否是黑
2. 没有连续红节点
3. 每条路径所经历的黑节点相同。
代码
public:
bool IsBalance(){if (root root-_col RED){return false;}int BlackNum 0; // 所经黑节点的次数int standard 0; //设置一个最长路径RBT_Data* cur root;while (cur){if (cur-_col BLACK)standard;cur cur-left;}return _IsBalance(root-left, BlackNum, standard) _IsBalance(root-right, BlackNum, standard);}private:
bool _IsBalance(const RBT_Data* cur, int BlackNum, int standard){if (cur nullptr){return true;}if (cur-_col BLACK)BlackNum;if (cur-_col RED cur-_col cur-parent-_col){return false;}return _IsBalance(cur-left, BlackNum, standard) _IsBalance(cur-right, BlackNum, standard);} 产生随机数验证
void Random_Test()
{srand(time(0));const size_t N 10000000;RB_Treeint, int t;for (size_t i 0; i N; i){size_t x rand();t.insert(make_pair(x, x));}cout t.IsBalance() endl;
} 四删除
红黑树的删除本节不做讲解有兴趣的同学可参考《算法导论》或者《STL源码剖析》 http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html 下期预告用红黑树封装map与 set 结语 本小节就到这里了感谢小伙伴的浏览如果有什么建议欢迎在评论区评论如果给小伙伴带来一些收获请留下你的小赞你的点赞和关注将会成为博主创作的动力。
