什么是平衡树

偏向一边就会变慢

在树里，每往下走一层，要查的范围就缩小一半。可要是只按从小到大的顺序放值，会怎么样？
新放的值总比之前放的所有值都大，所以总是接在最右边。于是枝不再分叉，拉成长长的一条线。名字还叫树，形状却和前面看过的一排列表一样。

依次放进值。树只往一边变长，几乎成了一条线，找的步数一下子变多了。

拉成一条线的树，实际上几乎没有枝。从上往下走，范围不是每次减半，而是每次只少一个。
所以要找最末端的值，就得从头到尾一个个数。为了快速查找而做的树，反倒变慢了。这样一来，用树就没有意义了。

让两边深度差不多

同样的值，形状整理得好，情况就完全不同。不只往一边堆，而是把中间的值放在上面，小的值往左、大的值往右分出枝去。
这样一来，每往下走一层，要查的范围才真正减半。像这样两边深度保持差不多的树，叫作平衡树。

这是用同样的值做成的两棵树。点一下偏斜的树和平衡的树，比比深度。哪一棵更快到底？

个数一样，平衡的树却浅得多。浅，意味着到底的步数少，也就是查找快。
可是，就算一开始很平衡，值一再放进、删除，一边也可能慢慢变重。总不能每次都靠人手重新搭，所以要让树自己来修。

用旋转重新找回平衡

一边变重时，树会把几个节点的位置稍微换一换：把重的那一边的节点往上提，把原来在上面的节点往下放一层。
这样，挤在一边的重量就分到两边，树又平衡了。像这样重新安排位置，叫作旋转。“左边小、右边大”的顺序规则照样遵守，只把形状扶正。

这棵树右边重。点一下“旋转”。中间的节点升到上面，两边就平衡了。

旋转一次，歪歪斜斜的树就变端正了。只挪了几个节点的位置，两边的深度又差不多了。
重要的是，值的顺序规则一点也没乱：左边照样小，右边照样大。只是形状变了，约定没变，所以查找照样顺利。用这种办法保持平衡的树有好几种，各自判断平衡的规则稍有不同。

数据再多，深度也有保证

每次放进、删除时都用旋转保持平衡，有个好处：数据再怎么增加，树的深度都只会慢慢增长。
个数翻一倍，深度也只多一层。就像上一课看到的，这样缓慢的增长叫作对数增长。所以不管有一百个值还是一百万个，总能在几步之内找到。

增加数据量看看。偏斜的树，深度跟着数据量一路往上涨；平衡的树，却只一层层慢慢变深。

偏斜的树，数据越多，深度也跟着一路上涨。平衡的树，数据翻了好几倍，深度却几乎没变。
正是这个差别，让平衡树靠得住：不管进来多少数据，都可以放心它能快速找到。

小结

用一句话概括：树只往一边长，就几乎成了一条线，会变慢。平衡树让两边深度保持差不多。
放进、删除时一边变重，就用旋转重新安排位置。多亏这样，数据再多，深度也只会慢慢（log）增长，总能在几步之内找到。

依次点要点回顾一下。（偏向一边就慢 → 让两边差不多 → 用旋转重排 → 用 log 保证）

现在你知道树是怎样自己保持平衡的了。这就是在放进、删除的过程中也不失去快速查找的秘诀。我们只要把值交给它，旋转由树自己完成。
数据库的索引也是用这样的平衡树做成的，只不过用的是又宽又浅的树：一个节点里放好几个值，长出非常多的枝。下一课来看看这种索引在数据库里实际上怎么用。