摘要：在上一节中，在中用了链表和红黑树两种方式解决冲突，在中也是用红黑树存储的。其中节点颜色为黑色红黑树的左旋和右旋红黑树的插入和删除，都有可能破坏其特性，就不是一棵红黑树了，所以要调整。
在上一节中，HashMap在jdk 1.8中用了链表和红黑树两种方式解决冲突，在TreeMap中也是用红黑树存储的。下面分析一下红黑树的结构和基本操作。
一、红黑树的特征和基本操作
上一节中已经描述了红黑树的基本概念和特征，下面直接通过一个例子分析红黑树的构造和调整方法。
1、红黑树的数据结构
红黑树是一棵二叉查找树，在二叉树的基础上增加了节点的颜色，下面是TreeMap中的红黑树定义：
private static final boolean RED = false;
private static final boolean BLACK = true;
static final class Entry implements Map.Entry {
K key;
V value;
Entry left;
Entry right;
Entry parent;
boolean color = BLACK;
/**
* 给定key、value和父节点，构造一个新的。其中节点颜色为黑色
*/
Entry(K key, V value, Entry parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
2、红黑树的左旋和右旋
红黑树的插入和删除，都有可能破坏其特性，就不是一棵红黑树了，所以要调整。调整的方法又两种，一种是改变某个节点的颜色，另外一种是结构调整，包括左旋和右旋。
左旋：将X的节点的右儿子节点Y变为其父节点，并且将Y的左子树变为X的右子树，变换过程入下图
右旋：将X的节点的左儿子节点Y变为其父节点，并且将Y的右子树变为X的左子树，变换过程入下图
3、插入节点后调整红黑树
当在红黑树中插入一个节点后，可能会破坏红黑树的规则，首先再回顾一下红黑数的特点：
节点是红色或黑色。
根节点是黑色。
每个叶子节点都是黑色的空节点（NIL节点）。
每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
从上面的条件可以看出，a肯定是不会违背的。插入的节点不在根节点处，所以b也不会违背。插入的节点时非空节点，c也不会违背。最有可能违背的就是d和e。而在我们插入节点时，先将要插入的节点颜色设置为红色，这样也就不会违背e。所以，插入后只需要调整不违背e就可以。
插入后调整需要分三种情况来处理：
插入的是根节点:
处理方法是直接将根节点颜色设置为黑色
插入节点的父节点为黑色节点或父节点为根节点
不需要处理
插入节点的父节点时红色节点
这种又分为三种情况
下面假设插入节点为x，父节点为xp，祖父节点为xpp，祖父节点的左儿子为xppl，祖父节点的右儿子为xppr
S1：当前节点的父节点xp是红色，且当前节点的祖父节xpp点的另一个子节点（xppl或者xppr）也是红色
处理逻辑：将父节点xp设为红色，祖父节点的儿子节点（xppl或者xppr）设为黑色，将祖父节点xpp设为红色，将祖父节点xpp设为当前节点，继续处理。
S2：当前节点的父节点xp是红色，祖父节点的儿子节点（xppl或者xppr）是黑色，且当前节点x是其父节点xp的右孩子
处理逻辑：父节点xp作为当前节点x， 以当前节点x为支点进行左旋。
S3：当前节点的父节点xp是红色，祖父节点的儿子节点（xppl或者xppr）是黑色，且当前节点是其父节点xp的左孩子
处理逻辑：将父节点xp设置为黑色，祖父节点xpp设置为红色，以祖父节点xpp为支点进行右旋
4、删除节点后调整红黑树
未完，待续。。。
3、构造一棵红黑树
通过插入节点，构造红黑树
现在给定节点8 5 3 9 12 1 4 2，依次插入红黑树中，具体流程见下图：
在红黑树中删除节点
未完，待续。。。
二、HashMap中的红黑树相关源码
static final class TreeNode extends LinkedHashMap.Entry {
TreeNode parent; // red-black tree links
TreeNode left;
TreeNode right;
//在节点删除后，需解除链接
TreeNode prev;
boolean red;
TreeNode(int hash, K key, V val, Node next) {
super(hash, key, val, next);
}
/**
* 返回根节点
*/
final TreeNode root() {
for (TreeNode r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
/**
* 确保根节点就是第一个节点
*/
static void moveRootToFront(Node[] tab, TreeNode root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNode first = (TreeNode)tab[index];
//如果根节点不是第一个节点，进行调整
if (root != first) {
Node rn;
tab[index] = root;
TreeNode rp = root.prev;
if ((rn = root.next) != null)
((TreeNode)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
/**
* 根据hash值和key查询节点
*/
final TreeNode find(int h, Object k, Class kc) {
TreeNode p = this;
do {
int ph, dir; K pk;
TreeNode pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
/**
* 根据hash值和key查询节点
*/
final TreeNode getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
/**
* 将链表转换为红黑树
*/
final void treeify(Node[] tab) {
TreeNode root = null;
//从第一个节点开始
for (TreeNode x = this, next; x != null; x = next) {
next = (TreeNode)x.next;
x.left = x.right = null;
//如果root节点为null，x为根节点，此节点为黑色，父节点为null
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
//x的key值
K k = x.key;
//x的hash值
int h = x.hash;
Class kc = null;
for (TreeNode 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 xp = p;
//dir <=0 左子树搜索，并且判断左儿子是否为空，表示是否到叶子节点
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);
}
/**
* 红黑树转换为链表
*/
final Node untreeify(HashMap map) {
Node hd = null, tl = null;
for (Node q = this; q != null; q = q.next) {
Node p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
/**
* 插入一个节点
*/
final TreeNode putTreeVal(HashMap map, Node[] tab,
int h, K k, V v) {
Class kc = null;
boolean searched = false;
TreeNode root = (parent != null) ? root() : this;
//从根据点开始，和当前搜索节点的hash比较
for (TreeNode p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
//hash和key都一致
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode 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;
}
dir = tieBreakOrder(k, pk);
}
TreeNode xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node xpn = xp.next;
//新建节点
TreeNode x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode)xpn).prev = x;
//插入元素，判断是否平衡，并且调整。确保根节点就是第一个节点
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
/**
* Removes the given node, that must be present before this call.
* This is messier than typical red-black deletion code because we
* cannot swap the contents of an interior node with a leaf
* successor that is pinned by "next" pointers that are accessible
* independently during traversal. So instead we swap the tree
* linkages. If the current tree appears to have too few nodes,
* the bin is converted back to a plain bin. (The test triggers
* somewhere between 2 and 6 nodes, depending on tree structure).
*/
final void removeTreeNode(HashMap map, Node[] tab,
boolean movable) {
int n;
if (tab == null || (n = tab.length) == 0)
return;
int index = (n - 1) & hash;
TreeNode first = (TreeNode)tab[index], root = first, rl;
TreeNode succ = (TreeNode)next, pred = prev;
if (pred == null)
tab[index] = first = succ;
else
pred.next = succ;
if (succ != null)
succ.prev = pred;
if (first == null)
return;
if (root.parent != null)
root = root.root();
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
tab[index] = first.untreeify(map); // too small
return;
}
TreeNode p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
TreeNode s = pr, sl;
while ((sl = s.left) != null) // find successor
s = sl;
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode sr = s.right;
TreeNode pp = p.parent;
if (s == pr) { // p was s"s direct parent
p.parent = s;
s.right = p;
}
else {
TreeNode sp = s.parent;
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
pr.parent = s;
}
p.left = null;
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
if (sr != null)
replacement = sr;
else
replacement = p;
}
else if (pl != null)
replacement = pl;
else if (pr != null)
replacement = pr;
else
replacement = p;
if (replacement != p) {
TreeNode pp = replacement.parent = p.parent;
if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}
TreeNode r = p.red ? root : balanceDeletion(root, replacement);
if (replacement == p) { // detach
TreeNode pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
moveRootToFront(tab, r);
}
/* ------------------------------------------------------------ */
// Red-black tree methods, all adapted from CLR
//左旋
static TreeNode rotateLeft(TreeNode root,
TreeNode p) {
TreeNode r, pp, rl;
//以p为左旋支点，且p不为空，右儿子不为空
if (p != null && (r = p.right) != null) {
//将p的右儿子r的左儿子rl变为p的右儿子
if ((rl = p.right = r.left) != null)
rl.parent = p;
//处理p、l和p父节点的关系
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
else if (pp.left == p)
pp.left = r;
else
pp.right = r;
//处理p和r的关系
r.left = p;
p.parent = r;
}
return root;
}
//右旋
static TreeNode rotateRight(TreeNode root,
TreeNode p) {
TreeNode l, pp, lr;
//p:右旋支点，不为空，p的左儿子l不为空
if (p != null && (l = p.left) != null) {
//将左儿子的右子树变为p的左子树
if ((lr = p.left = l.right) != null)
lr.parent = p;
//p的父节点变为l的父节点
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
//如果p为右儿子，则p的父节点的右儿子变为l,否则左儿子变为l
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
//p变为l的右儿子
l.right = p;
p.parent = l;
}
return root;
}
static TreeNode balanceInsertion(TreeNode root,
TreeNode x) {
//插入节点初始化为红色
x.red = true;
//xp:父节点，xpp:祖父节点， xppl：祖父节点的左儿子，xppr:祖父节点的右儿子
//循环遍历
for (TreeNode xp, xpp, xppl, xppr;;) {
//插入的节点为根节点，节点颜色转换为黑色
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//当前节点的父为黑色节点或者父节点为根节点，直接返回
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//祖父节点的左儿子是父节点
if (xp == (xppl = xpp.left)) {
//S1：当前节点的父节点xp是红色，且当前节点的祖父节xpp点的另一个子节点（xppl或者xppr）也是红色
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
//S2：当前节点的父节点xp是红色，祖父节点的儿子节点（xppl或者xppr）是黑色，且当前节点x是其父节点xp的右孩子
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//S3：当前节点的父节点xp是红色，祖父节点的儿子节点（xppl或者xppr）是黑色，且当前节点是其父节点xp的左孩子
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
else {
//S1：当前节点的父节点xp是红色，且当前节点的祖父节xpp点的另一个子节点（xppl或者xppr）也是红色
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
//S2：当前节点的父节点xp是红色，祖父节点的儿子节点（xppl或者xppr）是黑色，且当前节点x是其父节点xp的右孩子
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//S3：当前节点的父节点xp是红色，祖父节点的儿子节点（xppl或者xppr）是黑色，且当前节点是其父节点xp的左孩子
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
static TreeNode balanceDeletion(TreeNode root,
TreeNode x) {
for (TreeNode xp, xpl, xpr;;) {
if (x == null || x == root)
return root;
else if ((xp = x.parent) == null) {
x.red = false;
return x;
}
else if (x.red) {
x.red = false;
return root;
}
else if ((xpl = xp.left) == x) {
if ((xpr = xp.right) != null && xpr.red) {
xpr.red = false;
xp.red = true;
root = rotateLeft(root, xp);
xpr = (xp = x.parent) == null ? null : xp.right;
}
if (xpr == null)
x = xp;
else {
TreeNode sl = xpr.left, sr = xpr.right;
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
xpr.red = true;
x = xp;
}
else {
if (sr == null || !sr.red) {
if (sl != null)
sl.red = false;
xpr.red = true;
root = rotateRight(root, xpr);
xpr = (xp = x.parent) == null ?
null : xp.right;
}
if (xpr != null) {
xpr.red = (xp == null) ? false : xp.red;
if ((sr = xpr.right) != null)
sr.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateLeft(root, xp);
}
x = root;
}
}
}
else { // symmetric
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left;
}
if (xpl == null)
x = xp;
else {
TreeNode sl = xpl.left, sr = xpl.right;
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
xpl.red = true;
x = xp;
}
else {
if (sl == null || !sl.red) {
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ?
null : xp.left;
}
if (xpl != null) {
xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
}
}
}
}
三、总结
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/72103.html
