【数据结构的——红黑树】

一、红黑树简介

红黑树是一种自平衡的二叉查找树，是一种高效的查找树，可以在$O(lo{g}_{2}n)$时间内完成查找、增加和删除等操作。

有了二叉搜索树，为什么需要平衡二叉树？

对于二叉搜索树，如果插入的数据是随机的，那么它就是接近平衡的二叉树，平衡二叉树（AVLTree）的操作效率较高，查增删的时间复杂度都是$O(lo{g}_{2}n)$。但是当插入的数据有序时，二叉搜索树的结点就会只在根结点的一侧，就变成了一个链表，操作效率也因此变低，时间复杂度变为了$O(n)$，平衡二叉树的出现正是为了应对这种极端情况。

那么有了平衡二叉树，为什么还需要红黑树呢？

• 红黑树是具备了某些特性的二叉搜索树，是一种接近平衡的二叉树，说其接近平衡是因为红黑树没有像AVL树中平衡因子的概念，它只是靠着满足红黑结点的5条性质来维持接近平衡的结构，并没有依靠平衡因子来维持绝对平衡。
• 每次对AVL进行插入（删除）时，几乎都需要通过旋转类保持平衡，在频繁进行插入（删除）的场景中，AVL的性能就大打折扣。而红黑树通过牺牲严格的平衡，换取插入（删除）时少量的旋转操作，整体性能优于AVL。
• 在进行插入操作时，红黑树最多旋转两次就能回到平衡；进行删除操作时，最多进行三次旋转就能回到平衡。
• 即使在最坏情况下，也能在 O ( l o g 2 n ) O(log_{2}n)