个人网站需要买服务器吗_组织建设包括哪些内容_沧州网站运营公司_品牌策划方案怎么写

TreeMap继承自AbstractMap，并实现了NavigableMap接口(NavigableMap继承自SortedMap接口)。底层的数据结构是红黑树，按照键的自然排序或者自定义实现的规则排序，实现元素的有序性。

特点

1. 元素是有序的：按照key的自然排序或者是自定义的比较器进行排序(并不是按照插入顺序排序)
2. 键不能重复，值可以重复：key不能重复，value可以重复
3. 键不能为null，值可以为null
4. 红黑树是一种自平衡的二叉树，通过规则维持树的高度近似平衡，保证查询的时间复杂度为O(log n)

红黑树底层原理

• TreeMap是基于红黑树实现的键值对集合
• 树的根节点为黑色
• 树里面的节点不是黑色的就是红色的
• 相邻的两个节点不能都是红色
• 从任意一个节点到其叶子节点的路径上黑色节点数相同
• 红黑树的所有叶子节点都是黑色(叶子节点是Nil节点)

参考博主：

红黑树插入： https://www.cnblogs.com/GNLin0820/p/9120337.html最终还是决定把红黑树的篇章一分为二，插入操作一篇，删除操作一篇，因为合在一起写篇幅实在太长了，写起来都觉得累，何况是阅读并理解的读者。 红黑树删除操作请参考 数据结构 - 红黑树（Red Black Tree）删除详解与实现（Java） 现在网络上最不缺的就是对某个知识点的讲解博文，各种花https://www.cnblogs.com/GNLin0820/p/9120337.html

红黑树删除： https://www.cnblogs.com/GNLin0820/p/9668378.html本篇要讲的就是红黑树的删除操作 红黑树插入操作请参考 数据结构 - 红黑树（Red Black Tree）插入详解与实现（Java） 红黑树的删除是红黑树操作中比较麻烦且比较有意思的一部分。 在此之前，重申一遍红黑树的五个定义： 1. 红黑树的节点不是黑色的就是红色的 2. 红黑树的根节点https://www.cnblogs.com/GNLin0820/p/9668378.html

添加节点

第一种情况

添加的节点(500)和它的父节点(400)也是红色，并且它的叔叔节点(Nil1)是黑色(Nil是不存在的叶子节点)

添加的节点(500)是叔叔节点(Nil1)的远亲(是父节点的右节点)

就以父节点(400)为中心点，左旋。旋转后：

1. 父节点变成黑色，祖父节点变成红色
2. 祖父节点(300)的父节点变成400，祖父节点(300)的左子节点是Nil1，右子节点是Nil2
3. 父节点(400)的左子节点变成了300，右子节点是500
4. 祖父节点(300)有父节点的话，父节点(400)的父节点 变成 祖父节点(300)的父节点

 第二种情况

添加的节点(350)是父节点(400)的左子节点，父节点是红色；它的叔叔节点(Nil1)是黑色

添加的节点(350)是叔叔节点(Nil1)的近亲(父节点的左子节点)

就以父节点(400)为中心，先右旋。旋转后：

1. 父节点(400)变成了插入节点(350)的右节点，400的父节点变成了350，400的左节点变成了Nil4
2. 插入节点(350)的右节点变成了400，它的父节点变成了300

再左旋：以350作为中心点，左旋

第三种情况

添加节点(100)是父节点的左子节点，父节点(200)是红色，它的叔叔节点(Nil4)是黑色

添加的节点(100)是叔叔节点的远亲(挨的远)

则以父节点(200)为中心点，右旋，旋转后：

1. 父节点(200)变成黑色，祖父节点(300)变成红色
2. 300的父节点变成了200，左子节点变成了Nil3，右子节点变成了Nil4
3. 200的右子节点变成了300，左子节点变成了100
4. 如果祖父节点(300)不是根节点，父节点(200)的父节点 变成 祖父节点(300)的父节点

