「AVL 旋转」存在的目的是什么？尽管有 logN 的时间复杂度，树的 hierarchy 岂不全乱了？

AVL旋转是AVL树的旋转，AVL树存在的意义是二分法查找，二分法查找的要求是能找到要找的结点，而树的层级结构只要能满足这一点就可以。

假设一颗不平衡的二叉树，从根节点开始查找，可以找到某个叶子结点，中间经过四次分叉；经过AVL旋转，再次从树的根节点开始查找（根节点也许变了），中间可能只要两次分叉，但是仍旧会找到要找的叶子结点。树的拓扑结构的确改变了，但是每个结点与其他结点之间的关系，也就是局部逻辑，并没有改变。

原发布于 https://www.zhihu.com/question/20390173/answer/14990228