二叉查找树、平衡树和B-树.ppt

《二叉查找树、平衡树和B-树.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二叉排序树BST(二叉搜索树)1.定义二叉排序树或者是空树，或者是满足如下性质的二叉树：1)若其左子树非空，则左子树上所有结点的值均小于根结点的值；2)若其右子树非空，则右子树上所有结点的值均大于等于根结点的值；3)其左右子树本身又各是一棵二叉排序树。2.性质中序遍历一棵二叉排序树，将得到一个以关键字递增排列的有序序列4524531228903.在二叉排序树上的操作1)查找例：在如下二叉排序树中查找关键字为24的记录。455310061907812337242445继续在左子树中查找2412继续在右子树中查找2437继续在左

2、子树中查找Key=24查找成功！例在如下二叉排序树中查找关键字为60的记录45531006190781233724查找失败！```查找路径左子树为空查找算法的一种递归实现BiTreeSearchBST(BiTreeT,KeyTypekey，BiTree&f){//二叉排序树用二叉链表存储。在根指针T所指二叉排序树中递归地查找关键字等于key的记录，若查找成功，则返回该记录结点的指针，否则返回空指针if(!T)

3、

4、EQ(key,T->data.key)return(T);//T为空或查找成功,返回elseifLT(key,T->da

5、ta.key){//在左子树中继续查找f=T;return(SearchBST(T->lchild,key,f));}//在右子树中继续查找f=T;return(SearchBST(T->rchild,key,f))}//SearchBST本算法利用先序遍历，f是被找到的那个结点的父结点，其初始调用值为NULL。性能分析：二叉排序树的查找效率与树的形态有关，若树的形态为“单枝”，二叉排序树的查找就“退化”为顺序查找；若树的形态比较“平衡”，二叉排序树的查找与二分查找类似；6190100534578123372445531006

6、190781233724查找算法的一种非递归实现BiTreeSearchBST(BiTreeT,KeyTypekey，BiTree&f){//二叉排序树用二叉链表存储。在根指针T所指二叉排序树中查找关键字等于key的记录，若查找成功，则返回该记录结点的指针，否则返回空指针f=NULL;p=T;while(!p){if(EQ(key,p->data.key)return(p);//查找成功,返回ifLT(key,p->data.key){f=p;p=p->lchild;//在左子树中继续查找}else{f=p;p=p->rch

7、ild}//在右子树中继续查找}//whilereturn(NULL);//T为空}//SearchBST2)插入插入一定发生在叶结点上插入操作可生成一棵二叉树。InsertBST()61901005345781233724插入算法：在查找不成功时插入StatusInsertBST(BiTree&T,ElemTypee){//当二叉排序树T中不存在关键字等于e.key的记录时，插入e并//返回TRUE，否则返回FALSE.if(!SerchBST(T,e.key,NULL){s=(BiTree)malloc(sizeof(BiTN

8、ode));s->data=e;s->lchild=s->rchild=NULL;if(!T)T=s;elseifLT(e.key,f->data.key)f->lchild=s;elsef->rchild=s;returnTRUE;}elsereturnFALSE;}//InsertBST本算法假设在查找过程中已确定插入位置为f插入算法：在插入点不确定时插入StatusInsertBST(BiTree&T,BiTrees){//将指针S所指结点插入到以T为根的二叉树排序树中.if(!T)T=s;elseifLT(s->data

9、.key,f->data.key)InsertBST(T->lchild,s);elseInsertBST(T->rchild,s);returnOK;}//InsertBST3)生成算法步骤:反复执行以下操作a.读入一个记录，设其关键字为K；b.调用SerchBST()，确定插入位置；c.调用InsertBST()，实施插入结点的操作；4)删除53[例]20901050869541241528891304587899239(1)(2)(2)(3)被删除结点的不同情况分析：p^是叶子结点：修改其双亲指针即可p^只有左孩子：用

10、p^的左子树代替以p^为根的子树p^只有右孩子：用p^的右子树代替以p^为根的子树p^有两个孩子：找到p^的中序后继(或前趋)结点q^，q^的数据复制给p^，删除只有右孩子(或左孩子)/无孩子的q^4.性能分析给定树的形态，等概率查找成功时的ASL