国内有做网游评测的网站么小说引流推广

TreeMap:基于红黑树实现的，

红黑树的定义:
（1）根节点是黑色。
（2）每个叶节点（NIL节点，空节点）是黑色的。
（3）节点是红色或黑色。
（4）如果一个节点是红色，那么他的两个子节点都是黑色
（5）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。


成员属性：

//比较器，private final Comparator<? super K> comparator;//红黑树的根节点private transient Entry<K,V> root;//元素数量private transient int size = 0;//结构修改记录private transient int modCount = 0;// Red-black mechanicsprivate static final boolean RED   = false;private static final boolean BLACK = true;

 

构造方法：

 

  //无参构造，comparator=null,默认按照自然顺序排序public TreeMap() {comparator = null;}//设置自定义比较器的构造函数public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator;}//指定Map的构造public TreeMap(Map<? extends K, ? extends V> m) {comparator = null;putAll(m);}//指定SortedMap的构造public TreeMap(SortedMap<K, ? extends V> m) {comparator = m.comparator();try {buildFromSorted(m.size(), m.entrySet().iterator(), null, null);} catch (java.io.IOException cannotHappen) {} catch (ClassNotFoundException cannotHappen) {}}

 

元素添加：

 //添加元素public V put(K key, V value) {//记录根节点Entry<K,V> t = root;//如果根节点为空，该元素设置为rootif (t == null) {compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);size = 1;modCount++;return null;}int cmp;Entry<K,V> parent;// split comparator and comparable pathsComparator<? super K> cpr = comparator;//比较器不为空if (cpr != null) {//循环比较并确定元素插入的位置(找父亲节点)do {//记录根节点parent = t;//将当前节点和根节点元素比较cmp = cpr.compare(key, t.key);//待插入key小于当前元素key，查找左边if (cmp < 0)t = t.left;//待插入key大于当前元素key，查找右边else if (cmp > 0)t = t.right;//相等，替换elsereturn t.setValue(value);} while (t != null);}//比较器为nullelse {//TreeMap元素，key不能为nullif (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")//key需要实现Comparable接口Comparable<? super K> k = (Comparable<? super K>) key;//循环比较并确定元素插入的位置do {parent = t;cmp = k.compareTo(t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}//找到父亲节点，根据父亲节点创建一个新节点Entry<K,V> e = new Entry<>(key, value, parent);//如果待插入元素的key值小于父节点的key值，父节点左边插入if (cmp < 0) {parent.left = e;}//如果待插入元素的key值大于父节点的key值，父节点右边插入else {parent.right = e;}//对红黑树进行重新平衡
        fixAfterInsertion(e);size++;modCount++;return null;}

 

元素插入后红黑树需要重新平衡：

 

/** From CLR *///插入后的重新平衡private void fixAfterInsertion(Entry<K,V> x) {//将x节点设置为红色x.color = RED;//循环，x节点不为null，不是根节点，父节点的颜色是红色while (x != null && x != root && x.parent.color == RED) {//如果x节点的父亲是x节点的祖父的左孩子if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {//获取x节点的祖父的右孩子(这里取一个别名，叔叔节点)Entry<K,V> y = rightOf(parentOf(parentOf(x)));//如果叔叔节点为红色if (colorOf(y) == RED) {//将x的父亲设置为黑节点
                    setColor(parentOf(x), BLACK);//叔叔也设置为黑节点
                    setColor(y, BLACK);//祖父节点设置为红色
                    setColor(parentOf(parentOf(x)), RED);//x指向祖父节点x = parentOf(parentOf(x));//叔叔节点是黑色} else {//如果x节点是父节点的右孩子if (x == rightOf(parentOf(x))) {//x移动到父节点x = parentOf(x);//左旋x
                        rotateLeft(x);}//x节点的父节点设置为黑色
                    setColor(parentOf(x), BLACK);//祖父节点设置为红色
                    setColor(parentOf(parentOf(x)), RED);//右旋祖父节点
                    rotateRight(parentOf(parentOf(x)));}} else {//获取祖父节点的左孩子()Entry<K,V> y = leftOf(parentOf(parentOf(x)));//如果祖父节点的左孩子颜色为红色if (colorOf(y) == RED) {//将x节点的父节点设置为黑色
                    setColor(parentOf(x), BLACK);//设置祖父节点的左孩子颜色为黑色
                    setColor(y, BLACK);//将祖父节点设置为红色
                    setColor(parentOf(parentOf(x)), RED);//x移动到祖父节点x = parentOf(parentOf(x));//如果祖父节点的左孩子颜色为黑色} else {//如果x为父节点的左孩子if (x == leftOf(parentOf(x))) {//将x移动到父节点x = parentOf(x);//右旋x
                        rotateRight(x);}//将父节点设置为黑色
                    setColor(parentOf(x), BLACK);//祖父节点设置为红色
                    setColor(parentOf(parentOf(x)), RED);//左旋祖父节点
                    rotateLeft(parentOf(parentOf(x)));}}}//根节点设置为黑色root.color = BLACK;}

 

