Java红黑树
概述
- 红黑树是一种自平衡的二叉查找树,是计算机科学中用到的一种数据结构。
- 1972年出现的,当时被称之为平衡二叉B树。在1978年被修改为红黑树。
- 红黑树是一种特殊的二叉查找树,红黑树上的每一个节点都有存储位表示节点的颜色。
- 每一个节点可以是红或者黑。
- 红黑树不是高度平衡的,它的平衡是通过“红黑规则”进行实现的。
平衡二叉树VS红黑树
- 平衡二叉树
- 高度平衡
- 当左右子树高度差超过1,通过旋转保持平衡
- 红黑树
- 是一个二叉查找树
- 不是高度平衡的
- 通过特有的“红黑规则”保持平衡
红黑树的红黑规则
- 一个节点要么红色、要么是黑色的
- 根节点必须是黑色的
- 如果一个节点没有子节点或者父节点,则该节点相应的指针属性值为 Nil ,这些 Nil 被视作叶节点,每一个叶节点(Nil)是黑色的
- 如果某个节点是红色的,那么它的子节点必须是黑色的(不能出现两个红色节点相连的情况)
- 对每个节点,从该节点到其所有的后代叶节点的简单路径上【就是从该节点到叶节点的每一条路径上】,均包含相同数目的黑色节点
如图:
红黑树添加节点的规则
- 默认颜色:添加节点默认是红色的(效率高)
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggfkfb
系列文章
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13