数据结构与算法学习笔记（十一）——红黑树

红黑树

1、为什么要有红黑树？
二叉查找树在不断的动态更新中，可能会退化成链表，出现树的高度远远大于O(log2n)的情况，所以有一种平衡二叉查找树——红黑树，可以在动态的更新中不断调整节点的位置，使该树一直保持相对平衡，不至于将时间复杂度退化到O(n)。
因此红黑树的性能非常稳定，可以应用于动态插入、删除、查找数据的场景。
2、红黑树是一种近似平衡的二叉查找树，且查找、插入、删除的时间复杂度都在O(logn)
平衡二叉树：其任意一个节点的左右子树的高度相差不能大于1。
合格的平衡二叉树：树的高度不会比log2n大很多，即高度仍是对数级

红黑树的特点

1、节点一类标记为红色，一类标记为黑色
2、根节点都是黑色
3、叶子节点都是黑色，且不存储数据(NIL)
4、任何相邻的节点不能同时为红色，两个红色节点之间一定会被黑色节点所隔开
5、每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点。

红黑树的实现难度有点高，还未理解完全
图源：王争——数据结构与算法之美