节点左旋和右旋：

 

/** From CLR *///左旋指定节点private void rotateLeft(Entry<K,V> p) {if (p != null) {//获取p节点的右孩子Entry<K,V> r = p.right;//r的左孩子设置为p的右孩子p.right = r.left;//如果r的左孩子不为nullif (r.left != null)//将p设置为r的左孩子的父亲r.left.parent = p;//p的父亲设置为r的父亲r.parent = p.parent;//p的父亲为nullif (p.parent == null)//r设置为root节点root = r;//如果p是它父亲的左孩子，else if (p.parent.left == p)//将r设置为p父亲的左孩子p.parent.left = r;//如果p是它父亲的右孩子else//将r设置为p父亲的右孩子p.parent.right = r;//将p设置为r的左孩子r.left = p;//将r设置为p的父亲p.parent = r;}}/** From CLR *///右旋指定节点private void rotateRight(Entry<K,V> p) {if (p != null) {//获取p节点的左孩子Entry<K,V> l = p.left;//将l的右孩子设置为p的左孩子p.left = l.right;//如果l的右孩子不为nullif (l.right != null){//将p设置为l的右孩子的父亲l.right.parent = p;}//将p的父亲设置为l的父亲l.parent = p.parent;//如果p的父亲为nullif (p.parent == null)//将l设置为root节点root = l;//如果p是p的父亲的右孩子，else if (p.parent.right == p)//将l设置为p的父亲的右孩子p.parent.right = l;//如果p是p的父亲的左孩子，else {//將l设置为p的父亲的左孩子p.parent.left = l;}//将p设置为l的右孩子l.right = p;//将l设置为p的父亲节点p.parent = l;}}

 

获取元素：

 

 //获取指定key的valuepublic V get(Object key) {Entry<K,V> p = getEntry(key);return (p==null ? null : p.value);}//根据指定的key删除节点final Entry<K,V> getEntry(Object key) {// Offload comparator-based version for sake of performanceif (comparator != null)//有比较器return getEntryUsingComparator(key);if (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;//没有比较器，key需要实现Comparable接口//获取root节点Entry<K,V> p = root;//循环找kwhile (p != null) {//从p节点开始比较，int cmp = k.compareTo(p.key);//如果当前节点的key，比p节点的key小，移动到左孩子if (cmp < 0)p = p.left;//如果当前节点的key，比p节点的key大，移动到右孩子else if (cmp > 0)p = p.right;else//如果相等，返回p。return p;}//找不到，返回nullreturn null;}final Entry<K,V> getEntryUsingComparator(Object key) {@SuppressWarnings("unchecked")K k = (K) key;//获取比较器Comparator<? super K> cpr = comparator;//比较器不为nullif (cpr != null) {//获取root节点Entry<K,V> p = root;//循环找kwhile (p != null) {//从p节点开始比较，int cmp = cpr.compare(k, p.key);//如果当前节点的key，比p节点的key小，移动到左孩子if (cmp < 0)p = p.left;//如果当前节点的key，比p节点的key大，移动到右孩子else if (cmp > 0)p = p.right;//如果相等else//返回preturn p;}}//没有找到，返回nullreturn null;}

 

