[工学]数据结构严蔚敏课件第9章.ppt

3．二叉排序树的插入算法 根据动态查找表的定义，“插入”操作在查找不成功时才进行； 二、二叉平衡树 何谓“二叉平衡树”？ 假设 m 阶 B-树的深度为 H+1，由于 第 H+1 层为叶子结点，而当前树中含有 N 个关键字，则叶子结点必为 N+1 个， N+1≥2(?m/2?)H-1 H-1≤log?m/2?((N+1)/2) H≤log?m/2?((N+1)/2)+1 由此可推得下列结果： 在含 N 个关键字的 B-树上进行一次查找，需访问的结点个数不超过 log?m/2?((N+1)/2)+1 结论： 是B-树的一种变型 四、B+树 1．B+树的结构特点： ※ 每个叶子结点中含有 n 个关键字和 n 个指向记录的指针；并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点； ※ 每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值； ※ 所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 ?m/2?和 m 之间。 2．查找过程 ※在 B+ 树上，既可以进行缩小范围的查 找，也可以进行顺序查找； ※ 在进行缩小范围的查找时，不管成功 与否，都必须查到叶子结点才能结束； ※若在结点内查找时，给定值≤Ki， 则 应继续在 Ai 所指子树中进行查找。 4） RL型(先顺时针旋转，再逆时针旋转。)  图 二叉排序树的RL型平衡旋转 RL型失衡的特点是：A-bf=-2，B-bf=1。 相应调整操作可用如下语句完成：  B=A-rchild； C=B-lchild；  B-lchild=C-rchild；  A-rchild=C-lchild；  C-lchild=A； C-rchild=B； 然后针对上述三种不同情况，修改A、B、C的平衡因子： if (S-key C-key) /* 在CL下插入S */ { A-bf=0； B-bf=-1 ； C-bf=0； } if (S-key C-key) /* 在CR下插入S */ { A-bf=1； B-bf=0 ； C-bf=0； } if (S-key ==C-key) /* C本身就是插入的新结点S */ { A-bf=0； B-bf=0 ； } 最后，将调整后的二叉树的根结点C“接到”原A处。 令A原来的父指针为FA，如果FA非空，则用C代替A做FA的左子或右子；否则，原来A就是根结点，此时应令根指针t指向C： if (FA==NULL) t=C;  else if (A==FA-lchild) FA-lchild=C;  else FA-rchild=C； 综上所述， 在一个平衡二叉排序树上插入一个新结点S时，主要包括以下三步：  （1） 查找应插位置， 同时记录离插入位置最近的可能失衡结点A（A的平衡因子不等于0）。  （2） 插入新结点S， 并修改从A到S路径上各结点的平衡因子。  （3） 根据A、 B的平衡因子， 判断是否失衡以及失衡类型， 并做相应处理。 下面给出完整算法，其中AVLTree为平衡二叉排序树类型， AVLTNode为平衡二叉排序树结点类型。 void ins-AVLtree（AVLTree *avlt , KeyType k） /*在平衡二叉排序树中插入元素k， 使之成为一棵新的平衡二叉排序树*/ { S=(AVLTree)malloc(sizeof(AVLTNode));  S-key=k; S-lchild=S-rchild=NULL;  S-bf=0;  if (*avlt==NULL) *avlt=S;  else  {  /* 首先查找S的插入位置fp， 同时记录距S的插入位置最近且 平衡因子不等于0（等于-1或1）的结点A， A为可能的失衡结点*/ A=*avlt； FA=NULL;  p=*avlt； fp=NULL while (p! =NULL) { i