为什么大家都这么推崇红黑树呢? 这就是数据结构的魅力!!! 下面我简述一下常用数据结构的优缺点
数组
大家对数组很熟悉, 都知道对数组来说,它底层的存储空间是连续的,因此如果我们根据index去获取元素,速度是相当快, 但是对于数组来说有时候查询也不见得就一定块, 比如我们查询数组中名字叫张三的人, 也不得不从开始遍历这个数组
如果我们想往数组中插入一个元素, 也不见得一定就慢, 比如我们往数组中最后的位置插入就很快, 但是要是往开始的位置插入的话, 肯定会很慢, 需要将现有数组中所有的元素往后移动一位, 才能空出开始的位置,给新元素用
链表
一说链式存储, 大家也都知道, 这种数据结构仅仅是逻辑连续, 物理存储不连续, 因此我们有可以通过玩指针或者引用很快的完成元素的删除和添加
对链表的查询来说, 一定是慢的, 无论查询谁, 查哪个, 都得从第一个节点开始遍历
AVL树
AVL树, 就是二叉平衡树, 这种有序的树形结果就将链式存储添加删除块, 顺序存储的查找快两大有点进行了一次中和, 在绝大部分情况下, AVL树在增删改查方面的性能都原超过数组和链表
红黑树
红黑树是对AVL树是又一次重大升级, AVL树,对于树的平衡要求太严格了, 每当添加,删除节点时,都不得不进行调整
对于AVL树个红黑树来说, 每次添加一个新的节点都是最多进行两次旋转(左旋右旋)就能重新使树变的平衡,
但是当我们删除一个叶子节点时, AVL树重新调整成平衡状态时最多需要进行旋转O(logN)次, 而红黑树最多旋转3次就能重新平衡,时间复杂度是O(1)
还有就是红黑树并不是完全意义上的AVL树, 也就是说它其实并不是真的像AVL树那样严格要求对一个节点来说左右子树的高度差不能超过1, 而是选择使用染成红色和黑色进行维护
简单来说, 因为红黑树并不像AVL树那样完全平衡, 可能会导致红黑树的读性能略逊于AVL, 但是红黑树的维护成本绝对是远远低于AVL, 在空间上的开销和AVL树基本持平, 因此红黑树被大家极力推崇, 和学习java的同学直接相关的就是jdk8的 hashmap
红黑树的特性红黑树主要存在下面的7条性质
节点非红即黑
根节点必定是黑色
叶子节点全部是黑色, (这里说的叶子节点是我们想象在肉眼看到的节点上再多加一层子节点)
红节点的子节点必定是黑色
红节点的父节点必定是黑色
从根节点到任意子节点的路径上,都要经历相同数目的黑节点
从根节点到任意子节点的路径上不可能存在两个连续相同的红节点
常见的误区如上图, 看着挺像红黑树, 其实他不是, 看它node10, 并不满足上面的性质6. 因为我们认为node10的左子节点是黑色的节点, 这样的话, 从node20到node10的左子节点就经历了两个黑节点, 而其他的 node15, node25, node35 经历的黑色子节点数都是三个
如上图它也不是红黑树, 因为我们认为node30的右节点是黑色的节点, 这样的话从node60到node30的右节点就经历了三个黑色的节点, 而其他的所有子节点都经历了4个, 故, 他不是红黑树
红黑树与2-3-4树等价如上图中,当我们将一个红黑树中的黑色节点和红色节点融合在一起时,我们会发现, 这个红黑树其实就是一颗2-3-4树, 一颗四阶B树
并且, 红黑树中黑色节点的每一个合并完成后的节点中都有一个黑色的节点, 换句话说就是红黑树中黑色节点的个数等于2-3-4树中节点的个数
添加添加节点其实就是构造红黑树的过程, 只要我们严格遵循上面的7条限制, 构造出来的树就是红黑树
通过上图其实我们发现, 红黑树真的可以和四阶B树之间进行等价代换, 换句话说就是 4阶B树的性质对于红黑树来书其实也是存在的, 主要是如下两条性质
所有新添加进去的节点都被放在了叶子节点上
2-3-4树中每一个节点中允许承载的元素的个数 [1,3]
经验推荐: 就是新添加的节点尽量全部是红色, 如果你画一画就会发现, 如果我们新添加的节点是红色的话,上面所说的7条性质中, 除了第四条(红节点的子节点必定的黑节点). 其他的限制都可以满足
于是看一下一颗四阶B树插入节点时有哪些种情况