有了二叉查找树、平衡树（AVL）为啥还需要红黑树？
2024-09-05 20:08:14
序言
二叉查找树的缺点
平衡二叉树
虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logn)，不过却不是最佳的，因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树。
红黑树
红黑树具有如下特点：
1、具有二叉查找树的特点。
2、根节点是黑色的；
3、每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存数据。
4、任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的。
5、每个节点，从该节点到达其可达的叶子节点是所有路径，都包含相同数目的黑色节点。
正是由于红黑树的这种特点，使得它能够在最坏情况下，也能在 O(logn) 的时间复杂度查找到某个节点。
不过，与平衡树不同的是，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整，这也是我们为什么大多数情况下使用红黑树的原因。
不过，如果你要说，单单在查找方面的效率的话，平衡树比红黑树快。
所以，我们也可以说，红黑树是一种不大严格的平衡树。也可以说是一个折中发方案。
而关于红黑树的应用，一个非常经典的就是JDK1.8的HashMap中，当链表长度超过8时，就会由链表变成红黑树
小结：
平衡树是为了解决二叉查找树退化为链表的情况，而红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况。
资料
最新文章
- Codeigniter的Redis使用
- 【GoLang】golang 中 defer 参数的蹊跷
- 网站标题ico那些事
- HDU 1878 欧拉回路 图论
- 【转】仿百度输入框智能提示的js代码
- css的引入方法2
- 最简单的视音频播放示例6：OpenGL播放YUV420P（通过Texture，使用Shader）
- .NET MVC 插件化框架源码
- JS 实现 startWith endWith函数
- Linux06--Shell程序设计02 数据流重定向与管道
- 【故障】当Eclipse打不开的时候
- LeetCode 191. Number of 1 bits （位1的数量）
- linux进阶指令
- centos7学习笔记-安装配置apache
- debian及ubuntu挂载本地硬盘的ISO镜像文件
- 【原创视频教程】XSL视频教程[共9集]
- struts2 实现rest
- Kafka生产者APi
- JavaScript总结（七）
- SDL视频显示进阶