Chapter11-1-二叉搜索树-2学时

LOGO2011/10/211Chapter11Chapter11搜索树搜索树中国地质大学信息工程学院中国地质大学信息工程学院LOGO2011/10/21211.111.1二叉搜索树二叉搜索树11.2AVL11.2AVL树树11.311.3红黑树红黑树11.4B11.4B--树树11.511.5应用应用内容提要内容提要LOGO2011/10/213查找表的分类静态查找表仅作查询和检索操作的查找表。常用方法：顺序查找：无序表、有序表折半查找：有序表分块查找：索引顺序表动态查找表在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。哈希查找表又叫散列查找，利用哈希函数进行查找的过程LOGO2011/10/21411、搜索树简介、搜索树简介可用于描述字典的数据结构：可用于描述字典的数据结构：nn个元素个元素跳表：进行搜索、插入或者删除操作所需要的平跳表：进行搜索、插入或者删除操作所需要的平均时间为均时间为O(logn)O(logn)，而最坏情况下的时间为，而最坏情况下的时间为O(n)O(n)；；散列：平均和最坏时间分别为散列：平均和最坏时间分别为O(1)O(1)和和O(n)O(n)，可适，可适用于根据元素关键值进行的操作；用于根据元素关键值进行的操作；两者比较：使用跳表很容易对字典元素进行高效两者比较：使用跳表很容易对字典元素进行高效的顺序访问（如按照升序搜索元素），而散列却的顺序访问（如按照升序搜索元素），而散列却做不到这一点。做不到这一点。LOGO2011/10/215搜索树的引入搜索树的引入平衡搜索树平衡搜索树：对一个：对一个nn元素的字典进行搜索、插入元素的字典进行搜索、插入或者删除所需要的平均和最坏时间均为或者删除所需要的平均和最坏时间均为O(logn)O(logn)；；并且所有字典元素能够在线性时间内按升序输出。并且所有字典元素能够在线性时间内按升序输出。在搜索树中进行顺序访问时，搜索每个元素所需要在搜索树中进行顺序访问时，搜索每个元素所需要的平均时间为的平均时间为O(1)O(1)。。搜索树既适用于根据元素关键值的操作，也适用于搜索树既适用于根据元素关键值的操作，也适用于不按精确的关键值匹配进行字典操作的应用（比如不按精确的关键值匹配进行字典操作的应用（比如寻找关键值大于寻找关键值大于kk的最小元素）。的最小元素）。LOGO2011/10/21622、二叉搜索树、二叉搜索树散列无法提供较好性能的一些操作：散列无法提供较好性能的一些操作：按关键值的升序输出字典元素：按关键值的升序输出字典元素：O(D+nlogn)O(D+nlogn)按升序找到第按升序找到第kk个元素：个元素：O(n)O(n)删除第删除第kk个元素：个元素：O(n)O(n)相应平衡搜索树的操作复杂度：相应平衡搜索树的操作复杂度：按关键值的升序输出字典元素：按关键值的升序输出字典元素：O(n)O(n)按升序找到第按升序找到第kk个元素：个元素：O(logn)O(logn)删除第删除第kk个元素：个元素：O(logn)O(logn)LOGO2011/10/217（（11）二叉搜索树（）二叉搜索树（BSTBST）的定）的定义义1)1)每个元素有一个关键值，并且没每个元素有一个关键值，并且没有任意两个元素有相同的关键值；有任意两个元素有相同的关键值；因此因此所有的关键值都是唯一所有的关键值都是唯一的。的。2)2)根节点根节点左子树左子树的关键值（如果有的关键值（如果有的话）的话）小于小于根节点的关键值。根节点的关键值。3)3)根节点根节点右子树右子树的关键值（如果有的关键值（如果有的话）的话）大于大于根节点的关键值。根节点的关键值。4)4)根节点的根节点的左右子树左右子树也都是二叉搜也都是二叉搜索树。索树。39393434882323111168684646757571718686二叉搜索树（二叉搜索树（binarysearchtreebinarysearchtree）是一棵可能为空）是一棵可能为空的二叉树，一棵非空的二叉搜索树满足以下特征：的二叉树，一棵非空的二叉搜索树满足以下特征：中序遍历该树可以按从小中序遍历该树可以按从小到大的顺序将各个结点的关到大的顺序将各个结点的关键值排列起来。键值排列起来。LOGO2011/10/218二叉搜索树二叉搜索树--示例示例非二叉搜索树非二叉搜索树二叉搜索树二叉搜索树••有重复值的二叉索引树（有重复值的二叉索引树（DBSTDBST）：）：==、、==LOGO2011/10/219带索引的二叉搜索树带索引的二叉搜索树在每个节点中添加一个在每个节点中添加一个LeftSizeLeftSize域。这个域的值是域。这个域的值是该节点该节点左子树的元素个数加左子树的元素个数加11。。••LeftSizeLeftSize同时给出了一个元素在子树中的排名。同时给出了一个元素在子树中的排名。LOGO2011/10/2110（（22））BSTBST的抽象数据类型的抽象数据类型抽象数据类型抽象数据类型BSTree{BSTree{操作操作::Create()Create()：创建一个空的二叉搜索树：创建一个空的二叉搜索树SearchSearch(k,e)(k,e)：将：将关键值关键值为为kk的元素返回到的元素返回到ee中；中；如果操作失败则返回如果操作失败则返回falsefalse，否则返回，否则返回truetrueInsertInsert(e)(e)：将元素：将元素ee插入到搜索树中插入到搜索树中DeleteDelete(k,e)(k,e)：删除关键值为：删除关键值为kk的元素并且将其返回到的元素并且将其返回到ee中中Ascend()Ascend()：按照关键值的升序排列输出所有元素：按照关键值的升序排列输出所有元素}}LOGO2011/10/2111带索引的带索引的BSTBST--ADTADT描述描述抽象数据类型抽象数据类型IndexedBSTree{IndexedBSTree{操作：操作：Create()Create()：产生一个空的带索引的二叉搜索树：产生一个空的带索引的二叉搜索树Search(k,e)Search(k,e)：将关键值为：将关键值为kk的元素返回到的元素返回到ee中；中；IndexSearch(k,e)IndexSearch(k,e)：将：将第第kk个元素个元素返回到返回到ee中中Insert(e)Insert(e)：将元素：将元素ee插入到搜索树插入到搜索树Delete(k,e)Delete(k,e)：删除关键值为：删除关键值为kk的元素且将其返回到的元素且将其返回到ee中中IndexDelete(k,e)IndexDelete(k,e)：删除：删除第第kk个元素个元素并将其返回到并将其返回到ee中中Ascend()Ascend()：按照关键值的升序排列输出所有元素：按照关键值的升序排列输出所有元素}}LOGO2011/10/2112（（33））BSTBST的类定义的类定义templateclassE,classKtemplateclassE,classK元素，关键值元素，关键值classBSTree:publicBinaryTreeEclassBSTree:publicBinaryTreeE{{public:public:boolboolSearchSearch(constK&k,E&e)const;(constK&k,E&e)const;BSTreeE,K&BSTreeE,K&InsertInsert(constE&e);(constE&e);BSTreeE,K&BSTreeE,K&DeleteDelete(constK&k,E&e);(constK&k,E&e);voidAscend(){InOutput();}voidAscend(){InOutput();}中序升序输出中序升序输出};};LOGO2011/10/2113（（44））BSTBST--搜索搜索【【思想思想】】假设需要查找假设需要查找关键值为关键值为kk的元素，先从的元素，先从根开始。如果根为空，那么搜索树不包含任何元根开始。如果根为空，那么搜索树不包含任何元素，查找失败，否则将素，查找失败，否则将kk与根的关键值相比较：与根的关键值相比较：如果如果kk小于小于根节点的关键值，则只需在左子树根节点的关键值，则只需在左子树中搜索即可；中搜索即可；如果如果kk大于大于根节点的关键值，则只需在右子树根节点的关键值，则只需在右子树中搜索即可；中搜索即可；如果如果kk等于等于根节点的关键值，则查找成功，搜根节点的关键值，则查找成功，搜索终止！索终止！演示演示LOGO2011/10/2114BSTBST--搜索代码搜索代码templateclassE,classKtemplateclassE,classKboolBSTreeE,K::Search(constK&k,E&e)constboolBSTreeE,K::Search(constK&k,E&e)const{{BinaryTreeNodeE*p=root;BinaryTreeNodeE*p=root;while(p)while(p)if(kpif(kp--data)p=pdata)p=p--LeftChild;LeftChild;elseif(kpelseif(kp--data)p=pdata)p=p--RightChild;RightChild;else{else{e=pe=p--data;data;returntrue;}returntrue;}returnfalse;returnfalse;}}该算法的时间复杂性为该算法的时间复杂性为O(h)O(h)，，其中其中hh为树的高度为树的高度LOGO2011/10/2115（（55））BSTBST--插入插入思想：若在二叉搜索树中插入一个新元素思想：若在二叉搜索树中插入一个新元素ee，首先，首先要验证要验证ee的关键值与树中已有元素的关键值是否相的关键值与树中已有元素的关键值是否相同（采用同（采用BSTBST搜索算法）。搜索算法）。如果搜索不成功，则新元素将被插入到搜索的如果搜索不成功，则新元素将被插入到搜索的中断中断点点。。过程演示过程演示LOGO2011/10/2116BSTBST--插入代码插入代码templateclassE,classKtemplateclassE,classKBSTreeE,K&BSTreeE,K::Insert(constE&e)BSTreeE,K&BSTreeE,K::Insert(constE&e){{BinaryTreeNodeE*p=root,*pp=0;BinaryTreeNodeE*p=root,*pp=0;while(p)while(p){{pp=p;pp=p;////记录父节点指针记录父节点指针if(epif(ep--data)p=pdata)p=p--LeftChild;LeftChild;elseif(epelseif(ep--data)p=pdata)p=p--RightChild;RightChild;elsethrowBadInput();elsethrowBadInput();////找到相同键值的元素找到相同键值的元素}}插入节点插入节点77pppp7LOGO2011/10/2117BSTBST--插入代码（续）插入代码（续）BinaryTreeNodeE*r=newBinaryTreeNodeE(e);BinaryTreeNodeE*r=newBinaryTreeNodeE(e);if(root)if(root)////非空树非空树{{if(eppif(e