AVL

左子树和右子树高度的差的绝对值小于2，可以证明这个二叉树高度肯定是o(lgn)。
主要的树就两个操作，插入和删除操作。插入和删除后可能回出现一个问题，树不再平衡，因此我们需要通过操作进行重平衡。
诶，这怎么写啊。这个没有图不行啊。要不就不写了，反正旋转操作网上很多的，搜一下就行。
假设结点c左子树x，右子树y，结点v左子树c，右子树z。探究一下对v右旋后树高的变化。此时c的右子树变为v，v的左子树成了y。可以看出y高度没有变化，而相对于v的父节点来说，到x的路径减1，到z的路径加1，x与z的高度差减少了2。
修改树时又有左左，左右，右左，右右四种情况。但是要注意的是，插入操作后，不断向上更改结点高度并重平衡，但是只要改正一次就必恢复平衡，整个操作O(1)。但是删除操作却会将错误向上蔓延至整棵树，整个操作是O(lgn)。这种拓扑变化是很难容忍的。
注意操作的核心就是保持中序遍历顺序不变。所以在清华邓老师的课中提到了34重构。就像拼魔方，以前是转转转转到合适的地方，现在直接把魔方拆了安到对的地方。这种写法更加简单与易于维护。
整个BST的操作的一条核心准则就是，维持中序不变！从这个角度去看旋转操作就很自然了。
AVL还有很多值得研究的地方，等我混着伸展树与红黑树一起写吧。以前对树这里一直学的不够透，现在明白很多了。
冲！