企业官网建设流程全解析

潍坊网页推广制作,WordPress优化百度广告,做家教去什么网站,宁波网络推广本篇会用到上篇【AVL树的实现】中的旋转知识。一#xff0c;红黑树的概念红黑树是一颗二叉搜索树#xff0c;它的每一个节点增加一个存储为来表示节点的颜色。可以是红色或者黑色。它通过对从根开始到叶子节点的每条路径上各个节点颜色的约束#xff0c;确保最长路径不会超过…本篇会用到上篇【AVL树的实现】中的旋转知识。一红黑树的概念红黑树是一颗二叉搜索树它的每一个节点增加一个存储为来表示节点的颜色。可以是红色或者黑色。它通过对从根开始到叶子节点的每条路径上各个节点颜色的约束确保最长路径不会超过最短路径的2倍从而实现平衡的。1.1红黑树的规则1每个节点不是红色就是黑色。 2根节点是黑色的。 3红色节点的两个孩子只能是 黑色节点或者是空节点。也就是说不能出现连续的红色节点 4对于任意一个节点从该节点开始到叶子节点的所有路径上均包含相同数量的黑色节点。以上 都是红黑树满足红黑树的规则。1.2红黑树的最长路径1由第四条规则可知从根节点开始的每条路径上黑色节点的数量相同。所以在极端场景下一颗红黑树它的最短路径就是节点全为黑色的路径。假设红黑树的每条路径黑色节点数量都为b,那么最短路径的节点数量为b.2由 第三条规则可知一条路径上不能由连续的红色节点最长路径是由一黑一红间隔组成的所以最长路径为2*b。3而对于一颗红黑树最长和最短路径不一定存在。我们可以得出对于任意一颗红黑树它的任意 一条路径长度x都是bx2*b.1.3红黑树的效率分析假设N是红黑树节点的数量h是最短路径的长度,最长路径不超过2*h可以得到2^h-1 N 2^(2*h)-1,推出h大致为logN,也就意味着红黑树的增删查该最坏走2*logN,时间复杂度O(logN).二红黑树的实现2.1红黑树的结构enum color { Red, Black }; templateclass k,class v struct RBTreeNode { RBTreeNode(const pairk,v kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_kv(kv) {} RBTreeNodek, v* _left; RBTreeNodek, v* _right; RBTreeNodek, v* _parent; pairk, v _kv; color _col; }; templateclass k,class v class RBTree { typedef RBTreeNodek, v Node; public: //... private: Node* _rootnullptr; };2.2红黑树的插入2.2.1大致过程1插入一个值需要按照搜索树的规则进行插入再判断插入后是否满足红黑树的规则。2如果是空树插入新增节点就是黑色节点。如果是非空树插入新增节点就必须是红色节点因为如果插入黑色节点就一定会破坏规则4而插入红色节点是有可能会破坏规则3而且对于规则3来说解决方法比规则4的解决方法容易。3非空树插入后如果父节点是黑色节点则没有违反任何规则插入结束。 4非空树插入后如果父节点是红色节点则违反规则3进一步分析。