自己保持平衡的树

偏向一边就变慢

前面我们学过，树靠在枝杈间
一半一半地缩小范围来快速查找。
从上往下每走一步，
要看的范围就少一半。
可要是把值从小到大
只按顺序加入会怎样呢？
新值总是贴在一边，
枝杈不分叉，
拉成一条长长的直线。

把值一个个加进去。它只往一边变长，几乎成一条线，查找的步数猛地增多。

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

让两边深度差不多

就算是同样的那些值，
形状摆得好，情况就不一样。
不往一边堆，
而是把中间的值放在上面，
小的值放左边，大的值放右边，
把枝杈往两边分。
那么从上往下每走一步，
要看的范围就真的少一半。
这样两边深度差不多的树，
就叫平衡树。

都是同样的值。点一下偏斜的树和平衡的树，比一比深度。哪个更快到底?

数目一样，
平衡树却浅得多。
浅就是到底的步数少，
也就是查找快。
可就算一开始平衡得好，
值不停地加和删，
一边就会慢慢变重。
总不能每次都手动重搭，
所以该让树自己来修，对吧?

用旋转重新调平

一边变重时，
树就把节点的位置稍微换一换。
把重的那边的节点往上提，
把原来在上面的节点往下移一格。
那么堆在一边的重量
就分到两边，重新平衡。
这样重新安排位置，
就叫旋转。
顺序规则照旧守住，
只把形状摆正。

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

只一次旋转，
歪斜的树就摆正了。
只挪了几个节点的位置，
两边的深度就又差不多了。
要紧的是值的顺序规则
一点都没乱。
左边还是小，右边还是大。
只换了形状，约定照旧，
查找一样好用。

再多也保证深度

每次加和删都用旋转
守住平衡，有个好处。
数据再多，
树的深度也只长得很慢。
数目翻一倍，
深度也只多一级。
这样慢慢长，就叫 log。
所以无论是一百个值还是一百万个，
它总能保证在几步之内找到。

把数据量调大。偏斜的树深度跟着一路涨，可平衡树只一级一级慢慢变深。

偏斜的树，数据越多，
深度也跟着一个劲儿地涨。
可平衡树，
哪怕数据翻了好几倍，
深度还几乎照旧。
正是这个差别，
让平衡树叫人放心。
因为不管来多少数据，
都能信它快速找到。

来理一理

归成一句话，是这样。
树要是只往一边长，
就几乎成一条线，变慢。
平衡树让两边深度差不多。
加和删时一边变重了，
就用旋转重新安排位置。
多亏这样，数据再多，
深度也长得很慢（log），
总能保证在几步之内找到。

依次点要点回顾一下。(偏了就慢 → 让两边匀 → 用旋转重排 → 用 log 保证)

现在你知道树
怎么自己守住平衡了。
这就是它在加和删之间
也不丢掉快速查找的诀窍。
我们只管把值交给它，
树就自己把形状整好。
麻烦的旋转交给树，
我们只享受快速查找就好。