红黑树和平衡二叉树的区别是什么?红黑树详解

TheDisguiser 2020-04-14 18:18:30 java常见问答 9106

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

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

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

红黑树可以以 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一些知识问答的小知识的话,就请一直关注本站吧。