25丨红黑树（上）：为什么工程中都用红黑树这种二叉树？1
需积分: 0 36 浏览量
2022-08-03
14:38:15
上传
评论
收藏 1.99MB PDF 举报
25 | 红黑树（上）：为什么工程中都用红黑树这种二叉树？
2018-11-16 王争
数据结构与算法之美
进入课程
讲述：修阳
时长 10:00 大小 4.59M
上两节，我们依次讲了树、二叉树、二叉查找树。二叉查找树是最常用的一种二叉树，它支
持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下，时
间复杂度是 O(logn)。
不过，二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于 log n 的情况，
从而导致各个操作的效率下降。极端情况下，二叉树会退化为链表，时间复杂度会退化到
O(n)。我上一节说了，要解决这个复杂度退化的问题，我们需要设计一种平衡二叉查找
树，也就是今天要讲的这种数据结构。
很多书籍里，但凡讲到平衡二叉查找树，就会拿红黑树作为例子。不仅如此，如果你有一定
的开发经验，你会发现，在工程中，很多用到平衡二叉查找树的地方都会用红黑树。你有没
有想过，为什么工程中都喜欢用红黑树，而不是其他平衡二叉查找树呢？
2
下载APP
剩余11页未读，继续阅读
评论0