集合框架 Map篇(3)—-TreeMap及红黑树、EnumMap

  categories:资料  author:

来源:互联网

Map
——
1.HashMap
2.LinkedHashMap
3.IdentityHashMap
4.WeakHashMap
5.TreeMap
6.EnumMap
7.ConcurrentHashMap
8.ConcurrentSkipListMap
————————————–

——–EnumMap—————————————-

public class EnumMap<K extends Enum<K>,V> extends AbstractMap<K,V> implements Serializable, Cloneable

与枚举类型键一起使用的专用 Map 实现。枚举映射中所有键都必须来自单个枚举类型,该枚举类型在创建映射时显式或隐式地指定。枚举映射在内部表示为数组。此表示形式非常紧凑且高效。

枚举映射根据其键的自然顺序 来维护(该顺序是声明枚举常量的顺序)。在 collection 视图(keySet()、entrySet() 和 values())所返回的迭代器中反映了这一点。

eg.:

import java.util.EnumMap;

enum WeekEnum {
Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday
}

public class EnumMapTest {

private EnumMap<WeekEnum, String> enumMap = new EnumMap<WeekEnum, String>(WeekEnum.class);

public EnumMapTest() {
enumMap.put(WeekEnum.Monday, “星期一,一周开始”);
enumMap.put(WeekEnum.Thursday, “星期二,一周第二天”);
enumMap.put(WeekEnum.Wednesday, “星期三,好好工作……”);
enumMap.put(WeekEnum.Thursday, “星期四,……”);
enumMap.put(WeekEnum.Friday, “星期五,……”);
enumMap.put(WeekEnum.Saturday, “星期六,……”);
enumMap.put(WeekEnum.Sunday, “星期天,休息一下……”);
}

public String getDayDescription(WeekEnum day) {
return this.enumMap.get(day);
}

public static void main(String[] args) {
String dayDesc=new EnumMapTest().enumMap.get(WeekEnum.Sunday);
System.err.println(dayDesc);
}

}

上面是一个简单的例子。由于EnumMap的具有枚举类型的特点,类型固定且枚举值的个数固定,所以EnumMap效率是比较高的,可以结合具体的应用(特别像例子中的那样,元素的个数较少且较固定时考虑使用EnumMap存储数据)

——–TreeMap——————————————

TreeMap是一种支持排序的Map,其实现方式和HashMap有较大区别,是红黑树数据结构的实现。

/**
*TreeMap中节点的存储结构
*/
static final class Entry<K,V> implements Map.Entry<K,V> {
/**6个变量域:键、值对、左、右兄弟、父节点、颜色属性 */
K key;
V value;
Entry<K,V> left = null;//
Entry<K,V> right = null;
Entry<K,V> parent;
boolean color = BLACK;
……
}

put(Object key,Object value):

它是一个典型的基于红黑树的实现,因此要求一定要有key比较的方法,要么传入Comparator实现,要么key对像实现Comparator接口。
/**
*通过“键值对”初始化Entry并把该Entry放到红黑树结构中(如果该key对应的Entry存在,其value就替换为新的value)
*/
public V put(K key, V value) {
//临时变量t指向根节点
Entry<K,V> t = root;
//如果t为空,也就是root为空,TreeMap是空链的情况下,根据键值对创建Entry,并将其置为root根节点
if (t == null) {
root = new Entry<K,V>(key, value, null);//父节点为null
size = 1;//size表示节点的个数
modCount++;//modCount表示链表的变化次数
return null;
}
int cmp;
Entry<K,V> parent;
/**
*根据”比较器”comparator为null与否,采取定制比较或默认比较(key的Comparable)不同的方式
*然后,按照”二叉排序树”的方式从根节点开始查找。如果找到了就覆盖旧的value,并返回旧的value。
*/
Comparator<? super K> cpr = comparator;
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;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
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;
else
return t.setValue(value);
} while (t != null);
}
/**
*如果上述遍历没有找到对应的key,则把key-value和最后的遍历得到的parent(也就是待插入位置的parent)
*构造成新的Entry,作为新的插入节点。
*/
Entry<K,V> e = new Entry<K,V>(key, value, parent);
//设置parent和该新节点的关系
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);//插入新节点后,可能会改变原有的红黑树结构,要进行修复
size++;
modCount++;
return null;
}

