精华内容
下载资源
问答
  • 平衡树

    万次阅读 2018-08-08 22:13:11
     平衡树是二叉搜索树和堆合并构成的数据结构,它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 二.优势  对一棵查找树(search tree)进行查询/新增/删除 等动作,...

    一.概念:

       平衡树是二叉搜索树和堆合并构成的数据结构,它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

    二.优势

       对一棵查找树(search tree)进行查询/新增/删除 等动作, 所花的时间与树的高度h 成比例, 并不与树的容量 n 成比例。如果可以让树维持矮矮胖胖的好身材, 也就是让h维持在O(lg n)左右, 完成上述工作就很省时间。能够一直维持好身材, 不因新增删除而长歪的搜寻树, 叫做balanced search tree(平衡树)。

    三.种类:

      1.红黑树              2.AVL树               3.SBT         4.Treap          5.伸展树

     

    下面以Treap为例:

       1.特点:

       Treap每个节点的数据域包含2个值,key和weight。 
            key值,和原来的二叉搜索树一样,满足左子树<根节点<右子树。 
            weight值,随机产生。在Treap中weight值满足堆的性质,根节点的weight值小于等于(或大于等于)左右儿子节点。 

                

       2.结构调整:

       Treap的大部分操作都和二叉搜索树是一样的,唯一区别在于每次插入一个节点后,需要对树的结构进行调整。

    因为每一个节点的weight值不一样,当我们按照key值插入一个节点后,这个节点有可能不满足weight值的要求。

       左旋:在例子中是将右子树节点旋转至根。

       

       右旋:将左儿子节点旋转至根。
       

       

        

       

    展开全文
  • 平衡树与非平衡树简介

    千次阅读 2017-12-20 09:28:55
    平衡树与非平衡树的简单介绍。

         在二叉树中已经讲过,普通的二叉搜索树作为数据存储工具具有重要的优势:可以快速地找到一个给定值的数据项,并且可以快速的插入数据和删除数据。其他的数据存储结构,如数组在删除元素时必须要对删除元素后面的每一位元素都进行前移操作,而链表查询元素时必须要从初始元素一个一个的遍历到待查询元素,执行操作都不如二叉树来的快。

         但是,在二叉树文章中末尾讲过,如果树中插入的是随机数据,则增删查操作执行效果很好,因为数据是分散的、无序的。但是,如果插入的是有序数据(10,20,30,40...)或者(96,80,56,32...), 二叉树的执行效率会变得特别慢,因为当插入的数据有序时,二叉树就是非平衡的了。而对于非平衡树,它的快速查找(插入,删除)指定项的能力就丧失了。

        因为二叉树中任意一个节点的左子节点的关键字值小于这个节点的值,右子节点的关键字的值大于或等于这个节点的值。

    例如

        向树中依次插入(10,20,30,40...),最终树的形态如图:


        向树中依次插入(96,80,56,32...),最终树的形态如图:


        

        当树没有分支时,它其实就是一个链表(甚至比链表查询速度还要慢,毕竟链表不需要每一步都进行比较操作)。数据的排列是一维的,而不是二维的。不幸的是,和链表一样,现在就必须要(平均)查找一半的数据项来寻找要找的数据项。这种情况下,查询的速度下降到O(N),而不是平衡树的O(logN)。

       例如在一棵有10000个数据项的非平衡树中搜索数据平均要5000次比较,而在随机插入生成的平衡树中搜索数据项只需要14次(log2 (10000))比较。

       由部分无序的数据所生成的树只是部分不平衡。


       尽管部分不平衡树比最不平衡树情况要好,但是在这种情况下搜索花费的时间在O(N)和O(logN)之间,这取决于树的不平衡程度。显然,在这种情况下的查找时间不是最佳的。


       为了能以较快的时间O(logN)来搜索一棵树,需要保证树总是平衡的(或者至少大部分是平衡的)。这就是说对于树中的每个节点在它左边的后代数目和在它右边的后代数目应该大致相等。

      关于如何保证树的平衡性,在后面的文章中再详细讲解。


      注: 本文内容参考于Java数据结构和算法第二版,如有错误和疑问请留言,共同进步。

    展开全文
  • 好久不见! 就差这个坑就补齐了! 估计高三也不会太更博客了,不知道是不是NOIP前的最后一篇? 在博客园的新博客欢迎关注! 发现自己平衡树学了跟...平衡树的本质是一棵二叉搜索树(Binary Search Tree,即BST),

    好久不见!
    就差这个坑就补齐了!
    估计高三也不会太更博客了,不知道是不是NOIP前的最后一篇?
    在博客园的新博客欢迎关注!
    发现自己平衡树学了跟没学一样,退役了简单学了一发……
    平衡树有很多,比如AVL树,红黑树(RBTree)什么的,AVL被魔改成SBT?RBTree是系统中的平衡树。但是不常用不介绍了。
    平衡树的本质是一棵二叉搜索树(Binary Search Tree,即BST),规定一个二叉树,其左儿子的值都小于它,其右儿子的值都大于它,也就是说把二叉搜索树按中序遍历即可对这些数进行排序。但是这个二叉搜索树不是唯一的。
    我们可以用BST解决一些维护集合问题,比如插入一个数,查询某数排名(第几小)和查询第kkk大数。直接按着定义模拟,把BST搜一遍即可完成操作。
    可是这种操作很爆炸,当按照从小到大的顺序插入数据的时候复杂度会很大(此时BST为一条链),而且删除操作很困难。
    那么就需要一些操作维护这棵BST了。
    我们发现,有两个操作:左旋和右旋可以在不破坏BST性质的情况下维护这棵BST不会退化成链的形式。
    下面给出一棵BST的一部分
    BST
    右旋的意思即为:对于kkk节点,把父亲节点xxx作为自己的右儿子,自己的右儿子作为旋转后xxx的左儿子。
    分步的操作如下:
    Rturn1->Rturn2
    因为lc<k<rc<x<RClc<k<rc<x<RClc<k<rc<x<RC,旋转后仍符合。
    那么左旋就很好理解了:对于kkk节点,把父亲节点xxx作为自己的左儿子,自己的左儿子作为旋转后xxx的右儿子。
    Lturn1->Lturn2
    这样旋转有什么用呢?
    于是就有这几种维护方式了!

    1、Splay

    Splay可以说是一种经典的维护方式了,通过维护xxx-父亲-祖父的关系实现平衡,也就是判断这三个点是否在一条直线上实现平衡。
    记录操作Splay(x)\text{Splay}(x)Splay(x)为把xxx节点转到根上。这样很容易就可以快速查找了。
    那么如何旋转呢?
    于是我们开始了大段的讨论:(其实就三种……)
    1、xxx的父亲就是根……
    转一次就行了……
    2、xxx-父亲-祖父在一条直线上:
    这种情况如图:
    Splay1
    现在fffxxx的左儿子,gggfff的左儿子(右儿子同理,只不过操作相反),那么我们将ggg右旋,再将fff右旋即可(如果右儿子即为左旋),这个是Zig-Zig(Zag-Zag)操作。
    如图所示……
    Splay2->Splay3
    这样xxx就是根了!
    3、xxx-父亲-祖父不在一条直线上:
    就是拧着的呗……
    Splay4
    现在fffggg的右儿子,xxxfff的左儿子(反着的同理),我们反向操作,对fff右旋,再对ggg左旋即可把xxx转到根上。这个是Zig-Zag(Zag-Zig)操作。
    如图所示……
    Splay5->Splay6
    于是我们可以把任意一个节点都转到根上了!
    那么复杂度呢……
    根据势能分析,可知nnn个点,mmm次操作的Splay树的时间复杂度为O((n+m)log⁡2n)O((n+m)\log_2 n)O((n+m)log2n)
    这里的势能可以理解为物理学势能,网上证明应该很多吧……这里不贴了……
    Splay应用广泛,可以支持动态序列操作(如普通的平衡树),还可以支持区间变化的操作,比如区间反转,区间移动等。
    如何在Splay上提取区间呢?
    记需要提取[l,r][l,r][l,r],那么把l−1l-1l1提到根,将r+1r+1r+1提到根的右子树,那么根的右子树的左子树(即r+1r+1r+1的左子树)即为[l,r][l,r][l,r]区间的所有元素,就可以根节点打标记来维护了。
    但是当l=1l=1l=1时没有000元素,当r=nr=nr=n时没有n+1n+1n+1元素,这样就需要手动添加000n+1n+1n+1元素了。
    Splay还可以用在Link-Cut Tree上(即动态树),就可以维护森林中每棵树的形态了。这玩意很玄学就不补板子了……
    Splay在遇到有序数据的时候还会被卡……

    2、Treap

    Treap是个很玄学的数据结构,它是BST和Heap的合体版本。
    堆是个二叉树,其每个节点的优先级比儿子们的优先级都要小,这就是priority_queue的实现方式。
    因为BST是因为一些有序数据使得其退化,然而随机数据可以认为是无序的。那么把随机数当做Heap的优先级维护Tree就可以达到平衡BST的作用。所以,我们利用左旋和右旋操作保持Heap的性质,即可达到BST的平衡。
    Treap的树高期望是O(log⁡2n)O(\log_2 n)O(log2n)的,所以它的复杂度是期望O(log⁡2n)O(\log_2 n)O(log2n)的。
    Treap还有无旋维护的,是利用把树分成两块再合并的操作维护。
    Treap还可以演变为替罪羊树,主要思想是暴力重构……是一种重量平衡树。
    可以用Windows卡Treap(Windows下的rand范围比较小,再乘一个rand就可以防卡了……)

    3、SBT

    SBT是2006年在冬令营上首次出现的,可是被诸神犇喷不知道为什么……据说是换了一种方式维护AVL。
    主要是用Maintain操作维护平衡,而且这个Maintain操作是均摊O(1)O(1)O(1)的非常快(据说比AVL,Treap,Splay快很多)。
    知乎上陈启峰本人已经给出了资料包,可以参考。
    貌似SBT只能刷裸题+刷时间榜……
    下面是喜闻乐见的板子时间……
    Splay
    Treap
    SBT

    展开全文
  • 没事闲的学学平衡树吧,打代码炒鸡爽的(特别是机械键盘)(无视)。。。 (学习ing) - 平衡树到底是啥? 先看看排序二叉树吧 排序二叉树就是一棵树,啥树呢——就是这样一颗当前节点的左子树的权值都小于当前...

    没事闲的学学平衡树吧,打代码炒鸡爽的(特别是机械键盘)(无视)。。。
    (学习ing)
    - 平衡树到底是啥?

    • 先看看排序二叉树吧
    • 排序二叉树就是一棵树,啥树呢——就是这样一颗当前节点的左子树的权值都小于当前节点值,右子树的也一样。
      这样经过左-中-右的遍历就是一个有序序列。

    • 这样一棵树有啥用呢——就是可以维护一个有序的东西,可以动态插入,删除,查询第k大,查询前驱后继(就是有序序列中跟他挨着的那两个),还可以………很多作用,而且最重要的就是它可以转!

    • 怎么转呢?
    • 先看为什么转:因为这是一个有序序列变的树,所以节点和节点的权值只要是(横着看)是有序的就是排序二叉树,所以(纵向看)是啥样不重要,这样就造成了——排序二叉树的样子随插入顺序变化而变化。
    • 那么问题来了,如果我非常(变态)的有序的插入,最后就是一个链。这样所有操作都变回O(n)了。我不白玩了(这能忍吗)。
    • 所以要转。。。
      我一直不理解为啥叫转。。我觉得这东西横着看好看。。。
      估计我是不正常
      横着看就是把旋转当成改变节点深度(高度)
      经过调整高度之后呢,就可以不改变性质的前提下改变结构,最好的结果就是把它变成一个最优的结构(就是平衡树了)
      —————————————分割线———————————————
      呼~终于说完排序二叉树(查找树)了。
      该说平衡树了——
    • 平衡树定义:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
      这样的平衡树就可以解决退化的问题了
    • 现在常见的平衡树有:
      1. splay
      2. treap
      3. SBT
      4. AVL
      5. 没了
        (还有红黑树。。。这东西是非常NB的,但是代码量真不是我这种弱鸡能写的)
        (拉仇恨)STL中还有自带的set和map(红黑树实现),但只支持插入删除查找,在一些地方可以用。

    我在这就大概介绍下吧,详细的后续写,放链接。

    展开全文
  • 文艺平衡树算法

    千次阅读 2021-02-16 20:55:57
    一、文艺平衡树解决什么问题 您需要写一种数据结构,来维护一个有序序列。 其中需要提供以下操作:翻转一个区间,例如原有序列是5 4 3 2 1,翻转区间是[2,4],结果为5 2 3 4 1 二、文艺平衡树与普通平衡树 a[5]={ 5 ...
  • 各种平衡树

    2017-11-12 19:10:00
    平衡树 维基百科,自由的百科全书 平衡树是计算机科学中的一类数据结构。 平衡树是计算机科学中的一类改进的二叉查找树。一般的二叉查找树的查询复杂度是跟目标结点到树根的距离(即深度)有关,因此当...
  • 1、平衡树 (1)概念 平衡树左右子树的高度差的绝对值不超过1(左右子树的高度差为该结点的平衡因子,只能取-1,0,1),且其左右子树也是平衡树。 (2)向平衡树中插入结点时,该结点一定是插入在叶子结点上的。
  • 这道题考察的是平衡树的模板,只有一些平衡树的基本操作,相信只要对平衡树有一些了解的同学就能把这题A掉。 做这道题,权当是复习一下平衡树的模板,为接下来的平衡树的学习和刷题打下基础。 今天我主要讲的是...
  • 适度平衡树

    2016-09-20 07:57:10
    适度平衡树,是指将树高限制为“渐进地不超过 O(logn)O(\log n)”。举例: AVL 树; 伸展树; 红黑树; kd-树; 当然这些都可以归入平衡二叉搜索树(BBST,Balanced Binary Search Tree)之列。
  • 判断该树是不是平衡树 1. 递归 空间复杂度:深度 log2N(表示log以2为底N的对数) 时间复杂度:O(n^2) (递归的次数*每次递归的次数) 每个节点的遍历*高度(也是遍历整个树) 代码: int _Depth(Node* ...
  • 第一次写真正的树套树:线段树套平衡树?!(平衡树套线段树?!) 线段树维护的是区间,然后对于线段树维护的区间的所有数字都维护一个平衡树,然后所有的操作都对每个平衡树单独处理。 比如说操作3,需要先二分...
  • 二叉平衡树的旋转操作

    万次阅读 多人点赞 2018-06-25 00:33:21
    旋转是很多二叉平衡树维持平衡的主要手段,在这里复习一下。其实旋转过程中节点位置的变化只要遵循一个原则就行了:比Root小的在左子树,比Root大的在右子树。(当然这里前提条件是左小右大)。 情况一:插入F节点...
  • 总结二叉查找树:任意一个节点所包含的键值,大于等于左孩子的键值,小于等于右孩子的键值。...对于1百万个节点的平衡树,树的高度为12-20之间,对于10亿个节点的平衡树,树的高度为18-30之间。伸展树:当某个节点
  • 二叉平衡树(AVL树)

    2017-07-28 15:19:41
    这时,我们可以进入到平衡树的学习中了,但在学习之前,有一个问题,何为平衡树?很多的参考书中说到,平衡树就是每一个节点的平衡因子的值只能为0,±1。那么平衡因子又是什么?平衡因子,是左右子树节点个数的差。...
  • 树套树-线段树套平衡树

    千次阅读 2017-04-15 16:30:41
    树套树-线段树套平衡树的总结。
  • 平衡树·splay

    千次阅读 2020-01-27 19:30:16
    splaysplaysplay是实现平衡树的一种方法 他需要满足一个条件,就是对于一个点为根节点的子树,他的左子树全部小于根节点,右子树全部大于根节点 那他为什么叫这个名字呢? 我们查询一下百度翻译 但是事实上,...
  • 后缀平衡树

    千次阅读 2017-07-09 15:48:00
    本是打算研究后缀结构,但是发现不管是倍增还是DC3都异常容易错,知道最近才学习到了倍增算法的简易写法,但是仍然不爽,于是乎进入了后缀平衡树这样一个大坑。 风雨,残花,遇见你首先遇到的一个问题就是treap常数...
  • 二叉平衡树

    2014-10-24 17:24:55
    想要了解B+和B-树,要先了解二叉平衡树:这是一种
  • 前面学习二叉查找树和二叉树的各种遍历,但是其查找效率不稳定(斜树),而二叉平衡树的用途更多。查找相比稳定很多。(欢迎关注数据结构专栏) AVL树是带有平衡条件的二叉查找树。这个平衡条件必须要容易保持。而且要...
  • 创建二叉平衡树

    千次阅读 2016-08-10 15:45:38
    那么如何根据升序数组建立二叉平衡树,很简单,只需找到中间节点作为根,同理递归建立左右子树即可。 代码 /* 题目描述 对于一个元素各不相同且按升序排列的有序序列,请编写一个算法,创建一棵高度最小的二叉...
  • 建立平衡树,可以先将数组进行排序,然后选取中间元素作为根节点,数组中间元素左边的元素为根节点的左子树,数组中间右边的元素为根节点的右子树。 再对右子树和右子树选取中间节点,进行建树操作。 代码: package...
  • 什么是平衡树?所谓平衡树,就是树的任意结点的左子树和右子树的高度之差的绝对值不超过1。 所以判断一棵树是否为二叉树,不难想到可以先求出树的高度,再求出左右子树的高度差来判断,那么就想先求树的高度。 求树...
  • [hihoCoder]#1325 : 平衡树·Treap(平衡树)

    千次阅读 2016-10-02 21:04:12
    #1325 : 平衡树·Treap 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Ho:小Hi,我发现我们以前讲过的两个数据结构特别相似。 小Hi:你说的是哪两个啊? 小Ho:就是二叉...
  • 不过,由于最近做的题目的题解中经常出现“平衡树”这三个字,我决定从最简单的替罪羊树开始,好好学习平衡树。 简介 替罪羊树,英文名Scapegoat Tree,是我认为平衡树中最简单的一种。 替罪羊树的重构...
  • 在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis AVL树其实就是在...
  • 平衡树(AVL)

    2018-04-08 16:30:35
    1 概念 1.1 定义 AVL树又称为高度平衡的二叉搜索树,是1962年有俄罗斯的数学家G.M.Adel’son-Vel’skii和E.M.Landis提出来的。...注实现平衡树可采用的方法之一: 每个节点都有一个平衡因子(b...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 32,610
精华内容 13,044
关键字:

平衡树