第四种情况

插入节点(250)是父节点的右子节点，父节点为祖父节点(300)的左子节点，父节点(200)是红色

插入节点(250)的叔叔节点(Nil4)是黑色

250与Nil4是近亲(挨的近)

以父节点(200)为中心点，先左旋：

1. 200的父节点变成250，200的左子节点是Nil1，右子节点是Nil2
2. 250的父节点变成300，250的左子节点变成200

再按照第三种情况，以250为中心点右旋

第五种情况

插入节点为红色，它的父节点也为红色，它的叔叔节点也是红色

直接将父节点和叔叔节点变成黑色，祖父节点变成红色

如果祖父节点是根节点，则祖父节点最后要变成黑色

1. 首先确认插入节点位置，定位好插入节点的父节点，祖父节点，叔叔节点

2. 看自己和父节点颜色，都是红色就需要修复树平衡(相邻节点不能都是红色)

3. 确认要修复平衡后，看叔叔节点颜色

   1. 叔叔是红色，直接改变叔叔和父亲的颜色(变成黑色)，再改变祖父节点颜色(变为红色)

   2. 叔叔是黑色，就要左旋或者右旋

      1. 自己是左节点，父亲也是左节点：自己是红色，父节点变成黑色，祖父节点变成红色。以父亲为中心右旋

      2. 自己是左节点，父亲是右节点：以父亲为中心，先右旋再左旋，旋转完之后变换颜色，自己变成黑色，父亲节点和祖父节点变成红色

      3. 自己是右节点，父亲也是右节点：自己是红色，父节点变成黑色，祖父节点变成红色。以父亲为中心左旋

      4. 自己是右节点，父亲是左节点：以父亲为中心，先左旋再右旋，旋转完之后变换颜色，自己变成黑色，父亲节点和祖父节点变成红色

   3. 完成当次平衡后，如果叔叔是红色节点：把祖父节点作为下一次平衡的插入点；如果叔叔是黑色节点：把父亲节点作为下一次平衡的插入点

   4. 直到遍历到根节点或者是当前插入点的父节点是黑色，结束平衡操作

删除节点(部分)

首先要确认删除节点时不存在的情况

第二，四种：不满足条件：相邻的两个节点不能为红色

第一，三，五，六种：不满足条件：从任意节点到叶子节点路径上的黑色节点数要相同

也就是说：

在第一五种情况下：父节点是红色，只有一个子节点且是黑色，这时候必然会有另一个子节点也是黑色

在第二六种情况下：父节点是黑色，只有一个子节点且是黑色，这时候必然会有另一个子节点也是黑色

以下是会发生的删除情况

第一种情况

被删除的节点是黑色，并且只有一个子节点是红色

1. 100这个节点作为修复树的起点(代码中设置为replacement)
2. 100的父节点改为400
3. 200的所有指针都置为空
4. 100作为平衡树的起点去做平衡修复：100的颜色是红色，没有其他操作，直接将100这个节点的颜色变为黑色

第二种情况

要删除的节点p有左右子节点

1. 找到500的后继节点：就是600，被确认为要删除的节点
2. 将600节点里面的key-value复制到500节点
3. p指针变成指向600节点
4. 600节点没有子节点，所以没有replacement作为作为修复平衡树的起点
5. 600节点有父节点：600节点自己作为修复平衡树的起点
6. 600节点是红色，不需要修复平衡，直接将600节点中的指针清空

第三种情况

要删除的节点为450，有左右节点。

1. 确认其后继节点为600，将600节点的key-value复制给450节点，600被确认为要删除的节点
2. 600(p指针指向的节点，以下皆为p指向)没有子节点，则600作为修复树的起点
3. 600节点的颜色为黑色(被删除的节点是黑色，破坏了树的平衡)，修复树
4. 600的兄弟节点只有一个子节点，并且和600是近亲,420和440节点颜色互换
5. 以420为中心左旋
6. 以440为中心右旋
7. 清空p指针指向的节点