/** 红黑树插入后修复算法(该算法来源于CLR–算法3作者的姓氏第一个字母) */
private void fixAfterInsertion(Entry<K,V> x) {
//默认新插入的节点颜色为红色(这是为了尽量不改变红黑树黑节点的个数,具体可以查看”红黑树”的属性)
x.color = RED;
/** 直到 x 节点的父节点不是根,且 x 的父节点不是红色
(由于当x的父亲节点是黑色节点的时候,直接插入不会影响到红黑树的性质,所有就没有必要进行下面的操作了,
所以插入时,只考虑其父亲节点为红色的情况,只有这种情况下红黑树才需要修复操作)*/
while (x != null && x != root && x.parent.color == RED) {
/**
*新插入节点x的父节点为红色的时候又分为一下几种情况:
*1 x 的父节点P是其父节点G的左子节点:
*1.1 x的父亲节点p的兄弟节点为红色.解决办法:父设黑,父的兄设黑,父的父设红并以父的父为新节点往上遍历直到root涂黑。
*1.2 x的父亲节点p的兄弟节点为黑色.(此时,又分x是其父的左和右孩子两种情况)
*  1.2.1 x是其父右子。解决办法: x变黑,父的父变红,父左旋转,父的父右旋转。
*  1.2.2 x是其父左子。解决办法:父变黑,父的父变红,          父的父右旋转,
*
*2 x 的父节点P是其父节点G的右子节点(道理同上)
*/
// 1 如果 x 的父节点P是其父节点G的左子节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//1.1 如果x的父亲节点p的兄弟节点为红色
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);//将x的父亲节点设为黑色
setColor(y, BLACK);          //将x的父亲节点兄弟节点设为黑色
setColor(parentOf(parentOf(x)), RED);//将x的父亲节点的父亲节点设为红色
x = parentOf(parentOf(x));           //将x设为其父亲节点的父亲节点,以便继续往上遍历
} else {//1.2 如果x的父亲节点p的兄弟节点为黑色
if (x == rightOf(parentOf(x))) {//1.2.1 下面左转的目的是变成1.2.2的情况
x = parentOf(x);//x指向其父
rotateLeft(x);  //当前的x指向左旋转
}
//1.2.2情况的处理
setColor(parentOf(x), BLACK); //父设黑
setColor(parentOf(parentOf(x)), RED);//父父设红
rotateRight(parentOf(parentOf(x)));//父父右旋转
}
} else {//2 道理同上,只是出现right的地方换成了left,出现left的地方换成了right
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
//最后将root根节点置黑,以满足“红黑树”黑头黑尾的性质。
root.color = BLACK;
}

—————

TreeMap的删除操作的实现:

