平衡二叉树、二叉查找树、平衡二叉查找树、AVL树和红黑树的区别
平衡二叉树：
①树的左右高度差不能超过1；
②任何往下递归的左子树与右子树，必须符合第一个性质；
③没有任何节点的空树或只有根节点的树也是平衡二叉树。
二叉查找树：二叉查找树要么是一颗空树，要么就是具有如下性质的二叉树：
①若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
②若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
③任意节点的左、右子树也分别为二叉查找树；
④没有键值相等的节点。
平衡二叉查找树：由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树，又称AVL树，它是带有平衡条件的二叉查找树。它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
红黑树：主要特征是在每个节点上增加一个属性表示节点颜色，可以红色或黑色。红黑树和 AVL 树类似，都是在进行插入和删除时通过旋转保持自身平衡，从而获得较高的查找性能。与 AVL 树相比，红黑树不追求所有递归子树的高度差不超过 1，保证从根节点到叶尾的最长路径不超过最短路径的 2 倍，所以最差时间复杂度是 O(log n)。红黑树通过重新着色和左右旋转，更加高效地完成了插入和删除之后的自平衡调整。
红黑树在本质上还是二叉查找树，它额外引入了 5 个约束条件：① 节点只能是红色或黑色。② 根节点必须是黑色。③ 所有 NULL 节点都是黑色的。④ 一条路径上不能出现相邻的两个红色节点。⑤ 在任何递归子树中，根节点到叶子节点的所有路径上包含相同数目的黑色节点。这五个约束条件保证了红黑树的新增、删除、查找的最坏时间复杂度均为 O(log n)。如果一个树的左子节点或右子节点不存在，则均认定为黑色。红黑树的任何旋转在 3 次之内均可完成。
平衡二叉树、二叉查找树、平衡二叉查找树、AVL树和红黑树的区别：
平衡二叉树只是强调平衡而没有强调树中元素的有序性。
二叉查找树只是强调了树中数据的有序性而没有强调树的平衡。
平衡二叉查找树不但强调了数的平衡性，还强调了树中数据的有序性。
红黑树的平衡性不如 AVL 树，它维持的只是一种大致的平衡，不严格保证左右子树的高度差不超过 1。这导致节点数相同的情况下，红黑树的高度可能更高，也就是说平均查找次数会高于相同情况的 AVL 树。
在插入时，红黑树和 AVL 树都能在至多两次旋转内恢复平衡，在删除时由于红黑树只追求大致平衡，因此红黑树至多三次旋转可以恢复平衡，而 AVL 树最多需要 O(log n) 次。AVL 树在插入和删除时，将向上回溯确定是否需要旋转，这个回溯的时间成本最差为 O(log n)，而红黑树每次向上回溯的步长为 2，回溯成本低。因此面对频繁地插入与删除红黑树更加合适。