普通的二叉查找树(二叉搜索树)依赖于输入数据的随机性。如果输出的是预先排序的数据，就会导致单支树的出现，这时效率会急剧下降。
AVL树是一种平衡二叉查找树，正是为了应对这种不平衡状态的出现。AVL树要求任意节点的左右两棵子树的高度相差最多是1。因此，AVL树能够保证整棵树的深度为O(logN)，其中N是树中节点总数。
红黑树是一种二叉查找树，但在每个节点都颜色，要么是红色要么是黑色(非红即黑)。通过任何一条从根到叶子节点的路径上黑色节点的个数必须相同这一限制条件，红黑树确保没有一条路径会比其他路径长出两倍。
与AVL树相比，红黑树是一种弱平衡二叉查找树，可能会产生不平衡状态，但是它的旋转次数少，所以，对于搜索、插入、删除操作较多的情况，通常使用红黑树。AVL树是高度平衡的，频繁的插入和删除会引起频繁的rebalance，导致效率下降；红黑树是弱平衡的，插入最多两次旋转，删除最多三次旋转。所以红黑树在查找、插入、删除等方面的性能都是O(logN)，且性能稳定。
RB-tree必须满足
1.每个节点不是红色就是黑色
2.根节点为黑色
3.如果节点为红色，其子节点必须为黑色
4.任一节点到NULL(树尾端)的任何路径，所含之黑节点数必须相同
根据规则4，新增节点必须为红色，根据规则3，新增节点的父节点必须为黑色。当新节点根据二叉搜索树的规则到达其插入点，却未能符合上述条件时，就必须调整颜色并旋转树形。