private void deleteEntry(Entry<K,V> p) {
modCount++; //修改次数加1
size–;           //节点个数减1
// 如果被删除节点的左子树、右子树都不为空
if (p.left != null && p.right != null)    {
// 用 p 节点的中序后继节点代替 p 节点
Entry<K,V> s = successor (p);
p.key = s.key;
p.value = s.value;
p = s;
}

/**

*经过上面的操作(用 p 节点的中序后继节点代替 p 节点),实际要执行的删除操作就

*变成了针对p的中序后继节点(如果存在的话)的操作:

*既然要删除的节点是后继节点,那么要删除的节点的左子树一定为空,所以:

* 1 当(删除的节点)p为黑色时就有两种情况:

*   1.1 p的左右均为null;

*   1.2 p的左为空,右子树为一单个红色节点(并且该红色节点的左右为null,如果不为空就不会满足红黑树的性质了)

* 2 当p为红色时:其左右子树比为null(也只有这样才能满足红黑树的性质)

*/
// 如果 p 节点的左节点存在,replacement 代表左节点;否则代表右节点。
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null)    { //1.2的情况
replacement.parent = p.parent;
// 如果 p 没有父节点,则 replacemment 变成父节点
if (p.parent == null)
root = replacement;
// 如果 p 节点是其父节点的左子节点,则把其父左设为replacement
else if (p == p.parent.left)
p.parent.left  = replacement;
// 如果 p 节点是其父节点的右子节点,则把其父右设为replacement
else
p.parent.right = replacement;
p.left = p.right = p.parent = null;
// 由于当p是红色节点时,直接删除后不会影响到红黑树的高度,所以就不用修复,当为黑节点时需修复红黑树
if (p.color == BLACK)
fixAfterDeletion(replacement);

}  else if (p.parent == null) {  // 如果 p 节点没有父节点,置为空链
root = null;
}  else   { 1.1或2的情况:即要删除的p节点的左右子树均为null
if (p.color == BLACK) //如果是p为黑色,就进行修复(红色时不必)
// 修复红黑树
fixAfterDeletion(p);

if (p.parent != null)  { //在p父不为空的情况下,对其父的左(或右)节点进行删除后的置空处理
// 如果 p 是其父节点的左子节点
if (p == p.parent.left)
p.parent.left = null;
// 如果 p 是其父节点的右子节点
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
——

// 删除节点后修复红黑树
private void fixAfterDeletion(Entry<K,V> x)
{

/**

*由于x为红的情况不存在修复的情况,所以

*当x为黑色是修复存在如下情况:

*1 x 是其父节点的左子节点

*   1.1 当删除的节点有一个红孩子时。解决办法:红孩子目前属于删除节点父的一个孩子,把该孩子变成黑色。

*   1.2 当删除的节点左右子为null的情况下:

*        1.2.1 删除节点的兄弟节点为红色。解决办法:父变红,兄变黑,父左旋转。

*        1.2.2 删除节点的兄弟节点为黑色。(又有多种情况)

*                1.2.2.1 兄有两个黑子节点。解决办法:兄变红,子变黑,红父时变黑(黑父时,从黑父往上遍历)

*                1.2.2.2 兄的子节点左黑右红。解决办法:兄变父色,父变黑,兄红子变黑,父左旋转。

*                1.2.2.3 兄的子节点左红右黑。解决办法:兄红子变父色,父变黑,兄右旋转,父左旋转。

*2 x 是其父节点的右子节点(道理同上)

*/
// 直到 x 不是根节点,且 x 的颜色是黑色
while (x != root && colorOf(x) == BLACK)   {
// 如果 x 是其父节点的左子节点
if (x == leftOf(parentOf(x)))  { //1 情况
// 获取 x 节点的兄弟节点
Entry<K,V> sib = rightOf(parentOf(x));
// 如果 sib 节点是红色
if (colorOf(sib) == RED) { //1.2.1 情况
// 将 sib 节点设为黑色
setColor(sib, BLACK);
// 将 x 的父节点设为红色
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
// 再次将 sib 设为 x 的父节点的右子节点
sib = rightOf(parentOf(x));
}
// 如果 sib 的两个子节点都是黑色
if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { // 1.2.2.1 情况
// 将 sib 设为红色
setColor(sib, RED);
// 让 x 等于 x 的父节点,继续遍历
x = parentOf(x);
} else {
// 如果 sib 的只有右子节点是黑色
if (colorOf(rightOf(sib)) == BLACK) { // 1.2.2.3 情况,下面几行操作是先将其转换成1.2.2.2的情况
// 将 sib 的左子节点也设为黑色
setColor(leftOf(sib), BLACK);
// 将 sib 设为红色
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}

// 1.2.2.2 情况
// 设置 sib 的颜色与 x 的父节点的颜色相同
setColor(sib, colorOf(parentOf(x)));
// 将 x 的父节点设为黑色
setColor(parentOf(x), BLACK);
// 将 sib 的右子节点设为黑色
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // 2情况(道理同上)

// 获取 x 节点的兄弟节点
Entry<K,V> sib = leftOf(parentOf(x));
// 如果 sib 的颜色是红色
if (colorOf(sib) == RED)  {
// 将 sib 的颜色设为黑色
setColor(sib, BLACK);
// 将 sib 的父节点设为红色
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
// 如果 sib 的两个子节点都是黑色
if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) {
// 将 sib 设为红色
setColor(sib, RED);
// 让 x 等于 x 的父节点
x = parentOf(x);
} else {
// 如果 sib 只有左子节点是黑色
if (colorOf(leftOf(sib)) == BLACK)  {
// 将 sib 的右子节点也设为黑色
setColor(rightOf(sib), BLACK);
// 将 sib 设为红色
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
// 将 sib 的颜色设为与 x 的父节点颜色相同
setColor(sib, colorOf(parentOf(x)));
// 将 x 的父节点设为黑色
setColor(parentOf(x), BLACK);
// 将 sib 的左子节点设为黑色
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}

//最终设置root为黑色
setColor(x, BLACK);
}

———————————————————————–

———红黑树(R-B Tree)——————–

红黑树:一种二叉查找树(Binary Search Tree),但在每个结点上增加一个存储位表示结点的颜色(Red or Black)

通过对任何一条从根到叶子的路径上各个结点着色方式的限制,使得:

–红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的。

–红黑树能保证在最坏的情况下,基本的动态几何操作的时间均为O(lgn)

*红黑树上每个结点内含有5个域:color、key、left、right、Entry。

*红黑树满足以下条件:(黑头,黑尾,两红不相挨)

—-每个结点要么红的,要么黑的

—-根结点是黑的

—-每个叶子结点,即空结点(NULL)是黑的

—-如果结点是红的,那么它的两个儿子都是黑的

—-对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点

对于给定的黑色高度为 N 的红黑树,从根到叶子节点的最短路径长度为 N-1,最长路径长度为 2 * (N-1)

红黑树通过上面这种限制来保证它大致是平衡的——因为红黑树的高度不会无限增高,这样保证红黑树在最坏情况下都是高效的,不会出现普通排序二叉树的最坏的情况(插入数据时的有序情况下导致的)。

另外上面TreeMap中蓝色的注释部分,其实表示的就是红黑树在插入和删除元素时的修复情况。

网上有很多关于红黑树的详细解析,这里也就不再做过多的解释了。

关于红黑树的介绍 推荐:http://hi.baidu.com/20065562/blog/item/93b2d17fd6f391320dd7da44.html

http://blog.csdn.net/v_JULY_v/article/details/6105630

 

 

http://hi.baidu.com/yao1111yao/item/d3ed3d08f80df51febfe386d



快乐成长 每天进步一点点