注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

勇敢的劳尤条

 
 
 

日志

 
 

红黑树、B树、B+树、B*树 以及堆的科普  

2013-10-28 16:59:51|  分类: 数据结构知识积累 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

红黑树是一种自平衡二叉查找树。

那什么是二叉查找树呢?  BST
二叉排序树(Binary Sort Tree)又称二叉查找树,亦称二叉搜索树。 它或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树;
红黑树、B树、B+树、B*树 以及堆的科普 - yuanshuilee - 勇敢的劳尤条

什么是平衡二叉树呢?  AVL
平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

作用:我们知道,对于一般的二叉搜索树(Binary Search Tree),其期望高度(即为一棵平衡树时)为log2n,其各操作的时间复杂度(O(log2n))同时也由此而决定。但是,在某些极端的情况下(如在插入的序列是有序的时),二叉搜索树将退化成近似链或链,此时,其操作的时间复杂度将退化成线性的,即O(n)。



那么,我们现在就知道什么是红黑树了。红黑树,能保证在最坏情况下,基本的动态几何操作的时间均为O(lgn)。
一般的,红黑树,满足以下性质,即只有满足以下全部性质的树,我们才称之为红黑树:
1)每个结点要么是红的,要么是黑的。
2)根结点是黑的。
3)每个叶结点,即空结点(NIL)是黑的。
4)如果一个结点是红的,那么它的俩个儿子都是黑的。
5)对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

关于红黑树的其他知识,参考http://blog.chinaunix.net/uid-26575352-id-3061918.html


接下来随便介绍点B树、B+树、B*树(参考)
B-tree就是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+树、B*树 以及堆的科普 - yuanshuilee - 勇敢的劳尤条


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

B-树的特性:

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

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

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

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

       5.自动层次控制;

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

红黑树、B树、B+树、B*树 以及堆的科普 - yuanshuilee - 勇敢的劳尤条


B+树

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

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

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

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

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

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

 如:(M=3)

红黑树、B树、B+树、B*树 以及堆的科普 - yuanshuilee - 勇敢的劳尤条

B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;
B+的特性:
1.所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;
2.不可能在非叶子结点命中;
3.非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;
4.更适合文件索引系统;

B*树
B*树是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;
B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2);
B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;
B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;
所以,B*树分配新结点的概率比B+树要低,空间使用率更高;



最后讲讲堆。堆的意义就在于:最快的找到最大/最小值,在堆结构中插入一个值重新构造堆结构,取走最大/最下值后重新构造堆结构 其时间复杂度为O(logN),而其他方法最少为O(N).堆实践中用途不在于排序,其主要用在调度算法中,比如优先级调度,每次取优先级最高的,时间驱动,取时间最小/等待最长的 等等 ,分为最大堆/最小堆。
堆是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于(或不小于)其左孩子和右孩子节点的值。

堆的定义是:n个元素的序列{k1,k2,…,kn},当且仅当满足如下关系时被成为堆

    (1)Ki <= k2i 且 ki <= k2i-1        

  或 (2) Ki >= k2i 且 ki >= k2i-1 

          (i = 1,2,…[n/2])

当满足(1)时,为最小堆,当满足(2)时,为最大堆。

  若将此序列对应的一维数组堪称是一个完全二叉树,则2i和2i+1个节点分别是节点i的左右子节点。

如下为一个最大堆:

 

下面以最小堆为例说明堆的输出

 

  图1为一个最小堆,当最小节点根节点13输出后,将最后一个节点97作为根节点,移到顶端,如图2. 然后要对堆进行调整。比较此完全树的根节点与其两个子节点大小,因为27 < 38 < 97,所以27是三个节点里最小的,将节点27与根节点97交换。此时以97替代27而产生的右子树为一个新的堆,再以97为根节点,对此最小堆进行调整,同理,知道要将97与49交换,得到图3的完全树。此时以97代替49为根节点的右子树为一个新堆,再对此堆做同样的操作,因为此完全树已经是最小堆,所以可以停止操作,堆的调整完毕。此时再将根节点,对的最小值输出,并进行同样的调整,可以得到如图4的新堆。这个过程被称为“筛选”。

同样以最小堆说明堆的初始化

  从一个无序序列初始化为一个堆的过程就是一个反复“筛选”的过程。由完全二叉树的性质可以知,一个有n个节点的完全二叉树的最后一个非叶节点是节点[n/2],堆的初始化过程就从这个[n/2]节点开始。上图为如下无序数组的初始化:

    {49,38,65,97,76,13,27,50}

  首先,未处理的数组对应的堆为图1模样。从第四个节点开始([8/2]=4),因为50 < 97,故要交换两节点,交换后还要继续对其新的左子树进行类似输出后那样的筛选。易见其左子树只有节点97,已经为最佳情况,故可以继续堆的初始化,如图2。再考虑第三个节点,因为13 < 27 < 65,即节点13为当前的最小节点,故与节点65交换,并对新的左子树进行筛选,其也为最佳情况,故可继续堆的初始化,结果如图3。然后考虑第二个节点,因为38 < 50 < 76,故已经为最优情况,不用调整。最后再考虑第一个节点,根节点。因为 13 < 38 < 49,故需要将根节点49与其右孩子节点13交换,交换后还要继续对其新的右子树进行类似输出后那样的筛选,可见右子树还需要调整,因为 27 < 49 < 65,故将节点49与节点27交换。此时已经处理完了根节点,初始化结束。最终结果如图5.


  评论这张
 
阅读(855)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017