基于树的查找法PPT演示课件

第八章,查找,.,基本概念基于线性表的查找法基于树的查找法计算式查找法,本章目标,.,8.3 基于树的查找法,二叉排序树平衡二叉树B树,.,定义:二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树非空，则右子树上所有结点的值均大于（或大于等于）它的根结点的值；它的左、右子树也分别为二叉排序树,二叉排序树（二叉查找树）,.,折半查找中的判定树,图例,.,本章习题4（P295）,思考,.,typedef struct node KeyType key; /主关键字的值 struct node * lchild, * rchild; /左右指针 BSTNode, *BSTree;,结构定义,.,二叉排序树的插入二叉排序树的创建二叉排序树的查找二叉排序树的删除,二叉排序树（二叉查找树）,.,已知一关键字值为key的结点S：若二叉树是空树，则S成为二叉排序树的根；若二叉树非空，则将S.key与二叉排序树根结点的关键字进行比较：if(key的值等于根结点的值)，则停止插入；else if(key的值小于根结点的值),则将S插入左子树；else if(key的值大于根结点的值),则将S插入右子树。,插入,.,注：新结点作为叶结点插入。,35,15,45,50,40,25,10,20,30,28,eg:插入新结点28,插入图例,.,输入数据，反复执行二叉排序树的插入过程,输入数据 53, 78, 65, 17, 87, 09, 81, 15 ,53,.,算法8.4插入的递归算法,void InsertBST(BSTree *bst, KeyType key)/*若在二叉排序树中不存在关键字等于key的元素，插入该元素*/ BSTree s;if (*bst = NULL)/*递归结束条件*/ s=(BSTree)malloc(sizeof(BSTNode);/*申请新的结点s*/ s- key=key; s-lchild=NULL; s-rchild=NULL; *bst=s;else if (key key)InsertBST( /*将s插入右子树*/,时间复杂度为：O(log2n),.,创建过程实质上就是反复执行插入的过程,创建,.,输入数据，创建二叉排序树的过程,输入数据 53, 78, 65, 17, 87, 09, 81, 15 ,53,.,算法8.5创建二叉排序树,void CreateBST(BSTree *bst)/*从键盘输入元素的值，创建相应的二叉排序树*/ KeyType key;*bst=NULL;scanf(%d, ,时间复杂度为：O(nlog2n),.,思考,n个结点，按不同的输入顺序组成二叉排序树最短的二叉排序树高度是？log2n(取下整数)1最长的二叉排序树高度是？n,.,根据二叉排序树的特点首先将待查关键字key与根结点关键字t进行比较，如果：key=t:则返回根结点地址；keyt:则进一步查右子树。,查找,.,查找图例,35,15,45,50,40,25,10,20,30,搜索45搜索成功,搜索28搜索失败,.,算法8.6查找的递归算法,BSTree SearchBST(BSTree bst, KeyType key)/ *在根指针bst所指二叉排序树中，递归查找某关键字等于key的元素，若查找成功，返回指向该元素结点指针否则返回空指针* / if (!bst) return NULL;else if (bst-key = key)return bst;/ *查找成功* /else if (bst-key key)return SearchBST(bst-lchild, key);/ *在左子树继续查找* /else return SearchBST(bst-rchild, key);/ *在右子树继续查找* /,.,算法8.7查找的非递归算法,BSTree SearchBST(BSTree bst, KeyType key) BSTree q;q=bst;while(q)if (q-key = key) return q; /*查找成功*/if (q-key key) q=q-lchild; /*在左子树中查找*/else q=q-rchild; /*在右子树中查找*/return NULL; /*查找失败*/,.,平均查找长度（ASL）,若查找成功，则是从根结点出发走了一条从根结点到待查结点的路径若查找不成功，则是从根结点出发走了一条从根到某个叶子结点的路径所以，二叉排序树的查找与折半查找过程类似，查找长度与树的高度有关！,.,.,.,平均查找长度（ASL）,把n个结点按各种可能的次序插入到二叉排序树中，有n!棵二叉排序树但是，平均查找长度仍然是O(log2n)。,.,与折半查找的比较,区别：折半查找对应的判定树是惟一的，而二叉排序树却不是！折半查找采用顺序存储结构，作插入、删除时，需移动大量元素；而二叉排序树则不需要。,.,删除,从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，只能删掉该结点，并且保证删除后所得的二叉树仍然满足二叉排序树的性质不变。,.,算法思想：若等删除结点不在二叉排序树中，则不做任何操作。否则，假设要删除的结点为p，结点p的双亲结点为f，并假设结点p是结点f的左孩子（右孩子的情况类似），分三种情况讨论：（1）若p为叶结点（2）若p只有左子树（或只有右子树）（3）p既有左子树，又有右子树,.,（1）若p为叶结点：则可直接删除f-lchild=NULL;free(p);,.,（2）若p只有左子树（或只有右子树）可将p的左子树（或右子树）直接改为其双亲结点f的左子树只有左子树：f-lchild=p-lchild; free(p);只有左子树：f-lchild=p-rchild; free(p);,.,（3）p既有左子树，又有右子树,17,方法1：找到p结点在中序序列中的前驱结点s， 将p的左子树改为f的左子树， 将p的右子树改为s的右子树：,.,将p的左子树改为f的左子树f-lchild=p-lchild;将p的右子树改为s的右子树s-rchild=p-rchildfress(p);,17,.,53,78,65,09,17,87,30,40,12,15,05,15,方法2：找到p结点在中序序列中的前驱结点s， 用s的值替代p结点的值， 将s删除， 原s的左子树改为s的双亲结点q的右子树。,12,.,用s的值替代p结点的值，p-key=s-key; 将s删除，free(s);原s的左子树改为s的双亲结点q的右子树。q-rchild=s-lchild;思考为什么最后只需要修改s的左子树，而不用考虑它的右子树呢？算法8.8,.,平衡二叉排序树,二叉排序树的查找与折半查找过程类似，查找长度与树的高度有关！因此，控制二叉排序树的高度在比较低的状态，对查找比较有利!,.,平衡二叉排序树(AV树),定义:平衡二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：左子树与右子树的深度之差的绝对值小于等于1；左子树和右子树也是平衡二叉排序树；,.,性质： 1. 含有n个结点的AV树的高度为O(log2n)； 2. 在含有n个结点的AV树中搜索一个元素需要为O(log2n)时间； 3. 将一个新元素插入一棵n个结点的AV树中,可得到一棵n+1个结点的AVL树，且插入所需的时间为O(log2n)； 4. 从一棵n个结点的AVL树删除一个元素,可得到一棵n-1个结点的AV树，且删除所需的时间为O(log2n)；,.,结点的平衡因子bf,定义：结点左子树深度与右子树深度之差。AV树任一结点平衡因子只能取 -1, 0, 1如果一个结点的平衡因子的绝对值大于1,则这棵二叉搜索树就失去了平衡, 不再是AV树。,.,0,0,0,0,-1,0,0,0,1,是平衡二叉搜索树,写出以下二叉树各结点的平衡因子值：左子树的深度 减 右子树的深度,.,0,1,0,-1,0,-2,0,0,0,不是平衡二叉搜索树（AV树）,2,写出以下二叉树各结点的平衡因子值：,.,以插入为例：如果在一棵平衡的二叉搜索树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。平衡化旋转有两类： 单旋转 (LL旋转和RR旋转) 双旋转 (LR旋转和RL旋转),.,什么时候采用单旋转？什么时候采用双旋转？,.,以插入为例,在插入一 个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子。如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。如果这三个结点处于一条直线上，则采用单旋转进行平衡化。如果这三个结点处于一条折线上，则采用双旋转进行平衡化。,.,16,例，输入关键码序列为 16, 3, 7, 11, 9, 26, 18, 14, 15 ，插入和调整过程如下：,0,1,0,0,-1,2,LR双旋,0,1,-1,0,1,2,右单旋,0,-1,-1,-2,-2,0,0,0,0,.,1,-2,RL双旋,0,1,1,左单旋,0,-1,1,.,LR双旋,从空树开始的建平衡二叉排序树的过程,.,LL型,书P262-图8.10(b),240,125,120,030,015,060,A-bf=2, B-bf=1,A,B,.,LL型,B=A-lchild;A-lchild=B-rchild;B-rchild=A;A-bf=0; B-bf=0;,240,125,120,030,015,060,A-bf=2, B-bf=1,A,B,.,LR型,书P264-图8.12(b),A-bf=2, B-bf=-1,280,-140,020,160,045,090,A,B,010,030,150,070,085,095,C,.,LR型,调整语句：B=A-lchild；C=B-rchild;B-rchild=C-lchild;A-lchild=C-rchild;C-lchild=B; C-rchild=A;,.,LR型,平衡因子调整：/S为新插入结点If (S-keykey) A-bf=-1; B-bf=0; C-bf=0;If (S-keyC-key) A-bf=0; B-bf=1; C-bf=0;If (S-key=C-key) A-bf=0; B-bf=0;,.,RR型,书P263-图8.11(b),-140,-225,020,030,070,-160,A-bf=-2, B-bf=-1,A,B,.,RR型,B=A-rchild;A-rchild=B-lchild;B-lchild=A;A-bf=0; B-bf=0;,A-bf=-2, B-bf=-1,.,RL型,书P265-图8.13(b),A-bf=-2, B-bf=1,180,-240,020,160,045,090,A,B,010,030,-150,070,085,095,C,.,RL型,调整语句：B=A-rchild；C=B-lchild;B-lchild=C-rchild;A-rchild=C-rlchi