深入理解高级数据结构之红黑树
需积分: 9 173 浏览量
2022-09-11
18:04:56
上传
评论
收藏 1.71MB PDF 举报
目录
一、为什么要有红黑树？
二、什么是“平衡二叉查找树”？
三、红黑树的定义
四、为什么说红黑树是“近似平衡”的？
五、红黑树为什么综合性能好？
六、实现红黑树
1、插入操作的平衡调整
2、删除操作的平衡调整
1. 针对删除节点初步调整
2. 针对关注节点进行二次调整
3、小结
六、红黑树的应用场景
红黑树已经落地的场景
一、为什么要有红黑树？
二叉查找树是最常用的一种二叉树，它支持快速插入、删除、查找操作，各个操作的时间复杂度
跟树的高度成正比，理想情况下，时间复杂度是 O(logn)。
但是，在已经有了性能不错的二叉搜索树，为什么还需要引入红黑树呢？
那是因为，二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于 log2n 的情况，从
而导致各个操作的效率下降。极端情况下，二叉树会退化为链表，时间复杂度会退化到 O(n)。
而且，我们希望树的结构具有关联性，即相邻版本之间，比如说第一次插入，和第二次插入时，
树的结构不能发生太大变化，应该可以经过O（1）次数就可以变化完成。对于AVL树来说，插入是
满足这个条件的，删除却不满足这个条件。
要解决这两个问题，我们需要设计一种平衡二叉查找树，也就是今天要讲的红黑树。
二、什么是“平衡二叉查找树”？
平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。从
这个定义来看，上一节我们讲的完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树
也有可能是平衡二叉树。
剩余10页未读，继续阅读
资源评论
