最近看了几篇关于二叉搜索树的文字，其中就包括了几个简单的平衡树的内容，包括avltree和rbtree。很多文章和资料都说avltree综合性能没有rbtree高，但是有些说法是没什么依据的，可能是被早前的比较差的avltree实现给误导了。

在一些好的avltree的实现和rbtree做性能对比的时候，avltree的性能并比不rbtree差。

就从下面几个方面来分析下。

查询性能

因为avltree的平衡性要要求严格，所以在节点相同的情况下，高度必定不会比rbtree高，所以在查询性能上，avltree会更好，虽然都是O(logN)

插入性能

avltree

插入节点之前，先找到需要插入的位置，找这个位置根据二叉搜索树的逻辑很容易实现。

之后就是新建一个节点连上找到的这个节点即可，连上后就需要检查树是否平衡了并且向根部回溯的检查：

  1. 如果父节点的高度没有变化，那么可以直接停止回溯，因为插入节点没有破坏平衡
  2. 如果不平衡，就需要旋转操作，最多需要两步旋转，旋转后树高会-1，因为加入节点导致树高+1被抵消了，所以旋转后树一定是平衡的，可以停止回溯。所以回溯也是可以在常数时间内完成，并不需要很高的代价。
  3. 其他的情况只要重新计算树高即可

rbtree

红黑树的插入可以简单分成两种方式：

  1. 自底向上(Bottom-Top): 简单说就是先找到插入位置，之后添加节点，之后回溯调整，过程略复杂，需要讨论的情况很多，这里就不讲了
  2. 自顶向下(Top-Down): 从根节点开始通过旋转和颜色变化，保证插入的节点位置是黑色的，插入后不需要回溯调整颜色，所以，可以省略指向父节点指针

自顶向下

  1. 从根节点开始遍历
  2. 当前节点X为黑色，如果左右两个子节点L, R都是红色，这时候需要根据X的父节点P的颜色分别处理
  3. 如果P也是黑色的，直接变颜色即可，X变红色，L，R变为黑色
  4. 如果P是红色的，这时候p的父节点G一定是黑色的（因为两个红节点不能相连，P兄弟节点U一定是黑色的，因为如果U是红色的，那上一步一定会调整）。这时候都要根据X位置使用单旋转还是双旋转
  5. 如果X，P,G三个节点在一条线，那么只需要单旋转即可，再修改下颜色
1
2
3
4
5
6
7
8
9
10
11
            |                                  |
            Gb                                 Pb
            / \                               /   \
           Pr  Ub         简单右旋            Xr    Gr
          /  \            ====>             / \    / \
         Xb   Sb                           Yb  Zb Sb  Ub
        / \
       Yr  Zr

# r - 红色
# b - 黑色
  1. 如果X，P,G不在一条线，那就需要做两次旋转，再修改节点颜色

小结

通过两中数据结构的插入过程来看，在数量级上是没有区别的，唯一的差别是在avltree更平衡，所以他的树高会更低，尤其是在节点数量很多的时候，高度会更小，所以查找时间要小一点，插入操作会更有一点优势，尤其是rbtree在使用自顶向下的插入过程，对比更加明显

删除性能

avltree

avltree的删除要比插入麻烦点，首先找到要删除的节点

  1. 如果是叶子节点，直接删除
  2. 如果有一个子节点，用子节点替代删除节点连上父节点即可
  3. 如果有两个子节点，则需要在两个子节点中的比较高的子树中找一个值替代。如果左树高则找最大值，如果是右树高则找最小值。找到后交换删除节点和这个节点交换内容，之后按照1步骤删除即可

删除节点后需要向根节点回溯，判断平衡和节点高度，直到树高和平衡性没有变化的时候停止即可。

rbtree

红黑树的删除也是比较麻烦的，首先在删除节点后需要判断是否破坏平衡。如果删除的是一个红色叶子节点，那么直接删除即可。如果一个黑节点，那就会破坏平衡，需要回溯调整。所以目标就是保证删除的节点X一定是一个红色节点。过程如下：

  1. 如果根节点两个儿子都是黑色的，将根节点染成红色，X移动到子节点
  2. 如果根节点两个儿子有一个红色的，X移到根节点

甚至在因为树高比较低，查询性能更好。删除的性能因为要旋转和往根部回溯平衡高度而有点影响，但是rbtree同样需要回溯修改节点颜色，所以并没什么区别。