排序树对比
问题：有了二叉查找树、平衡树（AVL），为啥还需要红黑树？
答：极端情况下，二叉树会退化成链表，时间复杂度从O(logn)退化为O(n)。所以有了平衡二叉树。
平衡二叉树对平衡的要求过于严格——每个节点的左右子树的高度差最多为1。这样导致每次进行插入或删除时都会破坏平衡规则，需要进行左旋和右旋来调整。所以有了红黑树。红黑树的特点如下：
红黑树具有如下特点：
1、具有二叉查找树的特点。
2、根节点是黑色的；
3、每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存数据。
4、任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的。
5、每个节点，从该节点到达其可达的叶子节点是所有路径，都包含相同数目的黑色节点。
正是由于红黑树的这种特点，使得它能够在最坏情况下，也能在 O(logn) 的时间复杂度查找到某个节点。
不过与平衡树不同的是，红黑树在插入、删除等操作时不会像平衡树那样频繁着破坏红黑树的规则，所以不需要频繁的调整，这也是我们为什么大多数情况下使用红黑树的原因。
但是，单单在查找效率方面，平衡树比红黑树快。所以，红黑树是一种不大严格的平衡树，可以说是一个折中发方案。
总之：平衡树是为了解决二叉查找树退化为链表的情况，而红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况。
参考：
------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧！
微信打赏