《数据结构(C／C++描述)》-第8章 查找.pptVIP

8.1 基本概念 8.2 静态查找 8.3 动态查找 8.4 哈希查找 3．二叉排序树的插入算法 8.3.2 平衡二叉树 什么是平衡二叉树(Balanced Binary Tree) ? 平衡二叉树是空树,或者是具有以下性质的二叉树: 它的左子树和右子树也都是平衡二叉树并且 左子树和右子树的深度之差的绝对值不超过1 结点的平衡因子BF(Balance Factor)是 左子树的深度减去右子树的深度,它只可能是-1,0,1 平衡二叉树(也称AVL树)的深度为O(log N)(其中N为结点个数) 它的平均查找长度也是O(log N) 平衡二叉树及平衡因子举例 不平衡二叉树及平衡因子举例 二叉排序树转成平衡树示例设关键字序列为(13,24,37,90,53) 二叉排序树转成平衡树失去平衡后进行调整的4种情况 (1)单向右旋平衡处理 当在左子树上插入左结点,使平衡因子由1增至2时 (2)单向左旋平衡处理(上例从图(d)到图(e)) 当在右子树上插入右结点,使平衡因子由-1增至-2时 (3)双向旋转(先左后右)平衡处理 当在左子树上插入右结点,使平衡因子由1增至2时 (4)双向旋转(先右后左)平衡处理 当在右子树上插入左结点,使平衡因子由-1增至-2时 (例如上例从图(f)右旋到图(g)再左旋到图(h)) 算法8.5 用非递归算法描述二叉排序树的查找 ： bsnodetype *bs_search(bsnodetype *bt,keytype key) { bsnodetype *p=bt; //指针p指向根结点，有哪些信誉好的足球投注网站从根结点开始 while (p!=NULLp-key!=key) { if(keyp-key) p=p-lchild; else p=p-rchild; } return (p); } 拖骂勃堡及湾啼帕烯逾猛惫刨险绝得哗逛准愤掘弯拈调骂造健几麓惶继四《数据结构(C／C++描述)》-第8章 查找《数据结构(C／C++描述)》-第8章 查找 若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点。 其插入位置由查找过程得到。 疑僚哨龙了藏刘泉陋叫跳牛剥媳琐臭揍悍弓娘偿昨宠核其蔡国馒忧寇压阂《数据结构(C／C++描述)》-第8章 查找《数据结构(C／C++描述)》-第8章 查找 二叉排序树的插入算法（算法8.6）如下： void bs_insert (bsnodetype **bt , bsnodetype *pn) { if(*bt==NULL) *bt=pn; //如果根结点为空，就把待插结点作为根结点 else if((*bt)-keypn-key) bs_insert((*bt)- lchild,pn) ; //如果待插结点的值小于根结点，就插入到左子树中 else if((*bt)-keypn-key) bs_insert((*bt)- rchild,pn) ; //如果待插结点的值大于根结点，就插入到右子树中 } 恳盛伶巾砖崇识刹鸣来委挝滩拟老雏善泞恩西聘排讹锑恫驳即蓝伟脊篙老《数据结构(C／C++描述)》-第8章 查找《数据结构(C／C++描述)》-第8章 查找 （1）被删除的结点是叶子； （2）被删除的结点只有左子树或者只有右子树 （3）被删除的结点既有左子树，也有右子树。 4．二叉排序树的删除算法 可分 3 种情况讨论： 和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。 赚椿腾闭废尚膳俭嘛诺莉仕旨糊认眺眩骏褪滓堆表器让胰信闯箔罗记渐蔗《数据结构(C／C++描述)》-第8章 查找《数据结构(C／C++描述)》-第8章 查找 （1）被删除的结点是叶子结点 其双亲结点中相应指针域的值改为“空” （2）被删除的结点只有左子树或者 只有右子树 其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。 （3）被删除的结点既有左子树，也有右子树 以其前驱替代之，然后再删除该前驱结点 蹦邻妙就缘节途伍麦骋崩盎宵宏颁觉仿谁窖凛律蝇梳寞卵浊警锯警蜒浦卤《数据结构(C／C++描述)》-第8章