上回我们已经知道了红黑树的具体原理，相信你们对红黑树也有了一定的了解，这回我们就来说说红黑树与普通的平衡二叉树的区别到底有哪些，一起来看看吧。

红黑树与平衡二叉树的区别

红黑树不会追求“完全平衡 ”，它只会求部分达到平衡要求，降低了对旋转的要求，从而提高性能。

红黑树可以以 O(log2 n) 的时间复杂度进行查询、插入、删除等操作。此外，由于它的设计，所有不平衡都能够在三次旋转之内解决。在红黑树中，它的算法时间复杂度与AVL相同，并且统计性能会逼AVL树更高。

红黑树并不适应所有应用树的领域。如果数据上是静态的话，那么让他们待在他们能够插入，且不影响平衡的地方会具有更好的性能。如果数据是完全静态的话，试着做一个哈希表，性能可能会更好一些。

平衡二叉树，又被称为AVL树，它是一棵空树，它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这是类似于一个递归的数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

AVL树是最早发明的自平衡二叉查找树。在AVL树中，任何节点的两个子树的高度最大差别只能为一，所以它又被称为高度平衡树。查询、增加和删除在平均和最坏情况下都是O(log n)。增加和删除会需要通过一次或多次树旋转来重新平衡这个树。

我们引入二叉树的目的是为了提高二叉树的搜索的效率,从而减少树的平均搜索长度，为此,就必须在每颗二叉树插入一个结点时调整树的结构,让二叉树搜索能够保持平衡,从而可能降低树的高度,减少的平均树的搜索长度。

AVL树的定义:

一棵AVL树需要满足以下条件:

它的左子树和右子树都是AVL树

左子树和右子树的高度差不能超过1

性质:

1.一棵n个结点的AVL树的其高度保持在0(log2(n)),不会超过3/2log2(n+1)

2.一棵n个结点的AVL树的平均搜索长度保持在0(log2(n)).

3.一棵n个结点的AVL树删除一个结点做平衡化旋转所需要的时间为0(log2(n)).

从第一点来看 红黑树是牺牲了严格的高度平衡的优越条件为代价，使红黑树能够以O(log2 n)的时间复杂度进行查询、插入、删除操作。此外，由于它的设计，所有的不平衡都可以在三次旋转之内解决。

总结：

红黑树和平衡二叉树区别如下：

红黑树放弃追求完全平衡，只求大致平衡，在它与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，所以实现起来也更为简单。

平衡二叉树会追求绝对平衡，实现条件艰难，并且它每次插入新节点之后需要旋转的次数不能预知。

以上就是红黑树与平衡二叉树的区别了，想知道更多这种关于Java一些知识问答的小知识的话，就请一直关注本站吧。