第四种情况

方法

构造方法

public class TreeMap<K,V>extends AbstractMap<K,V>implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{//比较器private final Comparator<? super K> comparator;//根节点private transient Entry<K,V> root;//树中节点个数private transient int size = 0;//树的修改次数private transient int modCount = 0;public TreeMap() {comparator = null;}//创建一个TreeMap，自定义比较器public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator;}//创建一个TreeMap，将传入集合中的元素复制到TreeMap中public TreeMap(Map<? extends K, ? extends V> m) {comparator = null;putAll(m);}//创建一个TreeMap，将传入的集合复制到TreeMap中，使用传入集合中的比较器public TreeMap(SortedMap<K, ? extends V> m) {comparator = m.comparator();try {buildFromSorted(m.size(), m.entrySet().iterator(), null, null);} catch (java.io.IOException | ClassNotFoundException cannotHappen) {}}
}

查找当前节点的后继节点

    //查找当前节点的后继节点(比当前节点大的最小节点)static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {if (t == null)return null;//如果t节点的右节点不为空，则查找该右节点的最小左节点else if (t.right != null) {Entry<K,V> p = t.right;while (p.left != null)p = p.left;return p;} //如果t节点的右节点为空，则查找该节点的父节点，若t是父节点的左节点，则返回该父节点else {Entry<K,V> p = t.parent;Entry<K,V> ch = t;//若t是p(父节点)的右节点，则继续向上查找，直到查找到p，其中t是p的左节点，返回pwhile (p != null && ch == p.right) {ch = p;p = p.parent;}return p;}}

删除节点后自平衡

x节点是修复平衡的起点

    //x为删除方法中计算出的后继者节点的子节点或者是后继者节点本身//如果x节点不是根节点且它的颜色是黑色，则需要左旋或者右旋//否则直接将x节点的颜色变为黑色private void fixAfterDeletion(Entry<K,V> x) {//如果x节点不是根节点且它的颜色是黑色while (x != root && colorOf(x) == BLACK) {//如果x节点是左节点if (x == leftOf(parentOf(x))) {Entry<K,V> sib = rightOf(parentOf(x));//同一个父节点，x作为左节点是黑色，sib作为右节点是红色//将sib设置为黑色，父节点设置为红色//以x的父节点为中心点左旋if (colorOf(sib) == RED) {setColor(sib, BLACK);setColor(parentOf(x), RED);rotateLeft(parentOf(x));sib = rightOf(parentOf(x));}//sib的左节点是黑色，sib的右节点也是黑色，设置sib为红色//设置完成后将x的父节点赋值给xif (colorOf(leftOf(sib))  == BLACK &&colorOf(rightOf(sib)) == BLACK) {setColor(sib, RED);x = parentOf(x);} //如果sib的左右节点其中一个是红色else {//如果sib的右节点是黑色，设置sib的左节点为黑色，sib为红色，以sib为中心右旋//将x节点的父节点的右节点赋值给sibif (colorOf(rightOf(sib)) == BLACK) {setColor(leftOf(sib), BLACK);setColor(sib, RED);rotateRight(sib);sib = rightOf(parentOf(x));}//上面if条件执行与否都会执行下面的代码//将sib的颜色设置为x父节点的颜色//将x父节点的颜色设置为黑色//将sib的右节点颜色设置为黑色//以x的父节点为中心左旋setColor(sib, colorOf(parentOf(x)));setColor(parentOf(x), BLACK);setColor(rightOf(sib), BLACK);rotateLeft(parentOf(x));//将x设置为根节点，跳出循环x = root;}} //如果x是右节点，与是左节点的情况是对称的else {Entry<K,V> sib = leftOf(parentOf(x));if (colorOf(sib) == RED) {setColor(sib, BLACK);setColor(parentOf(x), RED);rotateRight(parentOf(x));sib = leftOf(parentOf(x));}if (colorOf(rightOf(sib)) == BLACK &&colorOf(leftOf(sib)) == BLACK) {setColor(sib, RED);x = parentOf(x);} else {if (colorOf(leftOf(sib)) == BLACK) {setColor(rightOf(sib), BLACK);setColor(sib, RED);rotateLeft(sib);sib = leftOf(parentOf(x));}setColor(sib, colorOf(parentOf(x)));setColor(parentOf(x), BLACK);setColor(leftOf(sib), BLACK);rotateRight(parentOf(x));x = root;}}}setColor(x, BLACK);}

