【数据结构的——红黑树】
目录
- 一、红黑树简介
- 二、红黑树的特性
- 三、2-3-4树与红黑树的等价关系
- 四、红黑树的操作
- 4.1、旋转操作
- 4.2、红黑树的插入
- 4.2.1、情形一
- 4.2.2、情形二
- 4.2.3、情形三
- 4.2.4、情形四
- 4.2.5、情形五
- 4.2.6、情形六
- 4.2.7、对插入进行小结
- 4.3、红黑树的删除
- 4.3.1、情形一
- 4.3.2、情形二
- 4.3.3、情形三
- 4.3.4、情形四
- 五、红黑树与AVL区别总结
- 六、工具
一、红黑树简介
红黑树是一种自平衡的二叉查找树，是一种高效的查找树，可以在 O ( l o g 2 n ) O(log_{2}n) O(log2n)时间内完成查找、增加和删除等操作。
有了二叉搜索树，为什么需要平衡二叉树？
对于二叉搜索树，如果插入的数据是随机的，那么它就是接近平衡的二叉树，平衡二叉树（AVLTree）的操作效率较高，查增删的时间复杂度都是 O ( l o g 2 n ) O(log_{2}n) O(log2n)。但是当插入的数据有序时，二叉搜索树的结点就会只在根结点的一侧，就变成了一个链表，操作效率也因此变低，时间复杂度变为了 O ( n ) O(n) O(n)，平衡二叉树的出现正是为了应对这种极端情况。
那么有了平衡二叉树，为什么还需要红黑树呢？
- 红黑树是具备了某些特性的二叉搜索树，是一种接近平衡的二叉树，说其接近平衡是因为红黑树没有像AVL树中平衡因子的概念，它只是靠着满足红黑结点的5条性质来维持接近平衡的结构，并没有依靠平衡因子来维持绝对平衡。
- 每次对AVL进行插入（删除）时，几乎都需要通过旋转类保持平衡，在频繁进行插入（删除）的场景中，AVL的性能就大打折扣。而红黑树通过牺牲严格的平衡，换取插入（删除）时少量的旋转操作，整体性能优于AVL。
- 在进行插入操作时，红黑树最多旋转两次就能回到平衡；进行删除操作时，最多进行三次旋转就能回到平衡。
- 即使在最坏情况下，也能在 O ( l o g 2 n ) O(log_{2}n)