Java集合（1）一 集合框架
Java集合（2）一 ArrayList 与 LinkList
Java集合（3）一 红黑树、TreeMap与TreeSet（上）
Java集合（4）一 红黑树、TreeMap与TreeSet（下）
Java集合（5）一 HashMap与HashSet
在Java集合（3）一 红黑树、TreeMap与TreeSet（上）中从二叉树的遍历、添加和删除引申到了红黑树的遍历、添加和删除。对二叉树结构有了一定的了解，在这篇文章中将会对红黑树进行详细的说明。
红黑树二叉树在理想情况下时间复杂度是O(logn)，最坏情况下当插入的数据由小到大或者由大到小排列的时候，二叉树就变成了一个链表，而我们知道链表检索的时间复杂度是O(n)，效率非常差，所以出现了AVL树和红黑树来改变这种状况。同时由于AVL树的极端平衡特性，导致添加和删除数据后需要过多的旋转操作来保证AVL树平衡的特征，所以TreeMap中会使用红黑树来存储数据。
最好情况下的二叉树：
最差情况下的二叉树：
当AVL树在添加或者删除节点时出现不平衡后通过什么操作来保证树的平衡性呢？这种操作就叫做书旋转。红黑树也是如此，不过红黑树更复杂，这点我们后面再说，先来看看AVL树的旋转操作。
树旋转操作是由于二叉树在添加节点时为了避免出现平衡失效的情况而做的一种操作，操作的基本原则是操作后不影响二叉树中序遍历的结果。
这里我们用AVL树来说明这个问题。AVL树是一种高度平衡的二叉树，他的任何两个节点的子树的高度最大差别为1，这样他的查找、插入和删除的时间复杂度都是O(logn)，当出现不平衡情况的时候，就需要执行树旋转。
树的旋转操作分为两种，左旋转和右旋转，这两种旋转是相对的。通过右旋或者左旋操作我们可以使一棵树继续保持平衡状态，并不会改变中序遍历的结果，但同时也要付出相应的代价。
//右旋 private void rotateRight(Entry<K,V> p) { if (p != null) { Entry<K,V> l = p.left; p.left = l.right; if (l.right != null) l.right.parent = p; l.parent = p.parent; if (p.parent == null) root = l; else if (p.parent.right == p) p.parent.right = l; else p.parent.left = l; l.right = p; p.parent = l; } } //左旋 private void rotateLeft(Entry<K,V> p) { if (p != null) { Entry<K,V> r = p.right; p.right = r.left; if (r.left != null) r.left.parent = p; r.parent = p.parent; if (p.parent == null) root = r; else if (p.parent.left == p) p.parent.left = r; else p.parent.right = r; r.left = p; p.parent = r; } }