扁担宽 板凳长
扁担想绑在板凳上
板凳不让扁担绑在板凳上
扁担偏要绑在板凳上
板凳偏偏不让扁担绑在那板凳上
到底扁担宽 还是板凳长
……
BST矮 BST高
BST有AVL 也有RBTree
各种形状的小树，各种性格的大树
到底小树好 还是大树好
……
暂时编到这里……
不知道为什么，各种树在大脑里各种浮现，想起了上面的歌词。
世间物种亿万万，人都个性习惯差异万万千，何况DataStructure世界里的这些树呢？
写在前面
"道生一，一生二，二生三，三生万物。"
任何事物都不是凭空产生，也不会兀自消失。
它们的出现都有各自的道理，生存也遵循着一定的法则，消失也有各自的缘由。
天空之浩瀚，江海之辽阔，处于其中的世间万物都在用自己的方式达到各自的平衡。
DataStructure里的各种树看得有点玄之又玄，如果只是记一些算法觉得并不能完全代表这些树结构存在的意义。
想写一些对这些树结构的理解和感受，而不是简单地重复概念，先不涉及算法代码相关，只是偶尔有了一些体会，想到哪写到哪吧。
如能让你产生一点共鸣，甚好；如不能，就当作者在自言自语。
关于树
大自然的树种有万千种，各有各的模样和特性，为了生存，各显神通。二进制世界里的“树”也是对大自然的一种映射吧。
事物并不是非黑即白。
树形结构的出现，是由链表进化而来，是从线性到非线性结构的发展。
而链表，又何尝不是一种特殊形状的树呢？
看过了好多篇关于树的技术文章，特别是红黑树的，一上来甩出来五条性质，balabala
RBTree性质.png
各种概念，各种图，如何出现，如何变色，又如何旋转，让人看得也天旋地转，看完还一头雾水。
忽然有一天觉得，红黑树，是道法自然的一种体现。
红与黑，不在意颜色，亦可看成黑白两道。
它的定义：一种自平衡二叉查找树。
自平衡，如何自平衡？平衡自在内心。
事物的出现自有它的道理，那么红黑树是怎样出现的？
它出现过程大致是：
二叉树 -> 二叉查找树(BST) -> AVL树
....... ....... ...... .... .... ..... |
（B树 -> 2-3树）-> 红黑树(RB Tree)
BST
Binary Search Tree
BST先不说来龙去脉了，二叉查找树的出现自然是为了查找方便了。
如下，就是一棵BST了。
BST.png
但是BST在增删改查的过程中，也可能变成下面这样：
最坏运行情况O(N).png
它也符合BST的性质，但是看起来就极不平衡，一碰就倒，概况为“失衡”。
AVL
Self-Balancing Binary Search Tree / Height-Balanced Binary Search Tree
AVL树是最先发明的自平衡二叉搜索树（BBST）
从定义名字可以看出来，AVL是为了平衡而来。
"AVL"名字来源：其发明者前苏联学者 G.M. Adelson-Velsky 和 E.M. Landis 名字而命名。
英文定义如下：
Definition:
A tree is perfectly balanced if it is empty or the number of nodes in each subtree differ by no more than 1.
好一个“perfectly”~ But who is perfect?
它是一种高度平衡树，也是一种二叉搜索树，它的出现是为了解决二叉搜索树退化成链表的问题。
来个图看看，符合的性质：
- 每棵子树中的左子树和右子树的深度差不能超过 1；
- 二叉树中每棵子树都要求是平衡二叉树。
AVL Tree.png
AVL追求极致的平衡，而极致，也会带来弊端。
要追求什么，必然要通过另一些什么来换取。
而时刻要保持的“极致”，必然时刻要不松懈地维护。这其实挺累的。
它只是想要追求平衡的完美吧。
但事事无绝对。追求极致，就可能出现弊端。或者说，极致点，也是一个弱点。
- 优点：
查找元素时，速度很快。 - 缺点：
在添加或删除元素时，由于“追求极致的平衡”，通过不断地循环来达到自平衡，因而增加了时间复杂度。
AVL旋转
AVL左旋
AVL左旋.png
2-3树
在说红黑树之前，应该看一下2-3树，其实可以更好地认识红黑树。
（待补充）
红黑树（RB Tree）
既生瑜，何生亮？
还是来看看英文的定义~ 有时候英文的更好理解。
Definition:
Red-Black Trees are binary search trees that are named after the way the nodes are coloured.
Red-Black Tree is a self-balancing Binary Search Tree (BST) where every node follows following rules.
RedBlackTree
- **Every node has a color either red or black.
- **Root of tree is always black.
- **There are no two adjacent red nodes (A red node cannot have a red parent or red child).
- **Every path from a node (including root) to any of its descendant NULL node has the same number of black nodes.
看这个结构图和几条balabala的性质，是不是觉得很晕？很晕就对了~
先来了解个大概~
RB Tree也是平衡二叉搜索树，和AVL一样，都是Self-Balanced。
AVL追求极致的平衡，而红黑树的出现，大概就是为了弥补追求极致所造成的失衡，它只做到部分的平衡，是一种折中的表现。
RB Tree放弃的部分平衡，是为了换取增删操作时的效率。
牺牲了高度的绝对平衡，换来时间的优化。这比交换值不值？
当然值。
AVL为了平衡会要经过好多次旋转，旋转旋转……
白雪，夏夜，我不停歇……
而RB Tree的结构设计，使得任何不平衡都会在三次旋转之内解决。（很厉害！）
有得有失~ 有失有得~
得失，也是一种自平衡。
（它们如何旋转变化待补充~）
RB Tree的旋转
还是动图好看~
左旋
将E的右子树S绕E逆时针旋转，使得E的右子树S成为E的父亲，同时修改相关节点的引用。
旋转之后，二叉查找树的属性仍然满足。
左旋.gif
/** From CLR */
private void rotateLeft(TreeMapEntry<K,V> p) {
if (p != null) {
TreeMapEntry<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;
}
}
右旋
将S的左子树绕S顺时针旋转，使得S的左子树成为S的父亲，同时修改相关节点的引用。
旋转之后，二叉查找树的属性仍然满足。
右旋.gif
/** From CLR */
private void rotateRight(TreeMapEntry<K,V> p) {
if (p != null) {
TreeMapEntry<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;
}
}
AVL树和RB Tree对比
就AVL和RB Tree两种结构相比较，
AVL像一位特长生，显著的特长就是它的“绝对平衡”，锋芒毕露。
RB Tree像一位比较全面发展的学生，没有绝对的特长，但各方面表现都比较好，深谙折中之道。
不能说谁一定优于谁，“绝对”与“非绝对”也是相对，它们各自有自己的平衡，并且有自己的擅长点。
BST树的比较.png
写在后面
内容尚需修改与完善，如有表述不准确之处，望不吝指出，谢谢~
网友评论