AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。插入构建AVL树用时为O(lg n). 因为树高为O(lg n),在各个调整节点时旋转中没有循环所以为O(1)。
红黑树是在二叉查找树上多了一个存储颜色的节点,颜色只能是红或者黑。根据遍历树时对颜色遍历来确保每个路径长不能超过其他路径长的2倍,几乎是平衡的。红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能。红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外,由于它的设计,任何不平衡都会在三次旋转之内解决。当然,还有一些更好的,但实现起来更复杂的数据结构 能够做到一步旋转之内达到平衡,但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高。
当然,红黑树并不适应所有应用树的领域。如果数据基本上是静态的,那么让他们待在他们能够插入,并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的,例如,做一个哈希表,性能可能会更好一些。
分享到:
相关推荐
在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者...
介绍rb和avl树, linux kernel
红黑树和AVL树的代码实现,并显示树的形状,同时红黑树还可以输出个路径以及黑高度
AVL 树是一种平衡二叉搜索树,AVL 树有一个特点,所有节点的平衡因子不能大于 1,即所有节点的左子树与右子树的深度差只能为-1,0,1。根据这个概念,判断 AVL 树 就是去判断一棵二叉树是否是二叉搜索树,并且是否...
AVL树的简介,方便初学的读者了解AVL树。
本人实现的 AVL树与红黑树,具有可视化界面,代码清晰。
数据结构课程设计 图像化界面演示AVL树的插入、删除、查找操作,支持旋转的单步和自动演示
AVL树中 插入、删除节点以及判断一棵二叉查找树是否为AVL树
对输入的avl树判断其是否为avl树,并在其上插入删除元素,并把二叉查找树转换为avl树
数据结构中avl树的实现,包含avl树的插入,删除节点,并以括号表示法输出结果
AVL树的C语言实现
AVL树详解, 可以更深刻的了解到AVL树 AVL树详解, 可以更深刻的了解到AVL树 AVL树详解, 可以更深刻的了解到AVL树 AVL树详解, 可以更深刻的了解到AVL树 AVL树详解, 可以更深刻的了解到AVL树
学习AVL树的算法实现,使用c++在vc6.0中进行相应的算法实现,对正在学习算法的孩子有帮助
(1)编写 AVL树判别程序,并判别一个二元查找树是否为 AVL树。二元查找树用其先序遍历结果表示,如:5,2,1,3,7,8。 (2)实现 AVL树的 ADT,包括其上的基本操作:结点的加入和删除;另外包括将一般二元查找树...
AVL树 平衡二叉树 的各种方法:查找、删除、插入等
包括插入,删除等操作的AVL树,C++实现
这两个源文件主要实现了基于C++语言编写的AVL树,将AVL树的所有操作都实现了。测试平台为Linux,现将AVL树的源码奉上。
该程序通过C++实现了AVL树的一些基础操作:1.编写AVL树判别程序,并判别一个二叉搜索树是否为AVL树;2.实现AVL树的ADT,包括其上的基本操作:结点的加入和删除;3.实现基本操作的动态演示(图形演示);最重要的是,该...
avl树的实现: avl树是每个节点的左子树和右子树的高度最多差1的二叉查找树.一棵高度为h的avl树最少节点数由S(h) = S(h-1)+S(h-2)+1得到.avl树要保证任一节点的左右子树的高度之差的绝对值不能超过1(空树的高定义为1...
avl树实现 数据结构数据结构数据结构数据结构