蔡明志数据结构java版 第1 0章.ppt

《蔡明志数据结构java版 第1 0章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第10章B树10.1m-way查找树10.2B树10.3程序集锦10.4思考题110.1m-way查找树一棵m-way查找树，所有结点的度（degree）均小于或等于m，若T为空树，则T也称为m-way查找树，倘若T不是空树，则必须具备以下的性质：（1）结点的形式是n,A0,(K1,A1),(K2,A2),…,(Kn,An)，其中Ai是子树的指针，0≤i≤n，n为结点上的关键字个数，Ki是关键字，1≤i≤n；1≤n

2、+1，0≤i≤n。（4）子树An的所有关键字均大于Kn。（5）Ai指到的子树，0≤i≤n，也是m-way查找树。310.1m-way查找树10.1.1m-way查找树的增加10.1.2m-way查找树的删除410.1.1m-way查找树的增加为了简化起见，假设有一棵m为3的查找树，此为3-way查找树。请依次将关键字5,7,12,6,8,4,3,10加入到查找树，其中×表示目前没有关键字存在，如图所示。510.1.2m-way查找树的删除而在删除方法上则与二叉查找树极为相似，若删除非叶结点上的关键字，则以左子树中最大的关键字或右子树中的最小关键字取代，如有

3、一棵3-way的查找树如图所示。610.1.2m-way查找树的删除一次删除3、8、12、7、10，具体过程如图所示。7练习题1.试将关键字30、50、25、32、35、33、28、29、60依次加入到3-way查找树。2.将练习题1所建立的3-way查找树中依次删除28、35及50。810.2B树一棵阶数为m的B树是一棵m-way查找树。若是空树，也算B树，假若高度≥1必须满足以下的特点：（1）根至少有两个子结点（childrennode），即结点内至少有一个关键字（keyvalue）。（2）除了根外，所有非叶结点（即内部结点）至少有个子结点，至多有m个

4、子结点。这表示至少应有–1个关键字，至多有m–1个关键字（表示大于m/2的最小正整数）。（3）所有的叶结点都在同一层。910.2B树10.2.1B树的增加10.2.2B树的删除1010.2.1B树的增加从B树中开始查找，假设加入的关键字X在B树中找不到，则加入B树中，假设加入P结点，若该结点少于m–1个关键字，则直接加入；若该结点的关键字已等于m–1，则将此结点一分为二，因为一棵order为m的B树，最多能有m–1个关键字。1110.2.2B树的删除B树的删除分成两种：一为删除的结点是叶结点（leafnode），二为删除的结点为非叶结点（non-leafn

5、ode）。12练习题有一棵5阶B树，如图所示。试回答下列问题：1.依次加入33、36及38之后的B树是怎样的?2.接练习题1得到的结果，依次删除105和110。1310.3程序集锦建立一棵m-way树来处理数据1410.4思考题1．什么是B树，其与AVL树有什么差异？2．请写明二叉查找树与m-way查找树之间的区别。3．请写出B树插入及删除关键字的算法。4．若有一3阶B树，如图所示，删除关键字60后，其结果为何？1510.4思考题16