从0开始回顾数据结构---红黑树
红黑树
1、什么是红黑树
红黑树是一种不严格的平衡二叉树,插入、删除、查找的最坏时间复杂度都为 O(logn),避免了二叉树最坏情况下的O(n)时间复杂度。
红黑树特性如下:
1. 根节点是黑色
2. 每个节点要么是黑色要么是红色
3. 每个红色节点的两个子节点一定都是黑色
4. 每个叶子节点(NIL)都是黑色
5. 任意一个节点的路径到叶子节点所包含的黑色节点的数量是相同的---这个也称之为黑色完美平衡
6. 新插入的节点必须是红色->为什么?如果新插入的节点是黑色,那不管是在插入到那里,一定会破坏黑色完美平衡的,因为任意一个节点的路径到叶子节点的黑色节点的数量肯定不一样了。
2、为什么需