添加单个元素

   public V put(K key, V value) {Entry<K,V> t = root;if (t == null) {compare(key, key); // type (and possibly null) checkroot = new Entry<>(key, value, null);size = 1;modCount++;return null;}int cmp;Entry<K,V> parent;Comparator<? super K> cpr = comparator;//比较器不为空，根据比较器规则查找元素，若key已存在，更新key对应的value值if (cpr != null) {do {parent = t;cmp = cpr.compare(key, t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}//比较器为空，则按照自然顺序排序比较，查找key，若key存在，则更新key对应的value值else {if (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")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);}//key不存在，新建一个节点存放键值对，放入红黑树中Entry<K,V> e = new Entry<>(key, value, parent);if (cmp < 0)parent.left = e;elseparent.right = e;//添加完成后，调用函数保证红黑树的自平衡fixAfterInsertion(e);size++;modCount++;return null;}

添加多个元素

    //按照map的比较器添加元素或者是按照默认自然排序规则添加元素public void putAll(Map<? extends K, ? extends V> map) {int mapSize = map.size();if (size==0 && mapSize!=0 && map instanceof SortedMap) {Comparator<?> c = ((SortedMap<?,?>)map).comparator();if (c == comparator || (c != null && c.equals(comparator))) {++modCount;try {buildFromSorted(mapSize, map.entrySet().iterator(),null, null);} catch (java.io.IOException | ClassNotFoundException cannotHappen) {}return;}}super.putAll(map);}

删除单个元素

   private void deleteEntry(Entry<K,V> p) {modCount++;size--;//如果要删除的节点，左右节点都不为空，查找到当前节点的后继节点//将后继节点的键值对数据拷贝到要删除的节点中，并且将后继者节点作为被删除的节点if (p.left != null && p.right != null) {Entry<K,V> s = successor(p);p.key = s.key;p.value = s.value;//将后继者节点赋值给p，后续操作的p其实是此处查找到的后继者节点p = s;} // p has 2 children//指定从replacement开始修复树的平衡//从后继者节点的左节点或者右节点开始Entry<K,V> replacement = (p.left != null ? p.left : p.right);//如果replacement节点不为空，后继者节点的父节点与成为replacement节点的父节点if (replacement != null) {replacement.parent = p.parent;//如果后继者节点的父节点为空，则replacement作为根节点if (p.parent == null)root = replacement;//如果后继者节点是其父节点的左节点，则replacement成为父节点的左节点else if (p == p.parent.left)p.parent.left  = replacement;//如果后继者节点是其父节点的右节点，则replacement成为父节点的右节点elsep.parent.right = replacement;//将后继者节点的指针都清空p.left = p.right = p.parent = null;// 修复树的平衡，从replacement节点开始//如果删除的后继者节点是黑色，调用修复if (p.color == BLACK)fixAfterDeletion(replacement);} //如果后继者节点没有父节点，并且也没有子节点(左右节点)，那么清空根节点else if (p.parent == null) {root = null;} //如果后继者节点没有子节点但是有父节点，那么后继者节点自己作为树平衡的开始节点else { //修复树平衡if (p.color == BLACK)fixAfterDeletion(p);//删除后继者节点(清除后继者节点的指针，以及后继者节点的父节点指向它的指针)if (p.parent != null) {if (p == p.parent.left)p.parent.left = null;else if (p == p.parent.right)p.parent.right = null;p.parent = null;}}}