BSTree
BST存在的主要问题是，数在插入的时候会导致树倾斜，不同的插入顺序会导致树的高度不一样，而树的高度直接的影响了树的查找效率。理想的高度是logN，最坏的情况是所有的节点都在一条斜线上，这样的树的高度为N。
(1) 查找代价： 任何一个数据的查找过程都需要从根结点出发，沿某一个路径朝叶子结点前进。因此查找中数据比较次数与树的形态密切相关。
当树中每个结点左右子树高度大致相同时，树高为logN。则平均查找长度与logN成正比，查找的平均时间复杂度在O(logN)数量级上。
当先后插入的关键字有序时，BST退化成单支树结构。此时树高n。平均查找长度为(n+1)/2，查找的平均时间复杂度在O(N)数量级上。
(2) 插入代价： 新结点插入到树的叶子上，完全不需要改变树中原有结点的组织结构。插入一个结点的代价与查找一个不存在的数据的代价完全相同。
(3) 删除代价： 当删除一个结点P，首先需要定位到这个结点P，这个过程需要一个查找的代价。然后稍微改变一下树的形态。如果被删除结点的左、右子树只有一个存在，则改变形态的代价仅为O(1)。如果被删除结点的左、右子树均存在，只需要将结点与互换，在改变一些左右子树即可。因此删除操作的时间复杂度最大不会超过O(N)
AVLTree
基于BSTree存在的问题，一种新的树——平衡二叉查找树（AVLTree）产生了，平衡树在插入和删除的时候，会通过旋转操作将高度保持在logN。
(1) 查找代价：查找的时间复杂度维持在O(logN)，不会出现最差情况
(2) 插入代价：AVL树在执行每个插入操作时最多需要2次旋转，其时间复杂度在O(logN)左右。
(3) 删除代价：AVL删除结点的算法可以参见BST的删除结点，但是删除之后必须检查从删除结点开始到根结点路径上的所有结点的平衡因子。因此删除的代价稍微要大一些。每一次删除操作最多需要O(logN)次旋转，执行删除操作的时间复杂度需要O(2logN)。
RBTree
AVLTree 虽然查找效率变高了，但是由于在插入，删除节点时需要通过大量的旋转操作来维护平衡性，维护代价大。红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能
(1) 查找代价：由于红黑树的性质(最长路径长度不超过最短路径长度的2倍)，可以说明红黑树虽然不像AVL一样是严格平衡的，但平衡性能还是要比BST要好。其查找代价基本维持在O(logN)左右，但在最差情况下(最长路径是最短路径的2倍少1)，比AVL要略逊色一点。
(2) 插入代价：RBT插入结点时，需要旋转操作和变色操作。但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转，这一点和AVL的插入操作一样。虽然变色操作需要O(logN)，但是变色操作十分简单，代价很小。
(3) 删除代价：RBT的删除操作代价要比AVL要好的多，删除一个结点最多只需要3次旋转操作。
最后，因为RBTree 相比AVLTree 不是严格平衡的二叉查找树，插入，删除操作引起树的unbalance概率较低，所以需要进行 rebalance 的概率也较低，总体性能优于AVLTree。