无知的小狼

在看jdk的HashMap的代码的时候，看到了jdk8的实现方式用到了红黑树，然后，就看了一下。 废话少讲，开始红黑树的简介。 红黑树的特性 1.每个节点或者是黑色，或者是红色。 2.根节点是黑色。 3.每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！ 4.如果一个节点是红色的，则它的子节点必须是黑色的。 5.从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。 红黑树的添加： 第一步: 将红黑树当作一颗二叉查找树，将节点插入。 第二步：将插入的节点着色为”红色”。 第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。 伪代码： 123456789101112131415161718RB-INSERT(T, z) 01 y ← nil[T] // 新建节点“y”，将y设为空节点。02 x ← root[T] // 设“红黑树T”的根节点为“x”03 while x ≠ nil[T] // 找出要插入的节点“z”...

无知狼的博客！