国安中建建设集团网站,坛墨网站建设,镇江市网站开发公司,怎样建立自己的网站平台文章目录红黑树代码红黑树性质红黑树vsAVL树红黑树的实现Insert()情况一#xff1a;如果我插入的新节点时红色的情况二#xff1a;叔叔是黑色或者不存在情况三: cur红,p为红,g为黑,u不存在或者为黑-双旋检查erase()红黑树vsAVL树红黑树的应用#xff1a;红黑树
二叉搜索树 …
文章目录红黑树代码红黑树性质红黑树vsAVL树红黑树的实现Insert()情况一如果我插入的新节点时红色的情况二叔叔是黑色或者不存在情况三: cur红,p为红,g为黑,u不存在或者为黑-双旋检查erase()红黑树vsAVL树红黑树的应用红黑树
二叉搜索树
代码
红黑树性质 每个节点不是黑色就是红色.根节点是黑色红色节点的孩子节点都是黑色的所以不存在连续的红色.对于节点从该节点到所有后代叶子节点的简单路径上包含相同数目的黑色节点。这里的路径不是到叶子结点中止而是到NULL。 节点个数,最长路径不超过最短路径的2倍。最短路径是全黑最长路径就是一黑一红。假设每条路径黑节点的数量是N,N任意路径长度2N每个叶子节点都是黑色的这时候的叶子结点是NULL不是平常的叶子结点。在数路径的时候看的不是叶子结点而是NULL的个数,来保证每条路径黑色节点的数目是相等的.
红黑树vsAVL树 AVL树是严格平衡树的左右相差不超过2AVL左右两端更加均衡高度更接近logN。红黑树是近似平衡红黑树两边最坏情况是2logN。AVL树效率更高.
内存中搜索是差不多的logN足够小CPU对于这种很小基数的2倍是很快的几乎无差别,假设是10亿个数,AVL树放30层,红黑树可能是60层,查找30次和60次对于CPU很小.但是AVL是旋转了很多次红黑树是不一定旋转的。所以综合来说红黑树更优.
红黑树的实现
Insert() 第一次插入是插入那个节点好? 插入黑节点或者红结点就是在违反规则所以需要考虑那个代价更小所以选择红结点。 如果增加叶子结点是黑节点那么别的路径的黑节点个数怎么平衡?影响太大。 如果插入的是红色,可能父亲是黑色,就没问题;如果父亲是红色就不行,这两种存在概率问题,有空可钻.
情况一如果我插入的新节点时红色的
父节点是红的祖父一定是黑的,没有连续的红结点所以看叔叔节点如果是红结点那么只需要将parent和uncle节点都改为黑色祖父g变成红色因为祖父不一定是根节点所以我要保证所有路径黑节点个数相同
如果g-parent是红色的就需要curg,将祖父当成新增,继续向上调整。如果g-parent是黑色就可以结束了。所以就存在cur可能不是新增节点了,是某一个新增节点的祖父.
所以cur可能是新增也有可能是新增的祖父节点的n次。 情况二叔叔是黑色或者不存在
单纯变色不行了,因为最长路径已经超过了最短路径的2倍,就需要旋转一下.旋转的目的就是保持搜索树降低他的高度,让他左右均衡.所以是旋转加变色先根节点变黑。旋转又分为左右单旋和双旋的情况
右单旋图示(左单旋同理) 情况三: cur红,p为红,g为黑,u不存在或者为黑-双旋
折线,走单旋是没有效果的,只是把左边高变为右边高.所以走双旋. p为g的左孩子cur为p的右孩子则针对p做左单旋转,然后针对g做右单旋 p为g的右孩子cur为p的左孩子则针对p做右单旋转.然后针对g做左单旋 检查
完成之后编译执行正确只能保证这是一棵搜索树对于红黑树还需要进一步检验。
根节点的颜色必须是黑色如果节点是红色直接验证他的父亲是不是红色,验证孩子的可能性太多前序遍历就是深度优先遍历路径中统计黑节点个数就行给定参考值banchmark某一条路径的比如最左路径遍历一条路径,就将这条路径的值blackNum和基准值比较一次,看看每条路径的黑节点个数是否相等.
bool IsBalance(){if (_root _root-_color RED){cout 根节点不是黑色 endl;return false;}int banchmark 0;Node* left _root;while (left){if (left-_color BLACK){banchmark;}left left-_left;}int blackNum 0;return _IsBalance(_root, banchmark, blackNum);}
bool _IsBalance(Node* root, int banchmark, int blackNum){if (root nullptr){if (banchmark ! blackNum){cout 存在路径黑色节点的数量不相等 endl;return false;}return true;}if (root-_color RED root-_parent-_color RED){cout 连续出现红色节点 endl;return false;}if (root-_color BLACK){blackNum;}return _IsBalance(root-_left, banchmark, blackNum) _IsBalance(root-_right, banchmark, blackNum)}erase()
大佬博客
红黑树vsAVL树
红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O(logN)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多.
红黑树的应用 C STL库 – map/set、mutil_map/mutil_setJava 库linux内核其他一些库
