1. 准备知识 - 红黑树
学过数据结构与算法的同学对树一定不陌生。
二叉树：
二叉树是每个结点最多有两个子树的树结构。
二叉查找树：
二叉查找树是具有下列性质的二叉树：
若左子树不空，则左子树上所有结点的值均小于它的根结点的值。
若右子树不空，则右子树上所有结点的值均大于它的根结点的值。
左、右子树也分别为二叉排序树。
没有键值相等的节点。
平衡二叉树：
一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。也就是说该二叉树的任何一个子节点，其左右子树的高度都相近。
红黑树：
红黑树(Red Black Tree)是一种自平衡二叉查找树，查找效率O(logn)，它具有以下五个特点：
1. 每个结点都是红色或者黑色。
2. 根结点是黑色。
3. 每个叶子(NIL结点或空结点)是黑色。
4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
我们知道一颗基本的二叉树他们都需要满足一个基本性质：即树中的任何节点的值大于它的左子节点，且小于它的右子节点。按照这个基本性质使得树的检索效率大大提高。我们知道在生成二叉树的过程是非常容易失衡的，最坏的情况就是一边倒（只有右/左子树），这样势必会导致二叉树的检索效率大大降低（O(n)），所以为了维持二叉树的平衡，大牛们提出了各种实现的算法，如：AVL，SBT，伸展树，TREAP ，红黑树等等。
红黑树示例图：
2. Java实现红黑树
通过熟悉下面的代码，TreeMap的原理也就能庖丁解牛般的理解了。
/**
* 红黑树的Java实现(代码说明)
*
* 红黑树的基本操作是添加、删除和旋转。
*
* 在对红黑树进行添加或删除后，会用到旋转方法。
* 为什么呢？道理很简单，添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，
* 也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树。
* 简单点说，旋转的目的是让树保持红黑树的特性。
*
* 旋转包括两种：左旋 和 右旋。下面分别对红黑树的基本操作进行介绍。
*/
private static class RBTree<T extends Comparable<T>> {
// 根结点
private RBTNode<T> mRoot;
private static final boolean RED = false;
private static final boolean BLACK = true;
static class RBTNode<T extends Comparable<T>> {
// 颜色
boolean color;
// 关键字
T key;
// 左孩子
RBTNode<T> left;
// 右孩子
RBTNode<T> right;
// 父结点
RBTNode<T> parent;
public RBTNode(T key, boolean color, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right) {
this.key = key;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
}
public RBTree() {
mRoot = null;
}
private RBTNode<T> parentOf(RBTNode<T> node) {
return node != null ? node.parent : null;
}
private boolean colorOf(RBTNode<T> node) {
return node != null ? node.color : BLACK;
}
private boolean isRed(RBTNode<T> node) {
return ((node != null) && (node.color == RED)) ? true : false;
}
private boolean isBlack(RBTNode<T> node) {
return !isRed(node);
}
private void setBlack(RBTNode<T> node) {
if (node != null)
node.color = BLACK;
}
private void setRed(RBTNode<T> node) {
if (node != null)
node.color = RED;
}
private void setParent(RBTNode<T> node, RBTNode<T> parent) {
if (node != null)
node.parent = parent;
}
private void setColor(RBTNode<T> node, boolean color) {
if (node != null)
node.color = color;
}
/*
* 前序遍历"红黑树"
*/
private void preOrder(RBTNode<T> tree) {
if (tree != null) {
System.out.print(tree.key + " ");
preOrder(tree.left);
preOrder(tree.right);
}
}
public void preOrder() {
preOrder(mRoot);
}
/*
* 中序遍历"红黑树"
*/
private void inOrder(RBTNode<T> tree) {
if (tree != null) {
inOrder(tree.left);
System.out.print(tree.key + " ");
inOrder(tree.right);
}
}
public void inOrder() {
inOrder(mRoot);
}
/*
* 后序遍历"红黑树"
*/
private void postOrder(RBTNode<T> tree) {
if (tree != null) {
postOrder(tree.left);
postOrder(tree.right);
System.out.print(tree.key + " ");
}
}
public void postOrder() {
postOrder(mRoot);
}
/*
* (递归实现)查找"红黑树x"中键值为key的节点
*/
private RBTNode<T> search(RBTNode<T> x, T key) {
if (x == null)
return x;
int cmp = key.compareTo(x.key);
if (cmp < 0)
return search(x.left, key);
else if (cmp > 0)
return search(x.right, key);
else
return x;
}
public RBTNode<T> search(T key) {
return search(mRoot, key);
}
/*
* (非递归实现)查找"红黑树x"中键值为key的节点
*/
private RBTNode<T> iterativeSearch(RBTNode<T> x, T key) {
while (x != null) {
int cmp = key.compareTo(x.key);
if (cmp < 0)
x = x.left;
else if (cmp > 0)
x = x.right;
else
return x;
}
return x;
}
public RBTNode<T> iterativeSearch(T key) {
return iterativeSearch(mRoot, key);
}
/*
* 查找最小结点：返回tree为根结点的红黑树的最小结点。
*/
private RBTNode<T> minimum(RBTNode<T> tree) {
if (tree == null)
return null;
while (tree.left != null)
tree = tree.left;
return tree;
}
public T minimum() {
RBTNode<T> p = minimum(mRoot);
if (p != null)
return p.key;
return null;
}
/*
* 查找最大结点：返回tree为根结点的红黑树的最大结点。
*/
private RBTNode<T> maximum(RBTNode<T> tree) {
if (tree == null)
return null;
while (tree.right != null)
tree = tree.right;
return tree;
}
public T maximum() {
RBTNode<T> p = maximum(mRoot);
if (p != null)
return p.key;
return null;
}
/*
* 找结点(x)的后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"。
*/
public RBTNode<T> successor(RBTNode<T> x) {
// 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
if (x.right != null)
return minimum(x.right);
// 如果x没有右孩子。则x有以下两种可能：
// (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
// (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
RBTNode<T> y = x.parent;
while ((y != null) && (x == y.right)) {
x = y;
y = y.parent;
}
return y;
}
/*
* 找结点(x)的前驱结点。即，查找"红黑树中数据值小于该结点"的"最大结点"。
*/
public RBTNode<T> predecessor(RBTNode<T> x) {
// 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
if (x.left != null)
return maximum(x.left);
// 如果x没有左孩子。则x有以下两种可能：
// (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
// (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
RBTNode<T> y = x.parent;
while ((y != null) && (x == y.left)) {
x = y;
y = y.parent;
}
return y;
}
/*
* 对x进行左旋，意味着"将x变成一个左节点"。
*
* 对红黑树的节点(x)进行左旋转
*
* 左旋示意图(对节点x进行左旋)：
* px px
* / /
* x y
* / \ --(左旋)-. / \ #
* lx y x ry
* / \ / \
* ly ry lx ly
*
*
*/
private void leftRotate(RBTNode<T> x) {
// x的右孩子为y
RBTNode<T> y = x.right;
// 将 “y的左孩子” 设为 “x的右孩子”；
// 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
x.right = y.left;
if (y.left != null) {
y.left.parent = x;
}
// 将 “x的父亲” 设为 “y的父亲”
y.parent = x.parent;
if (x.parent == null) {
// 如果 “x的父亲” 是空节点，则将y设为根节点
this.mRoot = y;
} else {
if (x.parent.left == x) {
// 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
x.parent.left = y;
} else {
// 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
x.parent.right = y;
}
}
// 将 “x” 设为 “y的左孩子”
y.left = x;
// 将 “x的父节点” 设为 “y”
x.parent = y;
}
/*
* 对y进行右旋，意味着"将y变成一个右节点"。
*
* 对红黑树的节点(y)进行右旋转
*
* 右旋示意图(对节点y进行左旋)：
* py py
* / /
* y x
* / \ --(右旋)-. / \ #
* x ry lx y
* / \ / \ #
* lx rx rx ry
*
*/
private void rightRotate(RBTNode<T> y) {
// 设置x是当前节点的左孩子。
RBTNode<T> x = y.left;
// 将 “x的右孩子” 设为 “y的左孩子”；
// 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
y.left = x.right;
if (x.right != null) {
x.right.parent = y;
}
// 将 “y的父亲” 设为 “x的父亲”
x.parent = y.parent;
if (y.parent == null) {
// 如果 “y的父亲” 是空节点，则将x设为根节点
this.mRoot = x;
} else {
if (y == y.parent.right) {
// 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
y.parent.right = x;
} else {
// (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
y.parent.left = x;
}
}
// 将 “y” 设为 “x的右孩子”
x.right = y;
// 将 “y的父节点” 设为 “x”
y.parent = x;
}
/**
* 添加
*
* 将一个节点插入到红黑树中，需要执行哪些步骤呢？
* 首先，将红黑树当作一颗二叉查找树，将节点插入；
* 然后，将节点着色为红色；
* 最后，通过"旋转和重新着色"等一系列操作来修正该树，使之重新成为一颗红黑树。
*
* 详细描述如下：
*
* 第一步: 将红黑树当作一颗二叉查找树，将节点插入。
* 红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。
* 也就意味着，树的键值仍然是有序的。
* 此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。
* 这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。
*
* 好吧？那接下来，我们就来想方设法的旋转以及重新着色，使这颗树重新成为红黑树！
*
* 第二步：将插入的节点着色为"红色"。
* 为什么着色成红色，而不是黑色呢？为什么呢？在回答之前，我们需要重新温习一下红黑树的特性：
* (1) 每个节点或者是黑色，或者是红色。
* (2) 根节点是黑色。
* (3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
* (4) 如果一个节点是红色的，则它的子节点必须是黑色的。
* (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
*
* 将插入的节点着色为红色，不会违背"特性(5)"！少违背一条特性，就意味着我们需要处理的情况越少。
* 接下来，就要努力的让这棵树满足其它性质即可；满足了的话，它就又是一颗红黑树了。o(∩∩)o...哈哈
*
* 第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。
* 第二步中，将插入节点着色为"红色"之后，不会违背"特性(5)"。那它到底会违背哪些特性呢？
* 对于"特性(1)"，显然不会违背了。因为我们已经将它涂成红色了。
* 对于"特性(2)"，显然也不会违背。在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。
* 而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。
* 对于"特性(3)"，显然不会违背了。这里的叶子节点是指的空叶子节点，插入非空节点并不会对它们造成影响。
* 对于"特性(4)"，是有可能违背的！
* 那接下来，想办法使之"满足特性(4)"，就可以将树重新构造成红黑树了。
*/
/*
* 将结点插入到红黑树中
*
* 参数说明：
* node 插入的结点 // 对应《算法导论》中的node
*/
private void insert(RBTNode<T> node) {
int cmp;
RBTNode<T> y = null;
RBTNode<T> x = this.mRoot;
// 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
while (x != null) {
y = x;
cmp = node.key.compareTo(x.key);
if (cmp < 0)
x = x.left;
else
x = x.right;
}
node.parent = y;
if (y != null) {
cmp = node.key.compareTo(y.key);
if (cmp < 0)
y.left = node;
else
y.right = node;
} else {
this.mRoot = node;
}
// 2. 设置节点的颜色为红色
node.color = RED;
// 3. 将它重新修正为一颗二叉查找树
insertFixUp(node);
}
/*
* 红黑树插入修正函数
*
* 在向红黑树中插入节点之后(失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
*
* 参数说明：
* node 插入的结点 // 对应《算法导论》中的z
*/
private void insertFixUp(RBTNode<T> node) {
RBTNode<T> parent, gparent;
// 若“父节点存在，并且父节点的颜色是红色”
while (((parent = parentOf(node)) != null) && isRed(parent)) {
gparent = parentOf(parent);
// 若“父节点”是“祖父节点的左孩子”
if (parent == gparent.left) {
// Case 1条件：叔叔节点是红色
RBTNode<T> uncle = gparent.right;
if ((uncle != null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2条件：叔叔是黑色，且当前节点是右孩子
if (parent.right == node) {
RBTNode<T> tmp;
leftRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3条件：叔叔是黑色，且当前节点是左孩子。
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
} else { //若“z的父节点”是“z的祖父节点的右孩子”
// Case 1条件：叔叔节点是红色
RBTNode<T> uncle = gparent.left;
if ((uncle != null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2条件：叔叔是黑色，且当前节点是左孩子
if (parent.left == node) {
RBTNode<T> tmp;
rightRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3条件：叔叔是黑色，且当前节点是右孩子。
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
// 将根节点设为黑色
setBlack(this.mRoot);
}
/*
* 新建结点(key)，并将其插入到红黑树中
*
* 参数说明：
* key 插入结点的键值
*/
public void insert(T key) {
RBTNode<T> node=new RBTNode<T>(key,BLACK,null,null,null);
// 如果新建结点失败，则返回。
if (node != null)
insert(node);
}
/**
* 删除操作
*
* 将红黑树内的某一个节点删除。
* 需要执行的操作依次是：首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；
* 然后，通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。
*
* 详细描述如下：
* 第一步：将红黑树当作一颗二叉查找树，将节点删除。
* 这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况：
* ① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。
* ② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
* ③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；
* 之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，
* 再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了，下面就考虑后继节点。
* 在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子非空。
* 既然"的后继节点"不可能双子都非空，就意味着"该节点的后继节点"要么没有儿子，要么只有一个儿子。
* 若没有儿子，则按"情况① "进行处理；若只有一个儿子，则按"情况② "进行处理。
*
* 第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。
* 因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，
* 使之重新成为一棵红黑树。
*/
/*
* 删除结点(node)，并返回被删除的结点
*
* 参数说明：
* node 删除的结点
*/
private void remove(RBTNode<T> node) {
RBTNode<T> child, parent;
boolean color;
// 被删除节点的"左右孩子都不为空"的情况。
if ((node.left != null) && (node.right != null)) {
// 被删节点的后继节点。(称为"取代节点")
// 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。
RBTNode<T> replace = node;
// 获取后继节点
replace = replace.right;
while (replace.left != null)
replace = replace.left;
// "node节点"不是根节点(只有根节点不存在父节点)
if (parentOf(node) != null) {
if (parentOf(node).left == node)
parentOf(node).left = replace;
else
parentOf(node).right = replace;
} else {
// "node节点"是根节点，更新根节点。
this.mRoot = replace;
}
// child是"取代节点"的右孩子，也是需要"调整的节点"。
// "取代节点"肯定不存在左孩子！因为它是一个后继节点。
child = replace.right;
parent = parentOf(replace);
// 保存"取代节点"的颜色
color = colorOf(replace);
// "被删除节点"是"它的后继节点的父节点"
if (parent == node) {
parent = replace;
} else {
// child不为空
if (child != null)
setParent(child, parent);
parent.left = child;
replace.right = node.right;
setParent(node.right, replace);
}
replace.parent = node.parent;
replace.color = node.color;
replace.left = node.left;
node.left.parent = replace;
if (color == BLACK)
removeFixUp(child, parent);
node = null;
return;
}
if (node.left != null) {
child = node.left;
} else {
child = node.right;
}
parent = node.parent;
// 保存"取代节点"的颜色
color = node.color;
if (child != null)
child.parent = parent;
// "node节点"不是根节点
if (parent != null) {
if (parent.left == node)
parent.left = child;
else
parent.right = child;
} else {
this.mRoot = child;
}
if (color == BLACK)
removeFixUp(child, parent);
node = null;
}
/*
* 删除结点(z)，并返回被删除的结点
*
* 参数说明：
* tree 红黑树的根结点
* z 删除的结点
*/
public void remove(T key) {
RBTNode<T> node;
if ((node = search(mRoot, key)) != null)
remove(node);
}
/*
* 红黑树删除修正函数
*
* 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
*
* 参数说明：
* node 待修正的节点
*/
private void removeFixUp(RBTNode<T> node, RBTNode<T> parent) {
RBTNode<T> other;
while ((node == null || isBlack(node)) && (node != this.mRoot)) {
if (parent.left == node) {
other = parent.right;
if (isRed(other)) {
// Case 1: x的兄弟w是红色的
setBlack(other);
setRed(parent);
leftRotate(parent);
other = parent.right;
}
if ((other.left == null || isBlack(other.left)) &&
(other.right == null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.right == null || isBlack(other.right)) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
setBlack(other.left);
setRed(other);
rightRotate(other);
other = parent.right;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.right);
leftRotate(parent);
node = this.mRoot;
break;
}
} else {
other = parent.left;
if (isRed(other)) {
// Case 1: x的兄弟w是红色的
setBlack(other);
setRed(parent);
rightRotate(parent);
other = parent.left;
}
if ((other.left == null || isBlack(other.left)) &&
(other.right == null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.left == null || isBlack(other.left)) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
setBlack(other.right);
setRed(other);
leftRotate(other);
other = parent.left;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.left);
rightRotate(parent);
node = this.mRoot;
break;
}
}
}
if (node != null)
setBlack(node);
}
/*
* 销毁红黑树
*/
private void destroy(RBTNode<T> tree) {
if (tree == null)
return;
if (tree.left != null)
destroy(tree.left);
if (tree.right != null)
destroy(tree.right);
tree = null;
}
public void clear() {
destroy(mRoot);
mRoot = null;
}
/*
* 打印"红黑树"
*
* key -- 节点的键值
* direction -- 0，表示该节点是根节点;
* -1，表示该节点是它的父结点的左孩子;
* 1，表示该节点是它的父结点的右孩子。
*/
private void print(RBTNode<T> tree, T key, int direction) {
if (tree != null) {
if (direction == 0) // tree是根节点
System.out.printf("%2d(B) is root\n", tree.key);
else // tree是分支节点
System.out.printf("%2d(%s) is %2d's %6s child\n", tree.key, isRed(tree) ? "R" : "B", key, direction == 1 ? "right" : "left");
print(tree.left, tree.key, -1);
print(tree.right, tree.key, 1);
}
}
public void print() {
if (mRoot != null)
print(mRoot, mRoot.key, 0);
}
}
private static void testRBTree() {
final int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};
final boolean mDebugInsert = false; // "插入"动作的检测开关(false，关闭；true，打开)
final boolean mDebugDelete = false; // "删除"动作的检测开关(false，关闭；true，打开)
int i, ilen = a.length;
RBTree<Integer> tree = new RBTree<>();
System.out.printf("== 原始数据: ");
for (i = 0; i < ilen; i++)
System.out.printf("%d ", a);
System.out.printf("\n");
for (i = 0; i < ilen; i++) {
tree.insert(a);
// 设置mDebugInsert=true,测试"添加函数"
if (mDebugInsert) {
System.out.printf("== 添加节点: %d\n", a);
System.out.printf("== 树的详细信息: \n");
tree.print();
System.out.printf("\n");
}
}
System.out.printf("== 前序遍历: ");
tree.preOrder();
System.out.printf("\n== 中序遍历: ");
tree.inOrder();
System.out.printf("\n== 后序遍历: ");
tree.postOrder();
System.out.printf("\n");
System.out.printf("== 最小值: %s\n", tree.minimum());
System.out.printf("== 最大值: %s\n", tree.maximum());
System.out.printf("== 树的详细信息: \n");
tree.print();
System.out.printf("\n");
// 设置mDebugDelete=true,测试"删除函数"
if (mDebugDelete) {
for (i = 0; i < ilen; i++) {
tree.remove(a);
System.out.printf("== 删除节点: %d\n", a);
System.out.printf("== 树的详细信息: \n");
tree.print();
System.out.printf("\n");
}
}
// 销毁二叉树
tree.clear();
}
3. TreeMap的数据结构
TreeMap的定义如下：
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
}
TreeMap继承AbstractMap，实现NavigableMap、Cloneable、Serializable三个接口。其中AbstractMap表明TreeMap为一个Map即支持key-value的集合，NavigableMap（更多）则意味着它支持一系列的导航方法，具备针对给定搜索目标返回最接近匹配项的导航方法。
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
}
Entry类，实现了Map.Entry接口，里面包含key，value，左子树，右子树，父结点，颜色。
再来看看TreeMap的一些重要的属性和常量：
private static final boolean RED = false;
private static final boolean BLACK = true;
private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
private transient int size = 0;
private transient int modCount = 0;
RED: 红黑树的节点颜色--红色。
BLACK: 红黑树的节点颜色--黑色。
comparator: 比较器，因为TreeMap是有序的，通过comparator接口我们可以对TreeMap的内部排序进行控制。
root: 红黑树根结点。
size: 容器大小。
modCount: TreeMap修改的次数。
4. TreeMap的put方法
public V put(K key, V value) {
// 先拿到根结点
Entry<K,V> t = root;
// 如果根结点为空
if (t == null) {
compare(key, key);
// 新建结点，并赋值给root
root = new Entry<>(key, value, null);
// 存储数据size + 1
size = 1;
// 修改数 + 1
modCount++;
return null;
}
// 根结点不为空
int cmp;
// 插入结点的父结点
Entry<K,V> parent;
// 先判断是否在构造器中传入了外比较器
Comparator<? super K> cpr = comparator;
// 如果传入了外比较器，用外比较器比较，然后插入到二叉查找树的正确位置
// 如果传入了比较器，则不会判断空key，交由外部比较器比较
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 {
// 如果没有外部比较器，则需要判断key是否为空，为空抛出异常
if (key == null)
throw new NullPointerException();
// 按照key自身的内比较器比较，然后插入到二叉查找树的正确位置
@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;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 虽然插入完后，仍然为二叉查找树，但是不一定是红黑树，需要进行旋转，重着色进行修正
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
put步骤：
1. 如果根结点为空，新建结点，并赋值给root。
2. 根结点不为空，先判断是否在构造器中传入了外比较器，如果传入了外比较器，用外比较器比较，然后插入到二叉排序树的正确位置，此时不会判断空key，交由外部比较器比较。
3. 如果没有外部比较器，则需要判断key是否为空，为空抛出异常。按照key自身的内比较器比较，然后插入到二叉查找树的正确位置。
4. 虽然插入完后，仍然为二叉查找树，但是不一定是红黑树，需要进行旋转，重着色进行修正。修正过程可以参考上面Java实现的红黑树，过程不再赘述。
5. TreeMap的remove方法
public V remove(Object 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 (p.left != null && p.right != null) {
// 将p替换成后继结点
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
}
// 进行修正
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
p.left = p.right = p.parent = null;
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;
}
}
}
由于红黑树是一棵增强版的二叉查找树，红黑树的删除操作跟普通二叉查找树的删除操作也就非常相似，唯一的区别是红黑树在节点删除之后可能需要进行调整。现在考虑一棵普通二叉查找树的删除过程，可以简单分为两种情况：
1. 删除点p的左右子树都为空，或者只有一棵子树非空。
2. 删除点p的左右子树都非空。
对于上述情况1，处理起来比较简单，直接将p删除（左右子树都为空时），或者用非空子树替代p（只有一棵子树非空时）；对于情况2，可以用p的后继s（树中大于x的最小的那个元素）代替p，然后使用情况1删除s（此时s一定满足情况1，可以画画看）。删除结点成功后，进行旋转和重着色（如果需要），具体可以参考上面Java实现的红黑树。
6. TreeMap的clear方法
public void clear() {
modCount++;
size = 0;
root = null;
}
很简单，修改数+1，存储size设为0，根结点引用置为null，和一般的树clear一样。
7. TreeMap的遍历
@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
int expectedModCount = modCount;
// 从最左边的结点开始，然后逐个寻找下一个比它大的结点中最小的那个
for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
action.accept(e.key, e.value);
if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
}
}
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
从最左边的结点开始，然后逐个寻找下一个比它大的结点中最小的那个，这样输出也就是有序的了。
---------------------
【转载，仅作分享，侵删】
作者：况众文
原文：https://blog.csdn.net/u014294681/article/details/86249942
版权声明：本文为博主原创文章，转载请附上博文链接！
|
|
收藏
淘帖
踩
今天也要加油鸭