删除元素：

 

 //根据指定的key删除节点，返回该节点的值public V remove(Object key) {//根据key查找到对应的节点Entry<K,V> p = getEntry(key);if (p == null)return null;//获取该节点的值，作为返回值V oldValue = p.value;//删除节点
        deleteEntry(p);return oldValue;}//删除指定节点private void deleteEntry(Entry<K,V> p) {modCount++;size--;// If strictly internal, copy successor's element to p and then make p// point to successor.//如果p有两个孩子if (p.left != null && p.right != null) {//获取p的继承节点Entry<K,V> s = successor(p);//将s的key设置为p的keyp.key = s.key;//将s的value设置为p的valuep.value = s.value;//将s设置为pp = s;} // p has 2 children// Start fixup at replacement node, if it exists.//开始修复被移除节点的树结构//如果p有左孩子，获取左孩子，没有就获取右孩子Entry<K,V> replacement = (p.left != null ? p.left : p.right);//
        if (replacement != null) {// Link replacement to parentreplacement.parent = p.parent;//如果p没有父亲，p就是root节点if (p.parent == null)//将replacement设置为root节点root = replacement;//如果p是父节点的左孩子else if (p == p.parent.left)//将replacement设置为p的父亲的左孩子p.parent.left  = replacement;else//否则，将replacement设置为p的父亲的右孩子p.parent.right = replacement;//解除p节点的父亲和p节点的左右孩子的引用// Null out links so they are OK to use by fixAfterDeletion.p.left = p.right = p.parent = null;// Fix replacement//如果p为黑色if (p.color == BLACK)//颜色修复
                fixAfterDeletion(replacement);//p的父亲为null，说明p只有自己一个节点} else if (p.parent == null) { // return if we are the only node.//
            root = null;} else { //  No children. Use self as phantom replacement and unlink.//如果p是黑色if (p.color == BLACK)//调整
                fixAfterDeletion(p);//上面判断过if (p.parent != null) {//p是父亲的左孩子if (p == p.parent.left)//删除引用p.parent.left = null;//p是父亲的右孩子else if (p == p.parent.right)//删除引用p.parent.right = null;//删除p对父亲的引用p.parent = null;}}}/** From CLR *///删除后的颜色修复private void fixAfterDeletion(Entry<K,V> x) {//循环，只要x不是root节点并且x的颜色是黑色的while (x != root && colorOf(x) == BLACK) {//如果x是它父亲的左孩子if (x == leftOf(parentOf(x))) {//获取到x节点父亲的右孩子Entry<K,V> sib = rightOf(parentOf(x));//如果sib(父亲右孩子)是红色if (colorOf(sib) == RED) {//设置sib为黑色
                    setColor(sib, BLACK);//设置x父节点为红色
                    setColor(parentOf(x), RED);//x父节点左旋
                    rotateLeft(parentOf(x));//将x父亲的右节点设置为sib，即sib移动到旋转后的x父亲的右孩子sib = rightOf(parentOf(x));}//如果sib的左右孩子都是黑色if (colorOf(leftOf(sib))  == BLACK &&colorOf(rightOf(sib)) == BLACK) {//将sib设置为红色
                    setColor(sib, RED);//将x的父亲设置为x，即x移动到父亲节点x = parentOf(x);//如果不是} else {//如果sib的右孩子是黑色if (colorOf(rightOf(sib)) == BLACK) {//将sib的左孩子设置为黑色
                        setColor(leftOf(sib), BLACK);//将sib设置为红色
                        setColor(sib, RED);//右旋sib
                        rotateRight(sib);//将x的父亲的右孩子设置为sib，即sib移动到旋转后的x父亲的右孩子sib = rightOf(parentOf(x));}//将sib设置成和x的父亲一样的颜色
                    setColor(sib, colorOf(parentOf(x)));//将x的父亲设置为黑色
                    setColor(parentOf(x), BLACK);//将sib的右孩子设置为黑色
                    setColor(rightOf(sib), BLACK);//左旋x的父亲
                    rotateLeft(parentOf(x));//将root设置为x，跳出循环x = root;}//x是一个右孩子} else { // symmetric//获取x父亲的左孩子Entry<K,V> sib = leftOf(parentOf(x));//如果sib为红色if (colorOf(sib) == RED) {//将sib设置为黑色
                    setColor(sib, BLACK);//将x的父亲设置为红色
                    setColor(parentOf(x), RED);//右旋x的父亲
                    rotateRight(parentOf(x));//将x的父亲的左孩子设置为sib，即sib移动到旋转后的x父亲的左孩子sib = leftOf(parentOf(x));}//如果sib的左右孩子都是黑色if (colorOf(rightOf(sib)) == BLACK &&colorOf(leftOf(sib)) == BLACK) {//将sib设置为红色
                    setColor(sib, RED);//将x的父亲设置为x，即x移动到父亲节点x = parentOf(x);//如果不是} else {//如果sib的左孩子是黑色if (colorOf(leftOf(sib)) == BLACK) {//将sib的右孩子设置成黑色
                        setColor(rightOf(sib), BLACK);//将sib设置成红色
                        setColor(sib, RED);//左旋sib
                        rotateLeft(sib);//将x的父亲的左孩子设置为sib，即sib移动到旋转后的x父亲的左孩子sib = leftOf(parentOf(x));}//将sib设置成和x的父亲一样的颜色
                    setColor(sib, colorOf(parentOf(x)));//将x的父亲设置为黑色
                    setColor(parentOf(x), BLACK);//将sib的左孩子设置为黑色
                    setColor(leftOf(sib), BLACK);//右旋x的父亲
                    rotateRight(parentOf(x));//将root设置为x，跳出循环x = root;}}}//将x设置为黑色
        setColor(x, BLACK);}