数据结构(树)

2020-08-08T19:46:06
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9

树:

    树是n个结点的有限集合,有且仅有一个根结点,其余结点可分为m个根结点的子树。

    度:

        指的是一个节点拥有子节点的个数。如二叉树的节点的最大度为2。

    高度/深度:

        数的层数,根节点为第一层,依次类推。

    叶子节点:

        度为0的节点,即没有子节点的节点。

 

二叉树:

    在二叉树中每个节点最多有两个子节点,一般称为左子节点和右子节点(或左孩子和右孩子)

    前序遍历(前根遍历):——>左——>右

    中序遍历(中根遍历):左——>——>右

    后序遍历(后根遍历):左——>右——>

 

满二叉树:

    在一棵二叉树中,如果所有分支结点都有左孩子和右孩子结点,并且叶子结点都集中在二叉树的最下层,这样的树叫做满二叉树

    高度为h,由2^h-1个节点构成的二叉树。

完全二叉树:

    二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树),第 h 层所有的结点都连续集中在最左边。

 

二叉查找树(BST):

    又称二叉排序树,亦称二叉搜索树(Binary Search Tree)。

    定义:

    一棵空树,或者是具有下列性质的二叉树:

    1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;

    2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;

    3)左、右子树也分别为二叉排序树;

    4)没有键值相等的结点。

    最坏情况,会退化为一条链表:

 

平衡二叉树(AVL):

    AVL树本质还是一棵二叉查找树,只是在其基础上增加了“平衡”的要求。

    定义: 

    它或者是一颗空树,或者具有以下性质的二叉排序树:

    它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1。

     二叉树,它的搜索时间复杂度为O(log2N),所以它的搜索效率和树的深度有关。

    由于普通的二叉查找树会容易失去”平衡“,极端情况下,二叉查找树会退化成线性的链表,导致插入和查找的复杂度下降到 O(n) 。

    通过平衡二叉树,我们解决了二叉查找树的缺点。对于有 n 个节点的平衡树,最坏的查找时间复杂度也为 O(logn)

    插入、删除结点,可能会破坏其二叉平衡树的平衡,此时需要通过 左旋、右旋等操作使之重新平衡。

 

红黑树:

    定义:

    1)具有二叉查找树的特点。

    2)根节点是黑色的;

    3)每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存数据。

    4)如果一个节点是红色的,则它的子节点必须是黑色的,也就是说,红色节点是被黑色节点隔开的。

    5)每个节点,从该节点到达其可达的叶子节点是所有路径,都包含相同数目的黑色节点。

    虽然平衡树解决了二叉查找树退化为近似链表的缺点,能够把查找时间控制在 O(logn),不过却不是最佳的,因为平衡树要求每个节点的左子树和右子树的高度差至多等于1。这个要求实在是太严了,导致每次进行插入/删除节点的时候,几乎都会破坏该规则,进而需要通过左旋右旋来进行调整,使之再次成为一颗符合要求的平衡树。

    显然,如果在那种插入、删除很频繁的场景中,平衡树需要频繁着进行调整,这会使平衡树的性能大打折扣,为了解决这个问题,于是有了红黑树。与平衡树不同的是,红黑树在插入、删除等操作,不会像平衡树那样,频繁破坏红黑树规则,所以不需要频繁调整,这也是我们为什么大多数情况下使用红黑树的原因。不过,单单在查找方面的效率的话,平衡树比红黑树快。

    平衡树是为了解决二叉查找树退化为链表的情况,而红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况。

 

B-树、B+树、B*树

    二叉树,它的搜索时间复杂度为O(log2N),所以它的搜索效率和树的深度有关,如果要提高查询速度,那么就要降低树的深度。要降低树的深度,很自然的方法就是采用多叉树,再结合平衡二叉树的思想,我们可以构建一个平衡多叉树结构,然后就可以在上面构建平衡多路查找算法,提高大数据量下的搜索效率。

    B树(balanced tree),平衡多路搜索树。相关分析参考:mysql索引数据结构

 

    B+树 与 红黑树 应用场景:

        1.红黑树多用在内部排序,即全放在内存中;B树多用在内存里放不下,大部分数据存储在外存时。因为B树层数少,因此可以确保每次操作,读取磁盘的次数尽可能的少。

        2.在数据较小,可以完全放到内存中时,红黑树的时间复杂度比B树低。反之,数据量较大,外存中占主要部分时,B树因其读磁盘次数少,而具有更快的速度。

扫一扫关注公众号添加购物返利助手,领红包
当前页面是本站的「Baidu MIP」版。发表评论请点击:完整版 »
因本文不是用Markdown格式的编辑器书写的,转换的页面可能不符合MIP标准。