数据结构之查找课件(编辑修改稿)

数据结构之查找课件(编辑修改稿)内容摘要：

return (search (bright,k))。 } } 非递归算法 btree treesearch (BSTree *b, int k) { BSTree *p。 p=b。 while(p!=NULL)。 { if (pdata==k) return (p)。 else if (kpdata) p=pleft。 else p=pright。 } return (NULL)。 } 二叉排序树查找分析 树型查找最坏情况时，需要的查找时间取决于树的高度，当二叉排序树接近满二叉树时，其高度为 log2n，最坏情况下查找时间为 O(log n)，与二分查找是同样数量级的；当二叉排序树为只有一个端结点的所谓“退化树”时，其高度等于 n，最坏情况下查找时间为 O(n)，与顺序查找属于同一数量级。 为了保证树型查找有较高的查找速度，我们希望该二叉树接近满二叉树，也就是希望二叉树的每一个结点的左、右子树高度尽量接近平衡，即使按任意次序不断地插入结点，也不要使此树成为退化树。 图 两个二叉排序树 45 24 53 12 37 100 12 45 24 100 53 37 在二叉排序树上插入结点 基本思想 插入结点的非递归算法 Void insertbst(BSTree *tptr,*s) /*tptr指向根 {…… /*s 指向要插入的结点 slchild=srchild=null。 If (tptr==null) { tptr=s。 return。 } else { p=tptr。 While(p!=null) { if (pkey==skey) return。 /*无需插入 q=p。 /*q记录 p的父亲 if (skey pkey) /*寻找要插入的位置 p=plchild。 else p=prchild。 } If ( skeyqkey) /*至此 ,q指向的是 qlchild=s。 /*要插入结点 s的父 else qrchild=s。 /*结点 } } 在二叉排序树上删除结点 在二叉排序树中删除一个结点后，要使剩余的结点仍为二叉排序树。 设被删除的结点为 P, 且 P为 F的左儿子（若为右儿子时，道理相同）。 1. P无儿子 删除 P, 修改有关指针 flchild=null 2. P只有一个儿子 设 P只有左儿子 Pl(或右儿子 Pr), 只要令 Pl （或 Pr ）成为 F的左儿子即可。 Flchild=plchild 或 Flchild=prchild 3. P有两个儿子时，有两种方法。 设 P的前驱为 S. （ 1）令 P的左子树成为 F的左子树， P的右子树成为 S的右子树。 Flchild=plchild。 r=prchild。 /*r为临时变量 S=flchild。 While(srchild != null) s=srchild。 S=r。 /*使 P的右子树成为 S的右子树 （ 2）使 P的前驱 S代替 P,然后删除 S. 若 S有左儿子，则用 S的左儿子代替 S的位置。 设 Q为 S的父亲。 q=p。 S=plchild。 While(srchild != null) { q=s。 S=srchild。 /*找 P左子树最右下方的结点 S } Pkey=skey。 If (q!=p) qrchild=slchild。 Else qlchild=slchild。 /*当 Q=P时， S即为 P的左儿子，此时把 S的左儿子作为 P的左儿子 平衡树 平衡树 (Balanced tree)也称为 AVL树，是由阿德尔森 — 维尔斯基和兰迪斯 (Adelsonvelskii and landis)于 1962年首先提出的。 这是一种附加了一定限制条件的二叉树。 我们定义二叉树中每一结点的左子树高度减右子树高度为该结点的平衡因子（ Balance factor），所谓平衡树，是指一个二叉树其任一结点的平衡因子值只能是 +1， 0或 1，即任一结点的左、右子树高度之差不超过 1。 如图 ，图中数字为该结点的平衡因子。 平衡树 平衡二叉树 1 1 1 1 0 0 0 1 2 0 0 1 0 不平衡二叉树 假设给平衡树某个结点的左子树插入一个新结点，且此新结点使左子树的高度加 1，我们可能会遇到以下三种情况： (1) 如果原来其左子树高度 hl与右子树高度 hr相等 ，即原来此结点的平衡因子等于 0,插入新结点后将。