TreeNode
概念
即Map中红黑树结构存储数据的单位；其中包含的方法很多，不一一列举；由此代码可知道，TreeNode继承自LinkedHashMap内部类Entry<K,V>，而Entry<K,V>又继承自HashMap.Node<K,V>，具体的字段介绍请看下面注释
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links 父节点
TreeNode<K,V> left; //左子树
TreeNode<K,V> right; //右子树
TreeNode<K,V> prev; // 删除后需要取消链接 needed to unlink next upon deletion
boolean red; //颜色属性
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
特性
- 每个节点要么是黑色，要么是红色。（节点非黑即红）
- 根节点是黑色。
- 每个叶子节点（NIL）是黑色。
- 如果一个节点是红色的，则它的子节点必须是黑色的。（也就是说父子节点不能同时为红色）
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。（这一点是平衡的关键）
TreeNode方法分析
putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v)：红黑树添加节点
/**
* Tree version of putVal.
* HashMap:此hashmap对象
* Node[]:内部Node数组
* int h:key的hash码
* K:要存储的Key
* V:要存储的Value
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;//定义K 的类信息
boolean searched = false;
//获取红黑树的根节点
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)//比较根节点的hash和要存入的key的hash
dir = -1;//要添加的元素应该放置在当前节点的左侧
else if (ph < h)
dir = 1;//要添加的元素应该放置在当前节点的右侧
else if ((pk = p.key) == k || (k != null && k.equals(pk)))//如果要存入的key和根节点完全相同，直接返回
return p;
// 走到这一步说明 当前节点的hash值 和 指定key的hash值 是相等的，但是equals不等
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) || //查看k是否实现了comparable
(dir = compareComparables(kc, k, pk)) == 0) {
// 走到这里说明：指定key没有实现comparable接口或者实现了comparable接口并且和当前节点的键对象比较之后相等
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q; // 找到了指定key键对应的
}
// 走到这里就说明，遍历了所有子节点也没有找到和当前键equals相等的节点
dir = tieBreakOrder(k, pk);// 最后比较一下当前节点键和指定key键的大小
}
TreeNode<K,V> xp = p;
/*
* 三种情况：
* 1.如果dir小于等于0，那么看当前节点的左节点是否为空，如果为空，
* 就可以把要添加的元素作为当前节点的左节点，如果不为空，还需要下一轮继续比较
*
* 2.如果dir大于等于0，那么看当前节点的右节点是否为空，如果为空，
* 就可以把要添加的元素作为当前节点的右节点，如果不为空，还需要下一轮继续比较
*
* 3.如果以上两条当中有一个子节点不为空，这个if中还做了一件事，那就是把p已经指向了对应的不为空的子节点，开始下一轮的比较
*/
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;//获取当前节点的next节点
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);// 创建一个新的树节点
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;// 链表中的next节点指向到这个新的树节点
x.parent = x.prev = xp;
if (xpn != null)// 如果原来的next节点不为空
((TreeNode<K,V>)xpn).prev = x;// 那么原来的next节点的前节点指向到新的树节点
moveRootToFront(tab, balanceInsertion(root, x));// 重新平衡，以及新的根节点置顶
return null;// 返回空，意味着产生了一个新节点
}
}
}
balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x)：红黑树的插入平衡算法，当树结构中新插入了一个节点后，要对树进行重新的结构化，以保证该树始终维持红黑树的特性。
/**
* 重新平衡红黑树，返回头结点
* @param root：根节点
* @param x：新添加的节点
* @param <K>
* @param <V>
* @return
*/
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true;//初始x节点颜色为红色
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//查看有没有父节点，如果没有说明是头节点，头节点为黑色，返回头节点
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//如果x的父节点不是红色(即黑色)，或者x的祖父节点为null，
// 则不必旋转或改颜色，直接返回头节点
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//走到这里说明x的父节点至少在第三层且父节点为红色，要重新平衡
//如果x的父节点是祖父节点的左子节点
if (xp == (xppl = xpp.left)) {
//如果父节点的兄弟节点不为null并且兄弟节点为红色
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;//兄弟节点改为黑色
xp.red = false;//父节点也变为黑色
xpp.red = true;//祖父节点变为红色
x = xpp;//更新x为祖父节点，进入下次循环
}
//如果x父节点的兄弟节点为null或者为黑色
else {
//如果x是父节点的右子节点
if (x == xp.right) {
root = rotateLeft(root, x = xp);//左旋
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//如果x是父节点的左子节点
if (xp != null) {
xp.red = false;//修改x父节点颜色为黑色
if (xpp != null) {
xpp.red = true;//修改祖父节点颜色为红色
root = rotateRight(root, xpp);//红黑树右旋，更新root值
}
}
}
}
//如果x的父节点是祖父节点的右子节点，和左子节点类似，对称
else {
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
rotateRight(TreeNode<K,V> root,TreeNode<K,V> p)：红黑树右旋，左旋类似
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
//如果p节点不为null并且p的左节点也不为null
if (p != null && (l = p.left) != null) {
//两件事：
// 1.将p.left节点更新为l.right
// 2.如果l.right不为null,更新其父节点为p
if ((lr = p.left = l.right) != null)
lr.parent = p;
//两件事：
//1.将l.parent更新为p.parent,
//2.如果p.parent为null,说明p是头节点，更新l为头节点，置为黑色
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
//p.parent即pp不为null,如果原p是pp的右节点，现在更新右节点为l
else if (pp.right == p)
pp.right = l;
//如果原p是pp的左节点，现在更新左节点为l
else
pp.left = l;
//右旋，所以更新l的右节点为p，p的父节点为l
l.right = p;
p.parent = l;
}
return root;
}
moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root)：把给定节点设为桶中的第一个元素
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
//如果root不为null并且tab不为null并且tab数组的长度大于0
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;//根据root的hash值计算到下标值
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];//获取数组下标index的第一个节点
if (root != first) {//如果当前first不等于root
Node<K,V> rn;
tab[index] = root;//替换桶首位
TreeNode<K,V> rp = root.prev;//获取root的前节点
//下面的代码为将root从以前的链表中抽取出来，并放置到链表头
if ((rn = root.next) != null)//如果root的下节点不为null
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
treeifyBin(tab, hash)：树化链表结构
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//数组长度没有达到MIN_TREEIFY_CAPACITY时，扩容解决链表节点过多的问题
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;//临时存储数据节点 hd:头节点，tl:尾节点，p:循环的当前节点
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 到目前为止 也只是把Node对象转换成了TreeNode对象
if ((tab[index] = hd) != null)
hd.treeify(tab);//树化节点
}
}
treeify(Node<K,V>[] tab)：树化链表
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//1.赋值x为this,即头节点，如果x不为null
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;// 获取x的下一个节点
x.left = x.right = null;// 设置当前节点的左右节点为空
if (root == null) {
x.parent = null;
x.red = false;
root = x; // 根节点指向到当前节点
}
else {
//如果root不为null,以下代码主要节点与节点的大小，然后构建红黑树
K k = x.key;//获取x的key
int h = x.hash;//获取x的hash
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
网友评论