数据结构讲义9: 二进制排序树

动态搜索？？？？二进制排序树平衡二进制树B树（B +树）关键树二进制排序树？二进制排序树: 空二进制树或具有以下属性的二进制树: 如果左子树不为空，则左子树上所有节点的值小于根节点的值;如果右子树不为空，则右子树上所有节点的值大于根的值;它的左和右子树是二进制排序树. 类型定义为: typedef struct BSTNode {intkey; “关键字字段”……“其他数据字段” struct BSTNode * lchild，* rchild; ∥左右子指针} BSTNode，* BSTree；二进制排序树示例30 12 3 18 23 71 89 53 94用于搜索71，5个二进制排序树的搜索算法假设二进制排序树的根节点指针为root且给定关键字值为K，则可以描述该搜索算法如: ①设置初始值: q =根； ②如果K = q->键，则搜索成功，算法结束； ③否则，如果用K 键，并且q的左子树不为空，则将q的左子树根发送给q，转步骤②；否则，搜索失败，算法结束； ④否则，如果K＞ q －>键，且q的右子树不为空，则将q的右子树根发送给q，进入步骤②；否则，搜索将失败，算法将结束.

二进制排序树搜索递归算法int Bstree ::搜索（关键字类型K）{int flag = 0; BstNode * q =根； while（（q！= NULL）&&（flag == 0））{if（q-> key == K）{cout <<“找到成功，找到: ” << q-> key << endl; flag = 1;}否则，如果（K 键）q = q-lch; elseq = q-> rch;} if（flag == 0）cout <<“搜索失败，没有这样的节点！\ n”;在函数搜索中，参数root是根节点指针，K是期望查找的键值（假设此处为整数）. 执行完该函数后，如果搜索成功，则输出找到的节点的关键字值，指针q指向找到的节点，指针p指向其父节点；如果搜索失败，则q = NULL，p是q节点指针的父级. 二进制排序树搜索非递归算法BSTree SearchBST2（BSTree t，int k）{//二进制排序树t非递归地找到键等于k的数据元素，//如果搜索成功，它将返回到数据元素节点的指针，//否则返回空指针p = t; while（p！= NULL && p-> key！= K）{if（（k key）p = p-> lchild; else p = p-> rchild;} return p;} // SearchBST2二进制排序树上节点的插入步骤: （1）如果二进制排序树是空树，则k成为二进制排序树的根； （2）如果二进制排序树不为空，则将k与二进制排序树的根进行比较，如果k的值等于根节点的值，则停止插入；如果k的值小于根节点的值，则插入k Left子树；如果k的值大于根节点的值，则将k插入右子树.

插入算法void InsertBST（BSTree t，int k）{//如果二进制排序树t中没有关键字k，则进行插入，否则直接返回p = t; // p的初始值指向根节点，而（p）//找到插入位置{if（p-> key == k）return; // k已经存在，无需插入f = p; // f保存当前搜索到的节点p =（k 键）？ p-> lchild: p-> rchild; //如果使用k 键，则在左侧子树上搜索，否则在右侧子树上搜索} p =（BSTree）malloc（sizeof（BSTNode））; p->键= k; p-> lchild = p-> rchild = NULL;如果（t == NULL）t = p;否则数据结构二叉排序树，如果（k 键）f-> lchild = p; else f-> rchild = p;} // InsertBST二进制排序树生成集的序列是（32,26,45,35,12,20）？ （a）32（b）26（c）32 26 35（e）45 12 26 35（f）32 45 12 20（g）26 35 32 26（d）32 453245φ记录的键序列为: 63， 90、70、55、67、42、42、98、83，然后构造一个二进制排序树的过程如下: 63 63 63 63 63 90 90 70 63 55 90 70 42 55 70 63 90 98 42 55 70 905 570 905 570 63 90 98 67 904 267 676 783删除二进制排序树上的节点. 假设要删除的节点是* p，节点* p的父节点是* f，并假设该节点是* p *节点（类似于右子节点的情况）f左子节点.

在三种情况下讨论以下内容: ①如果* p是叶节点，则可以直接将其删除: f-> 1child = NULL;免费（p）; ②如果* p节点只有左子树或只有右子树，则可以直接将* p的左子树或右子树更改为其父节点* f的左子树，即: f-> 1child = p -> 1child（或f-> 1child = p-> rchild）；免费（p）; * fF * p P P1 * fF * fF * p P *fFPrP1Pr③如果* p同时具有左子树和右子树. 然后: 让* p节点的直接前任（或直接后任）替换* p，然后从二进制排序树中删除其直接前任（或直接后任）. 当用直接前体* s替换* p时，由于* s仅具有左子树SL，因此在删除* s之后，只需将SL成为父级* r的右子树* p s * P p Q Q PR r F FRp q Q SF FR PR r RQLRsRLSQL RLSLSL删除二进制文件10或40或45或5563 55 32 10 40 43 45 58 70 90 98吗？无效删除（BSTree bst，键类型X）？ //在二进制排序树中首先，删除关键字为X的节点. {BSTree f，p = bst ;？ While（p && p-> key！= X）//查找值为X的节点？如果（p->键> X）{f = p; p = p-> lchild;}？否则{f = p; p = p-> rchild;}？ if（p == null）{printf（“没有关键字是X \ n的节点”）；退出（0）;}？ if {p-> lchild == null} //删除的节点没有左子树吗？如果（f-> lchild == p）f-> lchild = p-> rchild; //节点将被删除右子树连接到其父节点？否则f-> rchild = p-> rchild; else //被删除的节点有一个左子树{q = p; s = p-> lchild; // s指向已删除节点的左子树的根，而（s-> rchild！= null）//检查左子树中最右边的节点（顺序中的最后一个节点）{q = s; s = s-> rchild;} p->键= s->键； //如果（q == p）p-> lchild = s-> lchild;则将节点值替换为其左侧子树的最右边节点的值； //删除的节点的左子树的根节点没有右子节点，否则q-> rchild = s-> lchild; // s是已删除节点左子树中的最后一个节点？ free（s）;?}？} //算法的结尾是最好的二进制排序树？定义: 找到平均长度最小的二叉排序树.

？示例: 完整的二叉树或完整的二叉树形式的二叉排序树. ？很难构造. •折衷: 平衡二叉树. 平衡的二叉树？定义: 它是一个空的二叉树，还是该二叉树中任何节点的左右子树的高度之差的绝对值不大于1，那么该二叉树称为平衡二叉树吗？平衡因子（bf）: 节点左右子树之间的高度差是通过节点的平衡因子平衡的二叉树的示例0 1 0 -1 1-1 00 0 1 01不平衡的二叉树的示例树2 1 -1 0 0 -2 1 0 0 1 0 00平衡二叉树的类型定义typedef struct AVLNode {int key; int bf; //节点结构AVLNode的平衡因子* lchild，* rchild; //左右子指针} AVLNode，* AVLTree；构造平衡的二叉树？方法: 每当插入节点时，请首先检查树的平衡是否被破坏. 如果通过插入节点破坏了二进制排序树的平衡，则找到最小的不平衡子树. 所谓最小不平衡子树，是指最靠近插入节点的节点，并且平衡因子的绝对值大于1，因为该节点不平衡，因此该节点的祖先节点也可能不匹配平衡. 因此，在不平衡之后，应调整以该节点为根的子树.

4个不平衡的3 2 1 LL类型1 2 1 2 2 3 RR类型313的案例4个不平衡的3 1 2 LR类型1 2 1 2 3 2 RL类型313二进制平衡树插入节点（旁边的数字示例关键字的插入顺序为（15、21、27、43、36、8、11）15 15 21 15 R 21 R 27 43 15 27 15 27 21 21单词的插入顺序是（15、21、27、43、36、8、11）21 15 27 15 21 36 27 43 8 15 27 21 36 4343 36示例关键字的插入顺序是（15、21、27、43、36， 8，11）21 15 36 11 43 21 36 15 27（j）81127843（i）LL类型调整操作的2 0A1B AR BL BR A ARBBL BR S（a）插入节点S后的余额损失（b）两个示例类型调整以在调整后恢复平衡1 20120310 13102500310 1310 125025 1625163102504712504701603101628016 92892847（a）树BL，BR，AR都是空的（b）BL，BR，AR都是非空树RR类型调整操作2A -1B B BR SAL A BL BRALBL（a）失落的巴拉插入节点* s之后的时间（b）调整后RR类型调整的两个示例-1 -20 -1 -2 031031-1 0470310 0 031-1 047 -14747031 696925047025047-1 031069040694069025 764076（a）AL，BL，BR所有空树（b）AL，BL，BR均为非空树LR类型调整操作图2A-10B BL CL S CCAR0 0BACRBL CL CR AR（a）插入节点* s失去平衡后进行LR类型调整的三个示例（ b）调整后恢复平衡1 2 0 1 2 0310 -1310280310 0 -1310 028-12525025 2831025047025147025031016 0281602816264726（a）LR（0）类型调整（b）LR（L）类型LR类型调整调整的三个示例1 2 0310 0 -1310 1280250 047025-1470 25031016 0281628016 303047（c）LR（R）类型调整RL类型调整操作图A AL BCA BR CR AL B BRCCL SCL CR（a）插入节点* s之后失去平衡（b）以下三个示例调整后的RL类型调整-1 -2 0 -1 -2 0310311 0400 0310 0311 040-147047 403147250470251470 031047040 069040 3669253669（a）RL（0）典型e调整（b）RL（L）类型调整RL类型调整的三个示例-1-20310 0 0311 140025047025-1470 031047040 06940069 43254369（c）RL（R）类型调整是在AVL树上插入节点吗？插入节点后，如果平衡二叉树失去平衡，是否有必要找到最小的不平衡子树？插入树后，修改相关节点的平衡因子？如何判断根子树是否失衡？如果不平衡，则需要进行相应处理. AVL树搜索和分析？深度为h的平衡二叉树中的最小节点数.

？令Nh代表深度为h的平衡二叉树中的最小节点数. •N0 = 0，N1 = 1，N2 = 2，并且Nh = Nh-1 + Nh-2 +1. 可以通过归纳证明，当h≥0时，Nh = Fh + 2-1. •具有n个节点的平衡二叉树的最大深度，即在AVL上搜索的时间复杂度为O（登录）. B树？拜耳在1970年提出B树吗？多路平衡外部搜索树. B树？上面讨论的搜索方法适用于组织较小的数据，并且可以存储在内存中. 这是一种内部搜索方法. B树是一种平衡的，有序的，多路动态搜索树，它是磁盘. 一种文件系统索引技术中常用的数据结构类型，例如磁盘管理系统中的目录管理和数据文件中的索引机制通常使用B树的定义？ M / 2？ B树–（1）树中的每个节点最多具有m个子树； （2）如果根节点不是叶节点，则至少有两个子树； （3）除根节点外，所有非终端节点都至少有一个子树； （4）所有非终端节点均包含以下信息数据（n，P0，K1，P1，K2，P2，...，Kn，Pn），其中: Ki（i = 1，...，n）为关键字And Ki

–（5）所有叶节点都出现在同一级别上，并且没有任何信息（可以将其视为外部节点或无法找到的节点. 实际上，这些节点不存在，指向这些节点nodes指针为空）. •满足以下特征的m级B树或空树或m元树: 502 386 345 301 375 363 487 487 456 419cB树示例i336 320 317 294 281 281 273jk890 782 613 568256223 177 162f154 071121 109ed058 024 016b搜索5阶B树g haB树？搜索过程包括两个基本操作: （1）搜索沿指针的节点； （2）按节点顺序搜索关键词；搜索算法Tree SearchBTree（BTree t，int k，int * pos）{//在B树中找到关键字k，并在成功时返回节点地址和k在其中的位置* pos，如果失败则返回NULL， t->键[0] = k; //设置前哨，并按以下顺序搜索（i = t-> keynum; k key [i]; i--）;的键[1..keynum]； //如果是（i> 0 && t-> key [i] == k），则查找从后到前的第一个小于或等于k的关键字//搜索成功，返回t和i {* pos = i ; return t;} //节点内搜索失败，但t->键[i] 键[i + 1]如果（！t-> son [i]）// * t是叶子，如果没有找到k，则搜索过程失败，返回NULL； DiskRead [t->儿子[i]]； //从磁盘读取下一个搜索到的树节点到内存中，返回SearchBTree（t-> son [i]，k，pos）; //递归继续搜索子树t-> son [i]} // SearchBTreeB树搜索分析？在包含N个关键字的B树中在Internet上搜索时，从根节点到该关键字所在的节点的路径中涉及的节点数不超过？不行1 ？？登录？ M 2 ??? 2 ??如果N = 1,999,999，m = 199，则为1，搜索次数最多为4.

？米/ 2？ B树搜索长度分析？第一层至少有一个节点；第二层至少有2个节点；第三层至少有2 *？米/ 2？节点……等等？ L + 1层至少具有2 *（？M / 2？）个L-1节点;并且L + 1层的节点是叶节点，数目为N + 1 ；？ N + 1> = 2 *（？M / 2？）L-1 ;?那是L <= log？ M / 2？ （（N +1）/ 2）+1. 附件: S = N +1的推导假设B树的一个节点的子树数为Ci，则该节点的关键字数Ni = Ci1. 对于具有k个节点的B树，存在吗？ ∑Ni = ∑（Ci-1）= ∑Ci-k（1≤i≤k）（1）？因为B树上的关键字数是∑Ni = N（1≤i≤k）（2）？ B树上子树的数量可以如下计算: 每个节点（根节点除外）是一个子树，叶（子树）的数量是S；然后？ ∑Ci =（k-1）+ S（1≤i≤k）（3）？综合（1）（2）（3），有s = n + 1. B树插入？插入操作首先需要通过搜索找到插入位置，然后可以根据以下三种情况进行处理: 情况1: 插入关键字的节点后，关键字的数量不超过m-1，即给定的关键字插入到节点的相应位置，并完成了插入过程.

情况2: 在插入关键字的节点之后，在关键字数量超过m-1之后，将执行拆分处理. 假设当前处理的节点由q指向，用？ M / 2？作为边界，节点* q分为两个节点，第一个？ M / 2？ -1关键字仍然部分由q指向，其余部分由q1指向，关键字K？ M / 2？在中间，使用指针ql将其“压缩”到父节点. 方案3: 执行方案2的“压缩”过程后，父节点中的关键字数也超过m-1，则必须将父节点用作当前节点以执行相同的处理，这也意味着继续“压缩”直到根节点. 一旦根节点中的关键字数超过m-1，则在分割根节点后，将插入节点分割后数据结构二叉排序树，整个B树的层数将增加一层. 插入后: M，P0，（K1，P1，），…，（Km，Pm）; Ki

如果该节点是最低的非终端节点，并且其中的关键字数量不少于？ m / 2？，删除完成. 否则，必须执行“合并”节点的操作. 如果delete关键字不是最低的非终端节点Ki，则可以将最小的关键字y指向Pi和Ki指向的子树中的最低的非终端节点，然后指向该节点中的相应Remove Ki. 因此，仅需要讨论在最低的非终端节点中删除关键字的情况. 可以在三种情况下处理: 情况1: 删除的关键字所在节点中的关键字数量不少于？ M / 2 ?，则只需从节点删除关键字K，并删除相应的指针Pi，树的其余部分不变. B树删除场景2: 删除的关键字所在节点中的关键字数量等于？ M / 2？和节点？ M / 2？ -1，则与他的兄弟（或左兄弟）相邻的右兄弟（或左兄弟）的数量大于年轻节点中最小（或最大）的关键字的数量. 移到父节点，并且父节点小于（或大于）并在其旁边. 将关键字的关键字下移到已删除关键字所在的节点. 情况3: 已删除关键字所在的节点及其相邻的同级节点中关键字的数量等于？ M / 2？ -1. 假定该节点有一个右兄弟，并且其右兄弟节点由父节点中的指针Pi指向，则在删除关键字之后，删除其所在节点中的其余关键字和指针以及父节点关键字k一起合并到Pi指向的右兄弟节点中（如果没有右兄弟，它们将合并到左兄弟节点中. ）

a bB树删除操作示例56 cb 72 h 69 83 a 56 cg 40 21 35 72 defgh 18 69 83 30 4018 35d ef 21307（a）初始状态a（b）删除756 c1821 72 defg 18 35 40 69 83b21 56 35 40 72 83（c）删除30（d）删除69B +树？ B +树是B树的变体. m层B +树和m层B树之间的区别是: （1）是n子树的节点必须具有n个关键字，每个关键字对应一个子树； （2）所有叶节点都包含所有关键字的信息和指向相应记录的指针，叶节点本身遵循“关键字”的大小从小到大的顺序链接； （3）所有非叶子节点仅用作索引，节点中的每个索引项仅包含相应子树的最大或最小关键字，并指向. 子树的指针不包含对应记录的指针关键字. A三阶B +树59 9715 44 5972 9710 1521 37 4451 5963 7285 91 97

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-181239-1.html