手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

数据结构-[树]-[1概览]

时间:2021/5/7 5:38:32|来源:|点击: 次

数据结构-[树]-[1概览]

文章目录

  • 数据结构-[树]-[1概览]
    • 前言
    • 1)BST树(二叉排序树)
    • 2)AVL树(平衡二叉搜索树)
        • 新概念:平衡因子
        • 结点新增和删除
    • 3)B树(B-树)(多路平衡查找树)
    • 4)B+树
    • 总结

前言

本文目前涉及的几种树,仅从理论方面进行探讨,暂不进行相关的代码实现。
其中关于B树和B+树的图解来自于以下链接:

B树和B+树原文链接

1)BST树(二叉排序树)

BST树(二叉排序树)(二叉搜索树)(Binary Sort Tree,**BST**)   
二叉排序树可以为空,如果不为空,需要满足以下几个性质:

1、非空左子树的所有键值<其根节点的键值
2、非空右子树的所有键值>其根节点的键值;
3、左右子树都是二叉排序树;

在这里插入图片描述

二叉排序树的查找效率并不稳定:

  1. 如果它平衡,则形成平衡二叉树(AVL树),查找的时间复杂度为log2N,层级上为O(logN)级别,效率接近于二分查找。
  2. 如果它完全不平衡,如上图所示,退化成链,则查找的时间复杂度便退化成了O(N)级别
    由于BST树查找效率的不稳定,故有了BST树中的特定类型AVL树

2)AVL树(平衡二叉搜索树)

新概念:平衡因子

平衡二叉搜索树(Self-balancing binary search tree)
  
AVL树属于BST的特定类型,满足所有BST树的定义,在此基础之上,增加以下定义:

1、如果树不为空,则任意节点的左右子树高度相差<=1

2、任意结点结点的左子树与右子树的高度差即为该结点的平衡因子。故在AVL树中任意结点的平衡因子都为(-1、1或者0)

如上图左侧的BST树,便是一种AVL树。

结点新增和删除

AVL树的查找效率变得更加稳定,且效率更高。

但同时新增和删除时的复杂度提升了不少。

新增后,如果不进行调整,就可能出现某些结点的平衡因子的绝对值>1,即之后的树可能不再是AVL树。

而维护一棵新的AVL树,则一般会针对结点进行左旋和右旋操作,四种情况下其中两种还需要进行两次旋转,才能确保树的平衡。

3)B树(B-树)(多路平衡查找树)

原文参考地址
原文参考地址
阶:B树中所有节点里最多的结点数值。 例如一颗4阶B树,那么所有结点里面,最多有4个子结点。

1.根结点至少有2棵子树。

2.每个中间节点都包含k-1个元素和k个孩子,其中 ceil(m/2) ≤ k ≤ m

3.每一个叶子节点都包含k-1个元素,其中 ceil(m/2) ≤ k ≤ m

4.所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域划分

6.类似于AVL树一样保持着有序(左小右大)

如图:三阶B树
在这里插入图片描述

4)B+树

1.有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。

2.所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。

在这里插入图片描述

总结

1)AVL树和B树对比而言,同等数据下,AVL树的查找效率还是不够高(层级会更深些)

2)B树和B+树作为数据库中使用比较多的技术来说,B+树的查找效率更高,因为维护了一条链表,在查找上比起B树来说,支持范围程度的查询。

Copyright © 2002-2019 某某自媒体运营 版权所有