《《数据结构——用C语言描述》-蔡明志-电子教案 第十章 2 3tree》由会员分享，可在线阅读，更多相关《《数据结构——用C语言描述》-蔡明志-电子教案 第十章 2 3tree（14页珍藏版）》请在金锄头文库上搜索。
1、10.1 2006,第10章 2-3 tree与2-3-4 tree,21世纪高等院校规划教材,返回总目录,10.2 2006,2-3 tree与2-3-4 tree,关于2-3 tree及其插入和删除 关于2-3-4 tree 及其插入和删除,10.3 2006,2-3 tree,2-3 Tree的概念：可以是空集合，也可以是符合下列 几项定义的非空集合： （1）2-3 Tree中的节点可以存放一组或两组数据。 （2）若节点中存放了一组数据Ldata，其必须存在左子节点与中 子节点，而且必须满足以下两个条件： - 左子节点所存放的数据键值必须小于Ldata.key。 - 中子节点存放的数据键
2、值必须大于Ldata.key。 （3）若节点中存放了两组数据Ldata与Rdata，则会存 在左子节点、中子节点与右子节点，而且必须满 足以下4个条件：,10.4 2006,2-3 tree（续）,- Ldata.keyRdata.key。 - 左子节点所存放的数据键值必须小于Ldata.key。 - 中子节点所存放的数据键值必须大于Ldata.key，小于 Rdata.key。 - 右子节点所存放的数据键值必须大于Rdata.key。 （4）树中的所有树叶节点必须为同一层次（Level）。,图10-1 符合条件（2）的2-3 Tree示意图,图10-2 符合条件（1）的2-3 Tree示意图
3、,10.5 2006,2-3 tree的插入,2-3 Tree的插入原则： 1该节点只有一组数据，则直接插入。 2该节点已存在两组数据，插入后不符合2-3 tree的定义， 因此必须将此节点一分为二，并将中间的键值往上提到 父节点。,10.6 2006,插入原则（1） 例,在图10-3中插入60，依查找结果将60插入于f节点中， 由于f节点的键值只有一个，则直接插入即可，如图 10-4所示。,图10-3 2-3 Tree示意图（英文字母表示节点的编号）,图10-4 插入60后的2-3 Tree示意图,10.7 2006,插入原则（2） 例,承（1）插入90，由于g节点已有两个键值80与85，因
4、 此必须将g节点划分为g和h两个节点，然后将85插入其 父节点c中，因为85介于80和90之间，如图10-5所示。,2-3 Tree示意图,图10-5 插入90后的2-3 Tree示意图,10.8 2006,2-3 tree的删除,2-3 Tree的删除分成两部分： 一为删除的节点是叶节点（leaf node）， 二为删除的节点为非叶节点（non-leaf node）。 2-3 Tree的删除后的结果必须符合2-3 Tree的的定义， 否则要进行调整，其操作方式和插入大同小异。,10.9 2006,2-3-4 tree定义（1）,2-3-4 Tree为2-3 Tree概念的扩充。 2-3-4
5、Tree必须符合下列定义： 12-3-4 Tree中的节点可以存放一组、两组或三组数据。 2若节点中存放了一组数据Ldata，其必须存在左子节点与左 中子节点，而且必须符合以下两个条件。 - 左子节点所存放的数据必须小于Ldata。 - 左中子节点存放的数据必须大于Ldata。 3若节点中存放了两笔数据Ldata与Mdata，则会存在左子节点、 左中子节点与右中子节点，而且必须满足以下4个条件： - Ldata.keyMdata.key。 - 左子节点所存放的数据必须小于Ldata。 - 左中子节点所存放的数据必须大于Ldata，小于Mdata。 - 右中子节点所存放的数据必须大于Mdata。
6、,10.10 2006,2-3-4 tree定义（2）,4若节点中存放了3笔数据Ldata、Mdata与Rdata，则会存在4 个子节点左子节点、左中子节点、右中子节点与右子节点， 如图10-28所示，而且必须满足以下几个条件： - LdataMdataRdata。 - 左子节点所存放的数据必须小于Ldata。 - 左中子节点所存放的数据必须大于Ldata，小于Mdata。 - 右中子节点所存放的数据必须大于Mdata，小于Rdata。 - 右子节点所存放的数据必须大于Rdata.key。 5树中的所有树叶节点必须为同一层次（Level）。,10.11 2006,2-3-4 tree定义 图,
7、图10-26 符合条件（2）的2-3-4 Tree示意图,图10-27 符合条件（3）的2-3-4 Tree示意图,图10-28 符合条件（4）的2-3-4 Tree示意图,10.12 2006,2-3-4 tree的插入和删除,2-3-4 Tree的插入和删除的操作都要符合2-3-4 Tree 的定义，否则要按照定义进行调整。 2-3-4 Tree的删除也同样可分为删除叶节点与非叶节 点两种情况。删除非叶节点的方法与2-3 Tree一样， 寻找一个叶节点的键值来取代。,10.13 2006,2-3-4 tree的删除 例,例：2-3-4 Tree删除树叶节点，如图10-36。 删除70，由于删除后d节点仍存在一个键值，故 可直接将70删除，如图10-37所示。,图10-36 2-3-4 tree示意图,图10-37 删除70后的2-3-4 tree示意图,10.14 2006,2-3-4 tree的删除 例,假设存在2-3-4 Tree，若要删除50，根据2-3-4 Tree的定义，此 时将父节点a中的左边键值40（大于30且要小于50）与b、c节点 合并于b节点，再将c节点删除；或将2-3-4 Tree示意图中a节点 的60与d节点合并。结果如下图所示。,删除50并将节点b、c合并,2-3-4 tree示意图,删除50并将节点a的60与节点d合并,
