平衡因子:每个结点的平衡因子就是左右子树的高度之差,即可用如下公式表示:BF(T) = Hl-Hr 平衡二叉树:平衡二叉树可能是空树,也有可能是左右子树高度之差小于等于1的树,即平衡因子的绝对值小于等于1。 那么为了使整棵树基金可能平衡,那么在构造树的过程中必须随时检查每个结点的平衡因小于等于。那么针对各种情况,为了让树更加平衡,那么必须对不平衡的点进行旋转处理,根据不同情况可以分为单左旋(LL旋转),单右旋(RR旋转),左右旋转(LR旋转),右左旋转(RL旋转)这4种旋转技术。
AVL树 零、前言 一、AVL树的概念 二、AVL树结点定义 三、AVL树的插入 四、AVL树的旋转 1、左单旋 2、右单旋 3、左右双旋 4、右左双旋 5、总结 五、AVL树的验证 六、AVL树的性能 零、前言 本章主要讲解map和set的底层结构平衡二叉搜索树的一种-AVL树的特性及其实现 一、AVL树的概念 引入: map/multimap/set/multiset其底层都是按照二叉搜索树来实现的,但是二叉搜索树有其自身的缺陷 假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化
树这个神奇的结构,由于其带有数学中指数增长的性质,再给予其一些特殊的性质后,被广泛应用于存储和搜索等苦力活,今天我们来学习用来搜索二叉树中的AVL树是如何实现高效的搜索功能的。
对于AVL树,相比普通的二叉搜索树,最主要的就是多了一个平衡因子保持AVL高度平衡的结构。而为了能够更加便捷的操作平衡因子,除了左右节点的指针,还要新增一个父亲节点指针,即三叉链的结构,因为左右子树的增加节点就会导致父亲节点平衡因子的变化:
二叉搜索树虽可以缩短查找的效率,但 如果数据有序或接近有序二叉搜索树将退化为单支树,查
我们在前面学习二叉搜索树时提到,二叉搜索树的查找效率为 O(N),因为当数据有序或接近有序时,构建出来的二叉搜索树是单分支或接近单分支的结构,此时树的高度接近 n,所以最坏情况下二叉搜索树的查找效率为 O(N);
普通的二叉搜索树可能会退化为单支树(歪脖子树),导致搜索性能严重下降,为了解决这个问题,诞生了平衡二叉搜索树,主要是通过某些规则判断后,降低二叉树的高度,从而避免退化,本文介绍的 AVL 树就属于其中一种比较经典的平衡二叉搜索树,它是通过 平衡因子 的方式来降低二叉树高度的,具体怎么操作,可以接着往下看
二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
我们先来回忆一下二分搜索树所存在的一个问题:当我们按顺序往二分搜索树添加元素时,那么二分搜索树可能就会退化成链表。例如,现在有这样一颗二分搜索树:
红黑树是一种常见的自平衡二叉查找树,常用于关联数组、字典,在各种语言的底层实现中被广泛应用,Java的TreeMap和TreeSet就是基于红黑树实现的。本篇分享将为读者讲解红黑树的定义、创建和用途。
二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下,时间复杂度为O(N);
在讨论平衡二叉树之前,先了解什么是二叉搜索树,二叉搜索树是二叉树的一种,它有一种特性,就是每个节点的左子节点都比节点本身的值小,右子节点都比节点本身大。因为这个特性,当对二叉搜索树进行中序遍历的时候,输出一定是按升序排列的。 利用二叉搜索树,可以在O(log N)的时间复杂度下查找指定元素。然而如果在插入二叉搜索树的时候,是以升序的方式,比如[1,2,3,4,5],二叉搜索树会一直往右节点增加,这样会导致二叉搜索树退化成链表,查找的时间复杂度也降到了O(N)。
因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:
前面我们介绍了STL中的关联式容器map/set/multimap/mutiset等,我们可以发现它们的底层都是按照二叉搜索树来实现的,但是二叉搜索树自身有一些缺陷,当往二叉搜索树中插入的元素有序或者接近有序二叉搜索树就会退化为单支,其检索的时间复杂度就会退化为O(n)。因此map、set等关联式容器的底层结构是对搜索二叉树进行平衡处理的平衡二叉搜索树。 本节我们就来了解平衡搜索二叉树AVL树的相关概念。
为什么叫AVL树? 因为AVL树是由 G.M.Adelson-Velsky 和 E.M.Landis 这两位俄罗斯科学家在1962年的论文中首次提出,是最早的自平衡二分搜索树结构。 由于AVL树是自平衡二分搜索树,所以本质上还是二分搜素树,也就是二分搜索树的性质AVL树都满足,由于二分搜索树在添加有序元素时,会退化成链表,造成时间复杂度为O(n),但AVL树是不会出现这种情况的,因为AVL树通过自平衡来解决了退化成链表的问题,关于二分搜索树,你可以看我之前二分搜索树(Binary Search Tree)这篇文章。 平衡二叉树:对于任意一个节点,左子树和右子树的高度差都不能超过1。
首先介绍下 二分搜索树 ,它又名有序二叉查找树,它的特点是左子树的节点值要小于父节点值,右子树的节点值要大于父节点值。基于这样的特点,我们在查找某个节点的时候,可以采取二分查找的思想快速找到这个节点,时间复杂度期望值是为O(log n),但是它有最坏的的情况下。
3. c处新增节点 parent->_bf = 1; cur->_bf = 0; curright->_bf = 0;
1. 虽然二叉搜索树的搜索效率很高,当搜索树接近满二叉树时,搜索效率可以达到logN,但是如果数据是有序的,则二叉搜索树会退化为单支树,搜索效率和普通的序列式容器相同了就,所以在搜索树的基础上,两位俄罗斯数学家研究出了平衡搜索树。
二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,导致其效率低下。
考虑一下二叉搜索树的特殊情况,如果一个二叉搜索树所有的节点都是右节点,那么这个二叉搜索树将会退化成为链表。从而导致搜索的时间复杂度变为O(n),其中n是二叉搜索树的节点个数。
二叉搜索树存在一个问题: 当往树中插入的数据一大部分大于某个节点或小于某个节点,这样就会导致树的一条边非常深。为了解决这个问题就出现了自平衡树这种解决方案。
不过二分搜索树不需要每一个节点都有两个子节点,不需要是一个满二叉树,所以二分搜索树在构建的时候,如果数据集是有序的,比如从小到大,或者从大到小的有序序列,二分搜索树就会退化成链表。
二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。
AVL树是一种自平衡二叉搜索树,它能够在每次插入或删除节点时通过旋转操作来保持树的平衡。在本文中,我们将深入讲解Python中的AVL树,包括AVL树的基本概念、平衡性维护、插入、删除和查询操作,并使用代码示例演示AVL树的使用。
接上篇文章《二叉搜索树》了解到二叉搜索树在极端情况也不能满足我们对于查询性能的要求。
二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
二叉搜索树一定程度上可以提高搜索效率,但是当原序列有序,例如序列A = {1,2,3,4,5,6},构造二叉搜索树如图。依据此序列构造的二叉搜索树为右斜树,同时二叉树退化成单链表,搜索效率降低为O(n)。
AVL树本质上是一颗二叉查找树,但是它又具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为平衡二叉树。下面是平衡二叉树和非平衡二叉树对比的例图:
map和set其底层都是按照二叉搜索树来实现的,但是二叉搜索树有其自身的缺陷,假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成O(N),因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理,即采用平衡树来实现。
二叉搜索树的特性便于我们进行查找插入删除等一系列操作,其时间复杂度为O(logn),但是,如果遇见最差的情况,比如以下这棵树:
平衡二叉搜索树(AVL树)是一种自平衡的二叉搜索树,它通过在插入或删除节点时进行旋转操作来保持树的平衡性。在AVL树中,任何节点的两个子树的高度差(平衡因子)最多为1。这种平衡性质确保了AVL树的高度始终是对数级别,使得查找、插入和删除等操作的时间复杂度保持在O(log n)。在本文中,我们将深入讨论AVL树的原理,并提供Python代码实现。
上篇文章里面,我们已经学习了二叉搜索树的相关内容,二叉搜索树有一个缺点,在插入数据是有序的序列(包括升序和降序),会导致二叉树退化成链表,从而导致在查找,删除,添加时的性能均从O(logN)降低为O(N),这是不能接受的。如下图:
前面我们学习了二叉搜索树,二叉搜索树如果左右子树高度相差不大,那么效率还是可观的,比如:满二叉搜索树的查询效率为 O(logn). 但是,如果插入的数据是有序的,或者大部分有序,则会导致 “二叉搜索树” 退化为类似于链表的结构. 那链表查询数据的时间复杂度牛牛就不用多说了吧.答案: O(n)
红黑树(Red Black Tree)是一种自平衡的二叉搜索树(Self-balancing Binary Search Tree)。以前也叫做平衡二叉 B 树(Symmetric Binary B-tree)。
二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查 找元素相当于在顺序表中搜索元素,效率低下, 所以在此基础上提出解决办法: 当向二叉搜索树中插入新节结点时,如果能保证每个节点的左右子树高度之差的绝对值不超过1即可降低树的高度,从而减少平均搜索长度 AVL树又称平衡二叉搜索树
《算法(java)》 — — Robert Sedgewick, Kevin Wayne
红黑树性质 1、每个结点或是红色的,或是黑色的 2、根节点是黑色的 3、每个叶结点(NIL)是黑色的 4、如果一个节点是红色的,则它的两个儿子都是黑色的。 5、对于每个结点,从该结点到其叶子结点构成的所有路径上的黑结点个数相同。 和AVL树的比较 AVL树是一棵严格的平衡树,它所有的子树都满足二叉平衡树的定义。因此AVL树高被严格控制在XXX,因此AVL树的查找比较高效。但AVL树插入、删除结点后旋转的次数比红黑树多。 红黑树用非严格的平衡来降低插入删除时旋转的次数。 因此,如果你的业务中
我们知道,二叉搜索树的效率很高,如果数据有序或接近有序二叉搜索树将退化为单支树,查 找元素相当于在顺序表中搜索元素,效率低下,为了解决这个问题,AVL树(平衡二叉树)就出现了。
红黑树是一种常见的自平衡二叉查找树,常用于关联数组、字典,在各种语言的底层实现中被广泛应用,Java 的 TreeMap 和 TreeSet 就是基于红黑树实现的。
参考资料 《算法(java)》 — — Robert Sedgewick, Kevin Wayne 《数据结构》 — — 严蔚敏 2017年度原创IT博客评选:http://www.itbang.me/goVote/203 引子 近日, 为了响应市政府“全市绿化”的号召, 身为共青团员的我决定在家里的后院挖坑种二叉树,以支援政府实现节能减排的伟大目标,并进一步为实现共同富裕和民族复兴打下坚实
红黑树是工程中一种非常重要的数据结构,大家熟悉的 HashMap 在 Java 8 就引入了红黑树的数据结构,不过实话实说,红黑树确实不容易掌握,左旋,右旋等概念让人头发发麻,本文用图文并茂的形式以期让读者彻底掌握红黑树,希望大家看了有收获,这篇文章肝了十多天,非常不易,希望大家不要白嫖,三连走起,多谢支持!
二叉树是一种常用的数据结构,更是实现众多算法的一把利器。 二分搜索树(Binary Search Tree)做为一种能实现快速定位查找的二叉树也得到了广泛应用
作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢! 二叉搜索树的深度与搜索效率 我们在树, 二叉树, 二叉搜索树中提到,一个有n个节点
树是一种分层数据的抽象模型。一个树结构包含一系列存在父子关系的节点,每个节点都有一个父节点(除了根节点)以及0个或多个子节点。位于树顶部的节点叫作根节点,它没有父节点。
这几天打开各种短视频的编程领域分类时,都有一些营销号配着动感的音乐,霹雳吧啦的输出一颗圣诞树,外行人以为多厉害,实际上最后都是这样输出。
没有必要过度关注本文中二叉树的增删改导致的结构改变,规则操作什么的了解一下就好,看不下去就跳过,本文过多的XX树操作图片纯粹是为了作为规则记录,该文章主要目的是增强下个人对各种常用XX树的设计及缘由的了解,也从中了解到常用的实现案例使用XX树实现的原因。
答案是:树的平衡。我们通过树的平衡,使得左右子树的深度保持在较小范围内,从而保证二叉树的查询效率。 这就是平衡二叉树的核心思想。 这种能平衡左右子树的二叉树,我们称之为平衡二叉树。
本文旨在让小白快速了解 学会红黑树的使用 和对二叉树 平衡树的基本认识 如果希望完全掌握 建议跟着我的代码然后看着图走一遍哈 方便理解
领取专属 10元无门槛券
手把手带您无忧上云