精华内容
下载资源
问答
  • 二叉树二叉树:二叉树是每个节点最多有两个子树的树结构;是n(n>=0)个结点的有限集合,它...树中所含的n个节点和满二叉树中编号为1至n的节点一一对应满二叉树满二叉树:除最后一层外,每一层上的所有结点都...
    二叉树
    二叉树:二叉树是每个节点最多有两个子树的树结构;
    是n(n>=0)个结点的有限集合,它或者是空树(n=0),或者是由一个根结点及两颗互不相交的、分别称为左子树和右子树的二叉树所组成。

    完全二叉树

    完全二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点;
    树中所含的n个节点和满二叉树中编号为1至n的节点一一对应

    满二叉树

    满二叉树:除最后一层外,每一层上的所有结点都有两个子结点;满二叉树是一种特殊的完全二叉树;

    二叉排序树(二叉搜索树)
           1. 所有非叶子结点至多拥有两个儿子( Left Right );
           2. 所有结点存储一个关键字;
           3. 非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;
    二叉排序树:二叉树中,每个节点都不比它左子树的任意元素小,而且不比它的右子树的任意元素大。又叫二叉搜索树。
    平衡二叉树

    平衡二叉树(Balanced Binary Tree)是二叉查找树的一个进化体,也是第一个引入平衡概念的二叉树。1962年,G.M. Adelson-Velsky 和 E.M. Landis发明了这棵树,所以它又叫AVL树。
    定义:平衡二叉树或为空树,或为如下性质的二叉排序树:
      (1)左右子树深度之差的绝对值不超过1;
      (2)左右子树仍然为平衡二叉树.

    平衡二叉树要求对于每一个节点来说,它的左右子树的高度之差不能超过1,如果插入或者删除一个节点使得高度之差大于1,就要进行节点之间的旋转,将二叉树重新维持在一个平衡状态。

    这个方案很好的解决了二叉查找树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多。

    RBT 红黑树
    AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多;
    红黑是弱平衡的,用非严格的平衡来换取增删节点时候旋转次数的降低;
    所以简单说,搜索的次数远远大于插入和删除,那么选择AVL树,如果搜索,插入删除次数几乎差不多,应该选择RB树。
    红黑树上每个结点内含五个域,color,key,left,right,p。如果相应的指针域没有,则设为NIL。
    一般的,红黑树,满足以下性质,即只有满足以下全部性质的树,我们才称之为红黑树:
    1)每个结点要么是红的,要么是黑的。
    2)根结点是黑的。
    3)每个叶结点,即空结点(NIL)是黑的。
    4)如果一个结点是红的,那么它的俩个儿子都是黑的。
    5)对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
    下图所示,即是一颗红黑树:





    Trie树既可用于一般的字典搜索,也可用于索引查找。
    每个节点相当于DFA的一个状态,终止状态为查找结束。有序查找的过程相当于状态的不断转换
    对于给定的一个字符串a1,a2,a3,...,an.则
    采用TRIE树搜索经过n次搜索即可完成一次查找。不过好像还是没有B树的搜索效率高,B树搜索算法复杂度为logt(n+1/2).当t趋向大,搜索效率变得高效。怪不得DB2的访问内存设置为虚拟内存的一个PAGE大小,而且帧切换频率降低,无需经常的PAGE切换。
    B树
     即二叉搜索树:
     1.所有非叶子结点至多拥有两个儿子(Left和Right);
     2.所有结点存储一个关键字;
     3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;
     如:
     B树的搜索,从根结点开始,如果查询的关键字与结点的关键字相等,那么就命中;否则,如果查询关键字比结点关键字小,就进入左儿子;如果比结点关键字大,就进入右儿子;如果左儿子或右儿子的指针为空,则报告找不到相应的关键字;
     如果B树的所有非叶子结点的左右子树的结点数目均保持差不多(平衡),那么B树的搜索性能逼近二分查找;但它比连续内存空间的二分查找的优点是,改变B树结构(插入与删除结点)不需要移动大段的内存数据,甚至通常是常数开销;
     如:
     但B树在经过多次插入与删除后,有可能导致不同的结构:
     右边也是一个B树,但它的搜索性能已经是线性的了;同样的关键字集合有可能导致不同的树结构索引;所以,使用B树还要考虑尽可能让B树保持左图的结构,和避免右图的结构,也就是所谓的“平衡”问题; 
     实际使用的B树都是在原B树的基础上加上平衡算法,即“平衡二叉树”;如何保持B树结点分布均匀的平衡算法是平衡二叉树的关键;平衡算法是一种在B树中插入和删除结点的策略;

    B-
    是一种平衡多路搜索树(并不是二叉的):
           1. 定义任意非叶子结点最多只有M 个儿子;且M>2
           2. 根结点的儿子数为[2, M]
           3. 除根结点以外的非叶子结点的儿子数为[M/2, M]
           4. 每个结点存放至少M/2-1 (取上整)和至多M-1 个关键字;(至少2 个关键字)
           5. 非叶子结点的关键字个数= 指向儿子的指针个数-1
           6. 非叶子结点的关键字:K[1], K[2], …, K[M-1] ;且K[i] < K[i+1]
           7. 非叶子结点的指针:P[1], P[2], …, P[M] ;其中P[1] 指向关键字小于K[1]
    子树,P[M] 指向关键字大于K[M-1] 的子树,其它P[i] 指向关键字属于(K[i-1], K[i]) 的子树;
           8. 所有叶子结点位于同一层;
    如:( M=3
           B- 树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果
    命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为
    空,或已经是叶子结点;
    B- 树的特性:
           1. 关键字集合分布在整颗树中;
           2. 任何一个关键字出现且只出现在一个结点中;
           3. 搜索有可能在非叶子结点结束;
           4. 其搜索性能等价于在关键字全集内做一次二分查找;
           5. 自动层次控制;
    由于限制了除根结点以外的非叶子结点,至少含有M/2 个儿子,确保了结点的至少
    利用率,其最底搜索性能为:
    其中,M 为设定的非叶子结点最多子树个数,N 为关键字总数;
    所以B- 树的性能总是等价于二分查找(与M 值无关),也就没有B 树平衡的问题;
    由于M/2 的限制,在插入结点时,如果结点已满,需要将结点分裂为两个各占
    M/2 的结点;删除结点时,需将两个不足M/2 的兄弟结点合并;
    B+
           B+ 树是B- 树的变体,也是一种多路搜索树:
           1. 其定义基本与B- 树同,除了:
           2. 非叶子结点的子树指针与关键字个数相同;
           3. 非叶子结点的子树指针P[i] ,指向关键字值属于[K[i], K[i+1]) 的子树
    B- 树是开区间);
           5. 为所有叶子结点增加一个链指针;
           6. 所有关键字都在叶子结点出现;
    如:(M=3
    B+ 的搜索与B- 树也基本相同,区别是B+ 树只有达到叶子结点才命中(B- 树可以在
    非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;
           B+ 的特性:
           1. 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好
    是有序的;
           2. 不可能在非叶子结点命中;
           3. 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储
    (关键字)数据的数据层;
           4. 更适合文件索引系统;比如对已经建立索引的数据库记录,查找10<=id<=20,那么只要通过根节点搜索到id=10的叶节点,之后只要根据叶节点的链表找到第一个大于20的就行了,比B-树在查找10到20内的每一个时每次都从根节点出发查找提高了不少效率。
    B*
    B+ 树的变体,在B+ 树的非根和非叶子结点再增加指向兄弟的指针;
    B* 树定义了非叶子结点关键字个数至少为(2/3)*M ,即块的最低使用率为2/3
    (代替B+ 树的1/2 );
           B+ 树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2 的数据
    复制到新结点,最后在父结点中增加新结点的指针;B+ 树的分裂只影响原结点和父
    结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;
           B* 树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分
    数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字
    (因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之
    间增加新结点,并各复制1/3 的数据到新结点,最后在父结点增加新结点的指针;
    所以,B* 树分配新结点的概率比B+ 树要低,空间使用率更高;
    小结
           B 树:二叉树,每个结点只存储一个关键字,等于则命中,小于走左结点,大于
    走右结点;
           B- 树:多路搜索树,每个结点存储M/2 M 个关键字,非叶子结点存储指向关键
    字范围的子结点;
    所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;
           B+ 树:在B- 树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点
    中出现,非叶子结点作为叶子结点的索引;B+ 树总是到叶子结点才命中;
           B* 树:在B+ 树基础上,为非叶子结点也增加链表指针,将结点的最低利用率
    1/2 提高到2/3

    B+/B* Tree 应用
    数据库索引--索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。


    数据库索引--表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键。


    倒排索引--也可以由B树及其变种实现但不一定非要B树及其变种实现,如 lucene没有使用B树结构,因此lucene可以用二分搜索算法快速定位关键词。实现时,lucene将下面三列分别作为词典文件(Term Dictionary)、频率文件(frequencies)、位置文件 (positions)保存。其中词典文件不仅保存有每个关键词,还保留了指向频率文件和位置文件的指针,通过指针可以找到该关键字的频率信息和位置信息。   
    1. 关键词            文章号[出现频率]              出现位置     
    2. guangzhou           1[2]                      36
    3. he                  2[1]                      1
    4. i                   1[1]                      4
    5. live                1[2]                      25,   
    6. 2[1]                      2
    7. shanghai            2[1]                      3
    8. tom                 1[1]                      1


    参考文章
    B-树和B+树的应用:数据搜索和数据库索引 http://blog.csdn.net/hguisu/article/details/7786014
    B树、B-树、B+树、B*树 http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html

    展开全文
  • 如图所示,(a)图就是一棵满二叉树,(b)图则不是满二叉树,因为该二叉树的D,F,G,H,I叶子结点在同一层上 完全二叉树 设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数, 第 h 层所有...

    满二叉树

    满足以下两个条件,缺一不可

    1 所有分支结点都有左子树和右子树;
    2 所有叶子结点在同一层上
    

    如图所示,(a)图就是一棵满二叉树,(b)图则不是满二叉树,因为该二叉树的D,F,G,H,I叶子结点未在同一层上
    在这里插入图片描述

    完全二叉树

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

    b不是完全二叉树,因为B结点没有右子树
    在这里插入图片描述

    满二叉树和完全二叉树的应用

    待续

    参考

    完全二叉树与满二叉树的区别(有图)_Android_Ape-CSDN博客_完全二叉树

    展开全文
  • 二叉树 二叉树:二叉树是每个节点最多有两个子树的树结构; 是n(n>=0)个结点的有限集合,它或者是空树(n=0),或者是由一个根结点及两颗互不相交的、...树中所含的n个节点和满二叉树中编号为1至n的节点一一对应

    二叉树

    二叉树:二叉树是每个节点最多有两个子树的树结构;

    是n(n>=0)个结点的有限集合,它或者是空树(n=0),或者是由一个根结点及两颗互不相交的、分别称为左子树和右子树的二叉树所组成。


    完全二叉树

    完全二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点;

    树中所含的n个节点和满二叉树中编号为1至n的节点一一对应


    满二叉树

    满二叉树:除最后一层外,每一层上的所有结点都有两个子结点;满二叉树是一种特殊的完全二叉树;


    二叉排序树(二叉搜索树)

    二叉排序树:二叉树中,每个节点都不比它左子树的任意元素小,而且不比它的右子树的任意元素大。又叫二叉搜索树。

    平衡二叉树

    平衡二叉树(Balanced Binary Tree)是二叉查找树的一个进化体,也是第一个引入平衡概念的二叉树。1962年,G.M. Adelson-Velsky 和 E.M. Landis发明了这棵树,所以它又叫AVL树。

    平衡二叉树要求对于每一个节点来说,它的左右子树的高度之差不能超过1,如果插入或者删除一个节点使得高度之差大于1,就要进行节点之间的旋转,将二叉树重新维持在一个平衡状态。

    这个方案很好的解决了二叉查找树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多。

    红黑树rbtree 二叉排序树

    map 就是采用红黑树存储的,红黑树(RB Tree)是平衡二叉树,其优点就是树到叶子节点深度一致,查找的效率也就一样,为logN.在实行查找,插入,删除的效率都一致,而当是全部静态数据时,没有太多优势,可能采用hash表各合适。

    hash_map是一个hash table占用内存更多,查找效率高一些,但是hash的时间比较费时。

    总 体来说,hash_map 查找速度会比map快,而且查找速度基本和数据数据量大小,属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小, hash还有hash函数的耗时,明白了吧,如果你考虑效率,特别是在元素达到一定数量级时,考虑考虑hash_map。但若你对内存使用特别严格,希望程序尽可能少消耗内存,那么一定要小心,hash_map可能会让你陷入尴尬,特别是当你的hash_map对象特别多时,你就更无法控制了,而且 hash_map的构造速度较慢。

    现在知道如何选择了吗?权衡三个因素: 查找速度, 数据量, 内存使用。

     

    trie树Double Array 字典查找树


    Trie树既可用于一般的字典搜索,也可用于索引查找。
    每个节点相当于DFA的一个状态,终止状态为查找结束。有序查找的过程相当于状态的不断转换
    对于给定的一个字符串a1,a2,a3,...,an.则
    采用TRIE树搜索经过n次搜索即可完成一次查找。不过好像还是没有B树的搜索效率高,B树搜索算法复杂度为logt(n+1/2).当t趋向大,搜索效率变得高效。怪不得DB2的访问内存设置为虚拟内存的一个PAGE大小,而且帧切换频率降低,无需经常的PAGE切换。

     

    B树

           即二叉搜索树:

           1.所有非叶子结点至多拥有两个儿子(Left和Right);

           2.所有结点存储一个关键字;

           3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;

           如:

           B树的搜索,从根结点开始,如果查询的关键字与结点的关键字相等,那么就命中;否则,如果查询关键字比结点关键字小,就进入左儿子;如果比结点关键字大,就进入右儿子;如果左儿子或右儿子的指针为空,则报告找不到相应的关键字;

           如果B树的所有非叶子结点的左右子树的结点数目均保持差不多(平衡),那么B树的搜索性能逼近二分查找;但它比连续内存空间的二分查找的优点是,改变B树结构(插入与删除结点)不需要移动大段的内存数据,甚至通常是常数开销;

           如:

        但B树在经过多次插入与删除后,有可能导致不同的结构:

       右边也是一个B树,但它的搜索性能已经是线性的了;同样的关键字集合有可能导致不同的树结构索引;所以,使用B树还要考虑尽可能让B树保持左图的结构,和避免右图的结构,也就是所谓的“平衡”问题;      

           实际使用的B树都是在原B树的基础上加上平衡算法,即“平衡二叉树”;如何保持B树结点分布均匀的平衡算法是平衡二叉树的关键;平衡算法是一种在B树中插入和删除结点的策略;

     

    B-树

           是一种多路搜索树(并不是二叉的):

           1.定义任意非叶子结点最多只有M个儿子;且M>2;

           2.根结点的儿子数为[2, M];

           3.除根结点以外的非叶子结点的儿子数为[M/2, M];

           4.每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)

           5.非叶子结点的关键字个数=指向儿子的指针个数-1;

           6.非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];

           7.非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;

           8.所有叶子结点位于同一层;

           如:(M=3)

     

           B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点;

    B-树的特性:

           1.关键字集合分布在整颗树中;

           2.任何一个关键字出现且只出现在一个结点中;

           3.搜索有可能在非叶子结点结束;

           4.其搜索性能等价于在关键字全集内做一次二分查找;

           5.自动层次控制;

           由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少利用率,其最底搜索性能为:

           其中,M为设定的非叶子结点最多子树个数,N为关键字总数;

           所以B-树的性能总是等价于二分查找(与M值无关),也就没有B树平衡的问题;

           由于M/2的限制,在插入结点时,如果结点已满,需要将结点分裂为两个各占M/2的结点;删除结点时,需将两个不足M/2的兄弟结点合并;

     

     

    B+树

           B+树是B-树的变体,也是一种多路搜索树:

           1.其定义基本与B-树同,除了:

           2.非叶子结点的子树指针与关键字个数相同;

           3.非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);

           5.为所有叶子结点增加一个链指针;

           6.所有关键字都在叶子结点出现;

           如:(M=3)

     

       B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;

           B+的特性:

           1.所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;

           2.不可能在非叶子结点命中;

           3.非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;

           4.更适合文件索引系统;

     

    B*树

           是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;

     

       B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2);

           B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;

           B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;

           所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

     

    小结

           B树:二叉树,每个结点只存储一个关键字,等于则命中,小于走左结点,大于走右结点;

           B-树:多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点;

           所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;

           B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;

           B*树:在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3;




    展开全文
  • 二叉树,完全二叉树,满二叉树,二叉排序树,平衡二叉树,红黑树,B数,B-树,B+树,B*树(一): http://blog.csdn.net/yuxin6866/article/details/52327328 BST树  即二叉搜索树:  1.所有非...

    二叉树,完全二叉树,满二叉树,二叉排序树,平衡二叉树,红黑树,B数,B-树,B+树,B*树(一):

    http://blog.csdn.net/yuxin6866/article/details/52327328

    BST

           即二叉搜索树:

           1.所有非叶子结点至多拥有两个儿子(LeftRight);

           2.所有结点存储一个关键字;

           3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;

           如:

           

           BST树的搜索,从根结点开始,如果查询的关键字与结点的关键字相等,那么就命中;

    否则,如果查询关键字比结点关键字小,就进入左儿子;如果比结点关键字大,就进入

    右儿子;如果左儿子或右儿子的指针为空,则报告找不到相应的关键字;

           如果BST树的所有非叶子结点的左右子树的结点数目均保持差不多(平衡),那么B

    的搜索性能逼近二分查找;但它比连续内存空间的二分查找的优点是,改变BST树结构

    插入与删除结点)不需要移动大段的内存数据,甚至通常是常数开销;

           如:

          

       BST树在经过多次插入与删除后,有可能导致不同的结构:

       右边也是一个BST树,但它的搜索性能已经是线性的了;同样的关键字集合有可能导致不同的

    树结构索引;所以,使用BST树还要考虑尽可能让BST树保持左图的结构,和避免右图的结构,也就

    是所谓的“平衡”问题;      

           
    AVL平衡二叉搜索
    定义:平衡二叉树或为空树,或为如下性质的二叉排序树:
      (1)左右子树深度之差的绝对值不超过1;
      (2)左右子树仍然为平衡二叉树.
    平衡因子BF=左子树深度-右子树深度.
    平衡二叉树每个结点的平衡因子只能是1,0,-1。若其绝对值超过1,则该二叉排序树就是不平衡的。
    如图所示为平衡树和非平衡树示意图:



     

    RBT 红黑树

    AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多;
    红黑是弱平衡的,用非严格的平衡来换取增删节点时候旋转次数的降低;
    所以简单说,搜索的次数远远大于插入和删除,那么选择AVL树,如果搜索,插入删除次数几乎差不多,应该选择RB树。

    红黑树上每个结点内含五个域,color,key,left,right,p。如果相应的指针域没有,则设为NIL。
    一般的,红黑树,满足以下性质,即只有满足以下全部性质的树,我们才称之为红黑树:
    1)每个结点要么是红的,要么是黑的。
    2)根结点是黑的。
    3)每个叶结点,即空结点(NIL)是黑的。
    4)如果一个结点是红的,那么它的俩个儿子都是黑的。
    5)对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
    下图所示,即是一颗红黑树:






     

    B-

           是一种平衡多路搜索树(并不是二叉的):

           1.定义任意非叶子结点最多只有M个儿子;且M>2

           2.根结点的儿子数为[2, M]

           3.除根结点以外的非叶子结点的儿子数为[M/2, M]

           4.每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)

           5.非叶子结点的关键字个数=指向儿子的指针个数-1

           6.非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1]

           7.非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]

    子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;

           8.所有叶子结点位于同一层;

           如:(M=3

           B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果

    命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为

    空,或已经是叶子结点;

    B-树的特性:

           1.关键字集合分布在整颗树中;

           2.任何一个关键字出现且只出现在一个结点中;

           3.搜索有可能在非叶子结点结束;

           4.其搜索性能等价于在关键字全集内做一次二分查找;

           5.自动层次控制;

           由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少

    利用率,其最底搜索性能为:

        

           其中,M为设定的非叶子结点最多子树个数,N为关键字总数;

           所以B-树的性能总是等价于二分查找(与M值无关),也就没有B树平衡的问题;

           由于M/2的限制,在插入结点时,如果结点已满,需要将结点分裂为两个各占

    M/2的结点;删除结点时,需将两个不足M/2的兄弟结点合并;

     

     

    B+

           B+树是B-树的变体,也是一种多路搜索树:

           1.其定义基本与B-树同,除了:

           2.非叶子结点的子树指针与关键字个数相同;

           3.非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树

    B-树是开区间);

           5.为所有叶子结点增加一个链指针;

           6.所有关键字都在叶子结点出现;

           如:(M=3

       B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在

    非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;

           B+的特性:

           1.所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好

    是有序的;

           2.不可能在非叶子结点命中;

           3.非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储

    (关键字)数据的数据层;

           4.更适合文件索引系统;比如对已经建立索引的数据库记录,查找10<=id<=20,那么只要通过根节点搜索到id=10的叶节点,之后只要根据叶节点的链表找到第一个大于20的就行了,比B-树在查找10到20内的每一个时每次都从根节点出发查找提高了不少效率。

      

    B*

           B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;

       B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3

    (代替B+树的1/2);

           B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据

    复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父

    结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;

           B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分

    数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字

    (因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之

    间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;

           所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

      

    小结

           B树:二叉树,每个结点只存储一个关键字,等于则命中,小于走左结点,大于

    走右结点;

           B-树:多路搜索树,每个结点存储M/2M个关键字,非叶子结点存储指向关键

    字范围的子结点;

           所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;

           B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点

    中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;

           B*树:在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率

    1/2提高到2/3


    B+/B*Tree应用

    数据库索引--索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。



    数据库索引--表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键。



    倒排索引--也可以由B树及其变种实现但不一定非要B树及其变种实现,如lucene没有使用B树结构,因此lucene可以用二分搜索算法快速定位关键词实现时,lucene将下面三列分别作为词典文件(Term Dictionary)、频率文件(frequencies)、位置文件 (positions)保存。其中词典文件不仅保存有每个关键词,还保留了指向频率文件和位置文件的指针,通过指针可以找到该关键字的频率信息和位置信息。   

    [java]  view plain  copy
    1. 关键词            文章号[出现频率]              出现位置     
    2. guangzhou           1[2]                      36     
    3. he                  2[1]                      1     
    4. i                   1[1]                      4     
    5. live                1[2]                      25,   
    6.                     2[1]                      2     
    7. shanghai            2[1]                      3     
    8. tom                 1[1]                      1  


    参考文章

    B-树和B+树的应用:数据搜索和数据库索引 http://blog.csdn.net/hguisu/article/details/7786014

    B树、B-树、B+树、B*树 http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html

    展开全文
  • 如何判断一棵二叉树完全二叉树

    千次阅读 2015-05-25 09:23:52
    完全二叉树(Complete Binary Tree): 设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) ...在广度优先遍历的时候,如果是满二叉树,或者完全二叉树,这些空洞是在广度优先的遍历的末尾,所以,但我们遍历到空洞的
  • 鉴别完全二叉树

    2020-05-05 10:44:46
    一颗 k 层 n 个节点的完全二叉树,和 k 层的满二叉树按层序遍历的前 n 个节点形状一致。所以,一颗完全二叉树中的任何节点如果有右儿子,那么一定有左儿子。且层序遍历时,一旦出现空节点,后续节点必定全为空。可以...
  • 完全二叉树的定义如下:二叉树只有最下层和次下层存在叶子结点,并且最下层的叶子结点只能集中在该层最左边的位置,显然,满二叉树也是完全二叉树。   那该如何判断一棵二叉树是否为完全二叉树呢?任意一棵二叉树...
  • 二叉树 二叉树:二叉树是每个节点最多有两个子树的树结构; 是n(n>=0)个结点的有限集合,它或者是空树(n=0),或者是由一个根结点及两颗互不相交的、...树中所含的n个节点和满二叉树中编号为1至n的节点一一对应
  • 完全二叉树的判断

    千次阅读 2018-11-25 19:14:44
    判断一棵树是否为完全二叉树 1)用递归算法写,左子树的层数永远和右子树的层数永远相同或者左子树层数比右子树层数一为完全二叉树,后经检验发现,某些二叉树满足要求但却不满足完全二叉树的要求,还需要考虑倒数...
  • 完全二叉树的权值

    2020-10-16 15:59:23
    给定一棵包含 N 个节点的完全二叉树,树上每个节点都有一个权值,按从 上到下、从左到右的顺序依次是 A1, A2, · · · AN,如下图所示: 现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的节点 权值之...
  • 完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 一棵二叉树...
  • 判断一棵二叉树是否为完全二叉树

    千次阅读 2018-08-23 14:48:04
    * 完全二叉树:除叶子节点外的节点都包含左右节点,此为满二叉树;不为满二叉树,但是叶子节点都集中在左边,没有节点存在有右子树但是没有左子树的情况,也为完全二叉树 * 所以要判断的情况: * 1、一个节点有右...
  • 完全二叉树只能是同深度的满二叉树缺少最后一层倒数连续个叶子结点。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该...
  • java遍历完全二叉树

    2017-05-12 09:16:40
    java 遍历 二叉树 按层 非递归 递归
  • 数据结构之判断一棵树是否为完全二叉树
  • 二叉树

    2020-07-01 17:24:08
    满二叉树7. 完全二叉树8. 完全二叉树的性质测试题9. 构建二叉树10. 二叉树的遍历前序遍历中序遍历后序遍历层序遍历11. 遍历的应用树状打印二叉树计算二叉树的高度判断一棵树是否为完全二叉树翻转二叉树重建二叉树 1...
  • 完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。 示例: ...
  • //完全二叉树指最后一层叶子结点,它的左边为满,右边可以不未满。 利用层级遍历,第一个为空,标记下。余下的不可以在有node. public static bool IsCompletedBinTree(Node h) { bool isNullMeet = false; ...
  • 完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。 示例: 输入:...
  • 平衡二叉树:判断条件1)左树是否平衡2)右树是否平衡 3)高度 左树右树相差高度不大于1   public static boolean isBalance(Node head){ if(head==null) return true; if(Math.abs(getHeight(head....
  • 分析:我们都知道完全二叉树是指最后一层左边是的,右边可能慢也不能不满,然后其余层都是的,根据这个特性,利用层遍历, 如果我们当前遍历到了NULL结点即叶结点,那么后续如果还有非叶结点,就说明是

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,730
精华内容 5,092
关键字:

完全二叉树必为满二叉树