TreeMap实现原理深究
Java TreeMap实现了SortedMap接口，也就是说会按照key的大小顺序对Map中的元素进行排序，key大小的评判可以通过其本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator）。
TreeMap底层通过红黑树（Red-Black tree）实现，也就意味着containsKey(), get(), put(), remove()都有着log(n)的时间复杂度。
这句话是我在网上摘抄的，对于这句话，有很多的不理解，所以通过查阅TreeMap的源码来解惑。(其实就是原文作者装逼，很多知识点就是不明说)
惑一：natural ordering
TreeMap实现了SortedMap接口，也就是说会按照key的大小顺序对Map中的元素进行排序，key大小的评判可以通过其本身的自然顺序（natural ordering）
先来看看这段代码：
TreeMap map = new TreeMap();
map.put("A","1");
map.put("C","2");
map.put("B","3");
map.put("E","4");
map.put("D","5");
System.out.println(map);
output:
{A=1, B=3, C=2, D=5, E=4}
可以发现，默认按照升序自动排序了。
通过查阅TreeMap源码，发现treeMap的put方法如下：
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
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();
@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;
}
/**
Compares two keys using the correct comparison method for this TreeMap.
*/
@SuppressWarnings("unchecked")
final int compare(Object k1, Object k2) {
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}
找出关键代码：
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();
@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);
}
因为直接使用TreeMap时，没有设置comparator，所以TreeMap的comparator属性一直是null,那代码就会一直走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;
else
return t.setValue(value);
} while (t != null);
然后再看do代码块中的关键代码：
cmp = k.compareTo(t.key);
k是作为参数传进来的对象，因为我传进来的k是String类型，所以只要String实现了Comparable接口的compareTo方法，那就会默认走string的排序算法，查看compareTo方法：
public int compareTo(String anotherString) {
int len1 = value.length;
int len2 = anotherString.value.length;
int lim = Math.min(len1, len2);
char v1[] = value;
char v2[] = anotherString.value;
int k = 0;
while (k < lim) {
char c1 = v1[k];
char c2 = v2[k];
if (c1 != c2) {
return c1 - c2;
}
k++;
}
return len1 - len2;
}
关键代码：
int k = 0;
while (k < lim) {
char c1 = v1[k];
char c2 = v2[k];
if (c1 != c2) {
return c1 - c2;
}
k++;
}
再关键代码：
char c1 = v1[k];
char c2 = v2[k];
看到这里，基本上就明白了，c1,c2取出来的是字符串对应的ASCII码值:65,66.
string 的value就是存ASCII码字符数组：
/** The value is used for character storage. */
private final char value[];
所以真相大白了，跟SortMap一毛钱关系都没有。。。。。
~~
以下是我的调试：
![paste image][image-1]
那SortMap是怎么回事？
我在TreeMap源码里找到这个构造方法：
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
也就是说，想要用SortedMap来排序，必须要传进来一个SortedMap实现才行，奶奶的胸，网文害人不浅。
从TreeMap的源码上看，它是NavigableMap的实现，而NavigableMap又是SortedMap的子类，TreeMap也算是SortedMap实现。
解惑二：也可以通过构造时传入的比较器（Comparator）
这个比较好理解，刚刚看put源码时，就看到有comparator属性判断，因为我没有传这个比较器，所以一直走else;
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
解惑三：TreeMap底层通过红黑树（Red-Black tree）实现
先不说这句说的对错，先来说说什么是Red-Black tree?
什么是Red-Black tree
看TreeMap的类注释，第一句话就是：
A Red-Black tree based {@link NavigableMap} implementation.
红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍。具体来说，红黑树是满足如下条件的二叉查找树（binary search tree）：
- 每个节点要么是红色，要么是黑色。
- 根节点必须是黑色
- 红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
- 对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。
在树的结构发生改变时（插入或者删除操作），往往会破坏上述条件3或条件4，需要通过调整使得查找树重新满足红黑树的条件。
红黑树的定义我现在看起来一头蒙逼，我觉得我还得先了解下什么是二叉树。
什么是二叉树
- 二叉树的定义：
二叉树是树形结构的一个重要类型。
许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。
二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。
这个定义是递归的。由于左、右子树也是二叉树， 因此子树也可为空树。下图中展现了五种不同基本形态的二叉树。
如图：
![paste image][image-2]
其中 (a) 为空树， (b) 为仅有一个结点的二叉树， (c) 是仅有左子树而右子树为空的二叉树， (d) 是仅有右子树而左子树为空的二叉树， (e) 是左、右子树均非空的二叉树。这里应特别注意的是，二叉树的左子树和右子树是严格区分并且不能随意颠倒的，图 (c) 与图 (d) 就是两棵不同的二叉树。
其实二叉树嘛，就是所有的数据结构都是长的像两棵树。
二叉树的应用与实现
二叉树的遍历
对于二叉树来讲最主要、最基本的运算是遍历。
遍历二叉树 是指以一定的次序访问二叉树中的每个结点。所谓 访问结点 是指对结点进行各种操作的简称。例如，查询结点数据域的内容，或输出它的值，或找出结点位置，或是执行对结点的其他操作。遍历二叉树的过程实质是把二叉树的结点进行线性排列的过程。假设遍历二叉树时访问结点的操作就是输出结点数据域的值，那么遍历的结果得到一个线性序列。
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：
（1）访问结点本身(N)，
（2）遍历该结点的左子树(L)，
（3）遍历该结点的右子树(R)。
以上三种操作有六种执行次序：
NLR、LNR、LRN、NRL、RNL、RLN。
注意：
前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。
由于被访问的结点必是某子树的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。二叉树的java实现
首先创建一棵二叉树如下图，然后对这颗二叉树进行遍历操作（遍历操作的实现分为递归实现和非递归实现），同时还提供一些方法如获取双亲结点、获取左孩子、右孩子等。
![paste image][image-3]
- 排序
给一组数字用二叉树的方式进行排序，eg : int a [ ] = {3,1,2,5,0,7,9,8} ，用这个数组中的数字建立二叉排序树，注意这里的二叉排序树是随便的，没有特殊的要求(比如建立高度最小的二叉排序树)，可知二叉排序树是不唯一的。常规方法采用递归，首先先以3这个数字为根节点，仅接着采用递归,大于根节点的在右子树中，小于等于根节点的在左子树中。二叉排序树结构图：
![paste image][image-4]![paste image]
以下是用二叉树结构来实现的排序与几种遍历方式：
package com.wolf.model.algorithm;
import java.util.*;
/**
* Created by sam on 2017/7/3.
*/
public class BinaryTree <T extends Comparable>{
private TreeNode root;
public TreeNode getRoot() {
return root;
}
public void setRoot(TreeNode root) {
this.root = root;
}
private class TreeNode{
private Object data;
private TreeNode parent;
private TreeNode left;
private TreeNode right;
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
public TreeNode(Object data, TreeNode parent, TreeNode left, TreeNode right) {
this.data = data;
this.parent = parent;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return "TreeNode{" +
"data=" + data+'}';
}
}
public void add(T ele){
if(root == null){
root = new TreeNode(ele, null, null, null);
}
else{
TreeNode current = root;
TreeNode parent = null;
int cmp;
//搜索合适的叶子节点，以该叶子节点为父节点添加新节点
do{
parent = current;
cmp = ele.compareTo(current.data);
//如果新节点的值大于当前节点的值
if(cmp > 0){
//以当前节点的右子节点作为当前节点
current = current.right;
}else{
current = current.left;
}
}while(current != null);
//创建新节点
TreeNode newNode = new TreeNode(ele, parent, null, null);
//如果新节点的值大于父节点的值
if(cmp > 0){
parent.right = newNode;
}else{
parent.left = newNode;
}
}
}
public void visted(TreeNode subTree) {
System.out.println("--name:" + subTree.data);
}
//中序遍历的非递归实现:LNR,从最左边的left按顺序排列
public void nonRecInOrder(TreeNode p) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = p;
while (node != null || stack.size() > 0) {
//存在左子树，把所有左子树添加到栈
while (node != null) {
stack.push(node);
node = node.left;
}
//栈非空
if (stack.size() > 0) {
node = stack.pop();
visted(node);
node = node.right;
}
}
}
//前序遍历递归实现：NLR
public List<TreeNode> preOrder(TreeNode subTree) {
List<TreeNode> list = new ArrayList<TreeNode>();
if (subTree != null) {
list.add(subTree);
if (subTree.left != null)
list.addAll(preOrder(subTree.left));
if (subTree.right != null)
list.addAll(preOrder(subTree.right));
}
return list;
}
//中序遍历的递归实现:LNR,从最左边的left按顺序排列,就是从小到大排序
public List<TreeNode> midNodeInOrder(TreeNode node){
List<TreeNode> list = new ArrayList<TreeNode>();
//保存所有左子树
if (node !=null && node.left !=null)
list.addAll(midNodeInOrder(node.left));
//保存根节点
list.add(node);
//保存所有右子树
if(node.right != null)
list.addAll(midNodeInOrder(node.right));
return list;
}
//中序遍历实现：RNL,从最右边的right按从大到小排序
public List<TreeNode> mid2NodeInOrder(TreeNode node){
List<TreeNode> list = new ArrayList<TreeNode>();
Stack<TreeNode> stack = new Stack<TreeNode>();
//保存所有右子树到栈
if (node.right !=null){
stack.push(node.right);
}
if (node != null){
stack.push(node);
if (node.right != null)
list.addAll(mid2NodeInOrder(node.right));
}
//将栈顶的元素pop出来，也就是最后添加进来的数，应该是离root最远的右边的右子树，第二次调用就依次类推
list.add(stack.pop());
if (node.left != null){
stack.push(node.left);
list.addAll(mid2NodeInOrder(node.left));
}
return list;
}
//根据给定的值搜索节点
public TreeNode searchNode(T ele)
{
//从根节点开始搜索
TreeNode p = root;
while (p != null)
{
int cmp = ele.compareTo(p.data);
//如果搜索的值小于当前p节点的值
if (cmp < 0)
{
//向左子树搜索
p = p.left;
}
//如果搜索的值大于当前p节点的值
else if (cmp > 0)
{
//向右子树搜索
p = p.right;
}
else
{
return p;
}
}
return null;
}
//广度优先遍历
public List<TreeNode> deepFirst(TreeNode root) {
List<TreeNode> list = new ArrayList<TreeNode>();
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
list.add(queue.peek());
TreeNode twoLinkNode = queue.poll();
if (twoLinkNode.left != null) {
queue.add(twoLinkNode.left);
}
if (twoLinkNode.right != null) {
queue.add(twoLinkNode.right);
}
}
return list;
}
}
二叉查找树的删除操作
删除操作的步骤如下：
- 查找到要删除的节点。
- 如果待删除的节点是叶子节点，则直接删除。
- 如果待删除的节点不是叶子节点，则先找到待删除节点的中序遍历的后继节点，用该后继节点的值替换待删除的节点的值，然后删除后继节点。
![paste image][image-5]
寻找节点后继
对于一棵二叉查找树，给定节点t，其后继（树中比大于t的最小的那个元素）可以通过如下方式找到：
t的右子树不空，则t的后继是其右子树中最小的那个元素。
t的右孩子为空，则t的后继是其第一个向左走的祖先。
后继节点在红黑树的删除操作中将会用到。
![paste image][image-6]
具体测试代码可以在我的github上下载：
[测试代码][1]
clone或下载分支： java8build
好了，已经明白了二叉树是个什么玩意，那现在再看红黑树，这红黑树不就是二叉树的变种嘛！也是树。
为什么会有红黑树
二叉树存在的主要问题是，数在插入的时候会导致树倾斜，不同的插入顺序会导致树的高度不一样，而树的高度直接的影响了树的查找效率。理想的高度是logN，最坏的情况是所有的节点都在一条斜线上，这样的树的高度为N。
在理想的情况下，二叉查找树增删查改的时间复杂度为O(logN)（其中N为节点数），最坏的情况下为O(N)。当它的高度为logN+1时，我们就说二叉查找树是平衡的。
![paste image][image-7]
RBTree的定义
- 任何一个节点都有颜色，黑色或者红色
- 根节点是黑色的
- 父子节点之间不能出现两个连续的红节点
- 任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数必须相等
- 空节点被认为是黑色的
数据结构表示如下：
class RBTreeNode<T>{
public T value;
public Node<T> parent;
public boolean isRed;
public Node<T> left;
public Node<T> right;
}
RBTree在理论上还是一棵二叉查找树，但是它在对BST的插入和删除操作时会维持树的平衡，即保证树的高度在[logN,logN+1]（理论上，极端的情况下可以出现RBTree的高度达到2*logN，但实际上很难遇到）。这样RBTree的查找时间复杂度始终保持在O(logN)从而接近于理想的BST。RBTree的删除和插入操作的时间复杂度也是O(logN)。RBTree的查找操作就是BST的查找操作。
好了，理论上，红黑树的数据结构比二叉查找树就多了一个字段：isRed.
由于插入和删除操作会打乱红黑树的结构，使其不遵循红黑树的定义结构，那么就需要通过调整的方式去使结构重新符合红黑树的数据结构。
红黑树的代码实现
在前端就说了，TreeMap是红黑树的典型实现类。
put(key,value):
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
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();
@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;
}
源码分析：
二叉树结构遵循
因为红黑树是二叉树的变种，所以它首先要遵循二叉树的定义：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);
比父节点小的，放到左边，比它大的放右边，如果相等就直接给父节点赋值。
作添加操作后，需要修复红黑树的结构使其能满足红黑树结构
修复红黑树的数据结构：
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(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 == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
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.color = BLACK;
}
其中作的调整操作是：rotateLeft(x)和rotateRight(x).
[1]: https://github.com/huguiqi/WolfSpringMVC.git
[image-1]: http://clockcoder.com/images/1498833284942mbt7rqrw.png?imageslim
[image-2]: http://clockcoder.com/images/1498964122299rcwlujax.png?imageslim
[image-3]: http://clockcoder.com/images/1498964788182lorucwvj.png?imageslim
[image-4]: http://clockcoder.com/images/1498965196156il66exh3.png?imageslim
[image-5]: http://clockcoder.com/images/1499227809263er3121jg.png?imageslim
[image-6]: http://clockcoder.com/images/14992264489782hiym621.png?imageslim
[image-7]: http://clockcoder.com/images/1499224611099quxx72o0.png?imageslim
