avl树/红黑树的旋转为什么不会改变顺序?

一、avl树/红黑树的旋转为什么不会改变顺序

因为右旋转为左旋转的镜像，而双旋转可以分解为两个单旋转，因此可以推出四种旋转都不会改变AVL树的平衡特性，不会改变顺序。AVL树是以二分搜索树（BST）为底层数据结构而实现的，其特性是需要维护AVL的平衡因子。

AVL树和红黑树的比较

经常在网上看到关于AVL树和红黑树的讨论，讨论的双方往往各执一词，都在试图证明到底哪个更加优越。并且似乎都可以给出充足的理论依据，但最后的结果往往是谁也不能说服谁。我认为问题的根源在于没有对齐讨论对象，当我们在比较AVL树和红黑树时，首先需要明确的是：我们到底在比较什么？

空间开销。AVL树的每个节点需要额外两比特来表示左斜、平衡、右斜三种状态，而红黑树的每个节点只需要额外一比特来表示红、黑两种颜色，看起来是红黑树占据了优势。但是结构体空间的分配不可能是以比特为单位来进行的，因此在以字节为单位分配内存的情况下红黑树的优势便没有了。从另一个角度来讲，不管是两比特还是一比特，都可以把它编码到某个指针域的最低两位，理由是内存对齐使得指针域的最低两位必然为零。在这种骚操作的情况下，AVL树和红黑树的空间开销也是一模一样的。顺带提一点不太相关的，父指针域要不要都可以，区别是不要父指针域可以使空间开销更小，然而代价是循环的时候需要维护一个栈结构，因此主流的实现是牺牲这一点微弱的空间开销以获取更快的运行速度。实现难度。有一种观点认为红黑树插入和删除后的调整过程需要考虑太多的场景了，而AVL树只需要比较左右子树的高度决定如何旋转即可，因此AVL树的实现难度要低于红黑树。事实上我以前学习的时候在网上看过不下十份的AVL树代码，几乎没有正确的(有的版本不保存平衡因子而保存高度，有的版本甚至每一次都用递归来求高度)。这两种树我都亲自实现过，就以自己的经验来看，在考虑各种Corner case、常数时间返回最值元素、指针向前向后迭代、对重复元素进行支持等等条件的限制下，要无误且优雅地实现这两者之间的任意一个都是很困难的。鉴于实现难度是个比较主观的东西，这里就不做过多的评价了。时间开销。也是大家通常说的时间复杂度，这个恐怕才是争议的核心，后面所有的篇幅都将针对它来讨论。

一般说来，不管是AVL树还是红黑树，不管是插入还是删除(我们不专门另讨论查找，它包含在了插入和删除中)，操作的开销大致都可以分解成如下两部分：

查找开销。插入前总是需要查找到具体的位置才行，需要不断向下查找直至外节点。删除前一般也要查找到对应元素，虽然这不是必要的，但是将查找和删除合在一起讨论显得更加方便一些。调整开销。插入和删除都有可能打破原来的平衡约束，因此需要一层一层地向上调整。每一次的调整开销里面具体又会包含：a. 变色开销，即修改节点的颜色(或者平衡因子)带来的开销；b. 旋转开销，即旋转操作中修改各种指针指向带来的开销。这两种开销的系数是不一样的，在需要精确讨论的时候应该严格区分而不能把它们混为一谈。

延伸阅读：

二、红黑树特征

红黑树听名字就知道，里面涉及到两种颜色：红色和黑色。

（1）每个节点只有两种颜色：红色和黑色。

（2）根节点是黑色的。

（3）每个叶子节点（NIL）都是黑色的空节点。

（4）从根节点到叶子节点，不会出现两个连续的红色节点。

（5）从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。

这五条就是红黑树的特征，你每看一个特征较好重新看一遍图，这样可以加深理解。这五条特征看起来真的很复杂，不过正是由于这些复杂的特征才保证了红黑树的良好特性。