平衡二叉树是二叉排序树吗?
是的。衡二叉树（balanced binary tree）是一种特殊的二叉排序树，它或者为空树，或者每个结点的左右子树都是平衡二叉树，也就是每个结点的左右子树的高度之差只能是－1,0,1三种情况。平衡二叉树又称AVL树，是由苏联的Georgy Adelson-Velsky和E.M.Landis发明的，并以他们的名字命名。平衡二叉树的平衡状况由平衡因子（Balance Factor,BF)来衡量。平衡因子定义为当前结点的左子树高度减去右子树的高度之差，其可能取值只有－1,0,1。叶结点的BF都是0。平衡二叉树的应用价值：如果能维持平衡二叉树的结构，检索操作就能在O(log n)时间内完成，实现高效检索。最小不平衡子树：距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树。（指BF超出合法值）。最小非平衡子树：包含插入结点位置，其根结点的BF是1或－1的最小子树。（指BF非0，但BF在合法值范围内）。以上内容参考：百度百科-平衡二叉查找树
平衡二叉树是二叉排序树吗？
平衡二叉树不一定是二叉排序树，平衡二叉树是为了避免二叉排序树高度增长过快，降低二叉排序树性能而设的树，二叉排序树当然不可能都是平衡二叉树。首先平衡二叉树是特殊的二叉排序树，他的结点元素间存在着偏序关系；其次相对于一般的二叉排序树，平衡二叉树的左右子树的深度差也有不超过1层的约束，这样使得平衡树是同种元素序列情况下的深度最小的二叉排序树，这可以减少二叉树元素查找的深度，从而提升平均查找效率。应用平衡树可以完成集合的一系列操作， 时间复杂度和空间复杂度相对于“2-3树”要低，在完成集合的一系列操作中始终保持平衡，为大型数据库的组织、索引提供了一条新的途径。二叉排序树或者是一颗空树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值。（2）若右子树不空，则右子树所有结点的值均大于或等于它的根结点的值。（3）左、右子树也分别为二叉排序树。
什么是红黑树
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。树的旋转当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。为了保持红黑树的性质，我们可以对相关结点做一系列的调整，通过对树进行旋转（例如左旋和右旋操作），即修改树中某些结点的颜色及指针结构，以达到对红黑树进行插入、删除结点等操作时，红黑树依然能保持它特有的性质（五点性质）。
什么是红黑树？
最近研究JDK源码的时候，发现TreeMap和TreeSet底层数据结构是红黑树，当然，TreeSet其实本质上就是Value为一个固定值的TreeMap。在JDK1.8以后，HashMap也用到了红黑树。 那红黑树到底是怎样的一种数据结构呢？相信大家都不是非常了解，我也去翻了好多的相关文章，发现一篇很有趣的漫画，可以帮助大家很快了解红黑树大概是怎样的一种数据结构，有哪些特点。 只是大概的介绍一下红黑树，详细的实现大家还是请参考相关的算法书籍。 以下内容转自： 漫画算法：什么是红黑树？ 1.左子树上所有结点的值均小于或等于它的根结点的值。 2.右子树上所有结点的值均大于或等于它的根结点的值。 3.左、右子树也分别为二叉排序树。 下图中这棵树，就是一颗典型的二叉查找树： 1.查看根节点9： 3.由于10 < 13，因此查看左孩子11： 假设初始的二叉查找树只有三个节点，根节点值为9，左孩子值为8，右孩子值为12： 2.根节点是黑色。 3.每个叶子节点都是黑色的空节点（NIL节点）。 4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 下图中这棵树，就是一颗典型的红黑树： 什么情况下会破坏红黑树的规则，什么情况下不会破坏规则呢？我们举两个简单的栗子： 1.向原红黑树插入值为14的新节点： 为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。 下图所表示的是红黑树的一部分，需要注意节点25并非根节点。因为节点21和节点22连续出现了红色，不符合规则4，所以把节点22从红色变成黑色： 但这样并不算完，因为凭空多出的黑色节点打破了规则5，所以发生连锁反应，需要继续把节点25从黑色变成红色： 逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。说起来很怪异，大家看下图： 图中，身为右孩子的Y取代了X的位置，而X变成了自己的左孩子。此为左旋转。 顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。大家看下图： 图中，身为左孩子的Y取代了X的位置，而X变成了自己的右孩子。此为右旋转。 首先，我们需要做的是变色，把节点25及其下方的节点变色： 这时候我们需要把节点13看做X，节点8看做Y，像刚才的示意图那样进行右旋转： 如果想要详细了解红黑树算法，可以参考这篇文章： Java数据结构和算法（十一）——红黑树
