红黑树简介 忘是亡心i 2022-08-26 12:28 4阅读 0赞 一、红黑树(Red-Black Tree)是二叉搜索树(Binary Search Tree)的一种。二叉搜索树在最坏的情况下可能会变成一个链表(当所有节点按从小到大的顺序依次插入后)。这种低效产生的原因是树没有维持一定的平衡性,要提高搜索效率,就要想办法来维持树左边的平衡,也就是要尽时降低树的高度,可行的做法就是用一些策略在每次修改树的内容之后都调整树的结构,使之满足一定的平衡条件。其中一种满足一定平衡条件而且目前应用广泛的是红黑树。它可以在每一次插入或删除节点之后都会花O(log N)的时间来对树的结构作修改,以保持树的平衡。而红黑树的查找方法与二叉搜索树完全一样,也能够在O(log N)时间上完成。而红黑树的插入和删除节点的的方法只是在原二叉搜索树搜索和删除算法之后经过一定的过程来维持红黑树的性质不变。 红黑树的每个节点上的属性除了有一个key、3个指针:parent、left、right以外,还多了一个属性:color。它只能是两种颜色:红或黑,当然也可以再加一些以key来索引的数据。而红黑树除了具有二叉搜索树的所有性质之外,还具有以下5点性质: 1. 每个节点是黑色的或是红色的。 2. 根节点是黑色的。 3. 空节点是黑色的(红黑树中,根节点的parent以及所有叶节点left、right都不指向NULL,而是指向一个定义好的空节点,这样可以保持算法的一致性,简化算法)。 4. 红色节点的父、左子、右子节点都是黑色。 5. 在任何一棵子树中,每一条从根节点向下走到空节点的路径上包含的黑色节点数量都相同。 如下图就是一棵红黑树: ![红黑树的介绍和实现\[原创\] - saturnman - 一路][- saturnman -] 小记: 1. 在一棵红黑树中null节点是很多的,如果每个null节点都用一个真的节点的话那就太浪费空间了,我们可以对所有的null节点都使用同一个节点,这样可以简化算法又能节约空间。 2. 由于红黑树的结构比较复杂,代码的书写一定要常规,比如一般null的left,right和parent都指向树的根节点,但是一般不应该用null节点来索引根节点或是做相应的判断,因为在一些地方我们为了保持算法的一致性,可能改变null节点的left,right,parent的指向。 3. 这里的红黑树实现并不是真的想拿来应用,而是拿来练习,因此在代码的实现上没有过份的考虑效率而影响可读性,因为红黑树结构复杂,里面很多部分的代码并不能随意写出而无错误,直接写出易引入很多细小的bug,因此很多地方要用数学方法来严格证明算法的正确性。 [- saturnman -]: /images/20220824/5494436b911346fb8985c8088dcb01ce.png
相关 树:红黑树 1,红黑树引入 红黑树是对AVL树的补充。AVL树要求整个树的高度差不能超过1,超过后需要进行左旋或者右旋操作再次对树进行平衡,虽然这样能够解决二叉树退化为链表的缺 ╰半橙微兮°/ 2023年02月28日 01:25/ 0 赞/ 174 阅读
相关 红黑树 红黑树的定义 每个节点要么是红色,要么是黑色。 根节点必须是黑色, 每个叶子节点是黑色(叶子节点包含NULL)。 红色节点不能连续(红色节点的孩子和父亲 Dear 丶/ 2022年12月13日 04:18/ 0 赞/ 36 阅读
相关 红黑树简介 一、红黑树(Red-Black Tree)是二叉搜索树(Binary Search Tree)的一种。二叉搜索树在最坏的情况下可能会变成一个链表(当所有节点按从小到大的顺序依次 忘是亡心i/ 2022年08月26日 12:28/ 0 赞/ 5 阅读
相关 红黑树 红黑树(Red Black Tree) 是一种自平衡二叉查找树,红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能,它虽然 谁践踏了优雅/ 2022年06月15日 12:57/ 0 赞/ 519 阅读
相关 红黑树 > 3.3 Balanced Search Trees > [http://algs4.cs.princeton.edu/33balanced/][http_algs4.c ╰+攻爆jí腚メ/ 2022年06月09日 12:48/ 0 赞/ 370 阅读
相关 红黑树 红黑树 概念 红黑树,又被称为对称二叉B树。 [红黑树模型][Link 1] 其本质是一种二叉查找树,单它在二叉查找树的基础上额外添加了一个标记(颜色),同时具 拼搏现实的明天。/ 2022年04月10日 02:39/ 0 赞/ 462 阅读
相关 红黑树简介与C++应用 简介 红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。 它是在1972年由Rudolf 旧城等待,/ 2022年02月09日 11:15/ 0 赞/ 166 阅读
相关 红黑树 先Mark,后续补充: [https://juejin.im/entry/58371f13a22b9d006882902d][https_juejin.im_entry_58 柔情只为你懂/ 2022年01月30日 14:57/ 0 赞/ 364 阅读
相关 红黑树 二叉查找树(BST) 1.左子树上所有结点的值均小于或等于它的根结点的值。 2.右子树上所有结点的值均大于或等于它的根结点的值。 3.左、右子树也分别为二叉排序树。 下 川长思鸟来/ 2021年10月24日 01:48/ 0 赞/ 418 阅读
相关 红黑树 1. 从 2-3 树说起 一棵标准的 BST (二叉查找树 / 二叉搜索树)是长这个样子的: BST 其中,这棵二叉查找树中的每个结点也叫 2-结点 ,2-结点 就表示树... 系统管理员/ 2020年11月29日 04:30/ 0 赞/ 866 阅读
还没有评论,来说两句吧...