1、 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURESChapter 7 搜索结构搜索结构 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES静态搜索结构静态搜索结构 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURESn通常称用于搜索的数据集
2、合为通常称用于搜索的数据集合为搜索结构搜索结构，它是，它是由同一数据类型的对象由同一数据类型的对象(或记录或记录)组成。组成。n在每个对象中有若干属性，其中有一个属性，在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象其值可唯一地标识这个对象,称为称为关键码关键码。n使用基于关键码的搜索，搜索结果应是唯一的。使用基于关键码的搜索，搜索结果应是唯一的。但在实际应用时，搜索条件是多方面的，可以但在实际应用时，搜索条件是多方面的，可以使用基于属性的搜索方法，但搜索结果可能不使用基于属性的搜索方法，但搜索结果可能不唯一。唯一。n实施搜索时有两种不同的环境。实施搜索时有两种不同的环境。u静
3、态环境静态环境 静态搜索表静态搜索表u动态环境动态环境 动态搜索表动态搜索表 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES定义定义 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES351545504025102030 Department of Computer Science&Technology,Nanjing University fall 2
4、009DATA STRUCTURES512345641C131332122133132123123123 132 213 231 312 321 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES#include template class BST;template Class BstNode :public BinTreeNode friend class BST;Department of Computer Science&Technology,Nanjing Univ
5、ersity fall 2009DATA STRUCTURESprotected:Type data;BstNode*leftChild,*rightChild;public:BstNode():leftChild(NULL),rightChild(NULL)/构造函数 BstNode(const Type d,BstNode*L=NULL,BstNode*R=NULL):data(d),leftChild(L),rightChild(R)void setData(Type d)data=d;Department of Computer Science&Technology,Nanjing U
6、niversity fall 2009DATA STRUCTURES Type GetData()return data;BstNode()/析构函数;template class BST :public BinaryTree private:BstNode*root;/根指针 Type RefValue;/数据输入停止的标志 void MakeEmpty(BstNode*&ptr);void Insert(Type x,BstNode*&ptr);/插入 Department of Computer Science&Technology,Nanjing University fall 200
7、9DATA STRUCTURES void Remove(Type x,BstNode*&ptr);/删除 void PrintTree(BstNode*ptr)const;BstNode*Copy (const BstNode*ptr);/复制 BstNode*Find(Type x,BstNode*ptr);/搜索 BstNode*Min(BstNode*ptr)const;/求最小 BstNode*Max(BstNode*ptr)const;/求最大public:Department of Computer Science&Technology,Nanjing University fa
8、ll 2009DATA STRUCTURES BST():root(NULL)/构造函数 BST(Type value);/构造函数 BST();/析构函数 const BST&operator=(const BST&Value);void MakeEmpty()MakeEmpty(root);root=NULL;void PrintTree()const PrintTree(root);int Find(Type x)/搜索元素 return Find(x,root)!=NULL;Type Min()return Min(root)-data;Type Max()return Max(roo
9、t)-data;Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES void Insert(Type x)Insert(x,root);/插入新元素 void Remove(Type x)Remove(x,root);/删除含x的结点有三种基本操作：有三种基本操作：查找查找插入插入删除删除 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES二叉搜索树（二叉排
10、序树）二叉搜索树（二叉排序树）对于树中的每个结点对于树中的每个结点x，它的左子树中所，它的左子树中所有关键码小于有关键码小于x的关键码，而它的右子树的关键码，而它的右子树中所有关键码大于中所有关键码大于x的关键码。的关键码。有三种基本操作：有三种基本操作：查找查找插入插入删除删除 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES351545504025102030 Department of Computer Science&Technology,Nanjing Unive
11、rsity fall 2009DATA STRUCTURES Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTUREStemplate BstNode*BST:Find(Type x,BstNode*ptr)const/二叉搜索树的递归的搜索算法 if(ptr=NULL)return NULL;/搜索失败 else if(x data)/在左子树搜索 return Find(x,ptr-leftChild);else if(x ptr-data)/在右子树搜索 return Fin
12、d(x,ptr-rightChild);else return ptr;/相等,搜索成功 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTUREStemplate BstNode *BST :Find(Type x,BstNode*ptr)const/二叉搜索树的迭代的搜索算法 if(ptr!=NULL)BstNode*temp=ptr;/从根搜索 while(temp!=NULL)if(temp-data=x)return temp;if(temp-data rightChild
13、;/右子树 else temp=temp-leftChild;/左子树 return NULL;/搜索失败 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES35154550402510203028插入新结点插入新结点28 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES Department of Computer Science&Technology,
14、Nanjing University fall 2009DATA STRUCTUREStemplate void BST:Insert(Type x,BstNode*&ptr)if(ptr=NULL)/空二叉树 ptr=new BstNode(x);/创建结点 if(ptr=NULL)cout “存储不足 endl;exit(1);else if(x data)/在左子树插入 Insert(x,ptr-leftChild);else if(x ptr-data)/在右子树插入 Insert(x,ptr-rightChild);Department of Computer Science&Tec
15、hnology,Nanjing University fall 2009DATA STRUCTURES 535378537865537865175378658717537865091787537865811787095378651517870981 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTUREStemplate BST:BST(Type value)输入数据,建立二叉搜索树。RefValue 是输入/结束标志。这个值应取不可能在输入序列中/出现的值,例如输入序列的值都是正
16、整数时,/取RefValue为0或负数。Type x;root=NULL;RefValue=value;cin x;while(x!=RefValue)Insert(x,root);cin x;Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES351545504025102030 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES基本思想：基本思想：首先查找
17、，确定被删除结点是否在二叉搜首先查找，确定被删除结点是否在二叉搜索树中。索树中。分情况讨论：分情况讨论：（删除结点为（删除结点为ptr指针所指，其双亲结点为指针所指，其双亲结点为f结点指针结点指针所指，被删除结点的左子树和右子树分别用所指，被删除结点的左子树和右子树分别用pl和和pr表表示）示）Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES5378651787092345删除45右子树空,用左子女顶替5378651787092353788817940923删除78左子树空
18、,用右子女顶替539488170923 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES8853788117940945删除782365538188179409452365在右子树上找中序下第一个结点填补 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES template void BST :Remove(const Type&x,BstNode*&pt
19、r)BstNode*temp;if(ptr!=NULL)if(x data)/在左子树中删除 Remove(x,ptr-leftChild);else if(x ptr-data)/在右子树中删除 Remove(x,ptr-rightChild);else if(ptr-leftChild!=NULL&ptr-rightChild!=NULL)Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES temp=Min(ptr-rightChild);/找ptr右子树中序下第一个结点
20、 ptr-data=temp-data;/填补上 Remove(ptr-data,ptr-rightChild);/在ptr的右子树中删除temp结点 else/ptr结点只有一个或零个子女 temp=ptr;if(ptr-leftChild=NULL)ptr=ptr-rightChild;/只有右子女 else if(ptr-rightChild=NULL)ptr=ptr-leftChild;/只有左子女 delete temp;Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTU
21、RES平衡处理平衡处理122133132123123 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES ABCABCDEDE Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES ABCABCDEDE3200001100 Department of Computer Science&Technology,Nanjing University fall 200
22、9DATA STRUCTURESABCDE1100template class AVLTree public:struct AVLNode/AVL树结点 Type data;int balance;AVLNode*left,*right;AVLNode():left(NULL),right(NULL),balance(0)AVLNode(Type d,AVLNode*l=NULL,AVLNode*r=NULL):data(d),left(l),right(r),balance(0);protected:Type RefValue;AVLNode*root;int Insert(AVLNode*
23、&Tree,Type x);void RotateLeft(AVLNode*Tree,AVLNode*&NewTree);void RotateRight(AVLNode*Tree,AVLNode*&NewTree);void LeftBalance(AVLNode*&Tree);void RightBalance(AVLNode*&Tree);int Height(AVLNode*t)const;public:AVLTree():root(NULL)AVLNode(Type Ref):RefValue(Ref),root(NULL)int Insert(Type x)return Inser
24、t(root,x);friend istream&operator (istream&in,AVLTree&Tree);friend ostream&operator (ostream&out,const AVLTree&Tree);int Height()const;12 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURESh插入插入BACEDhhh-1hhhh-1h-1ABDCEhhh-1BCEADh Department of Computer Science&Techn
25、ology,Nanjing University fall 2009DATA STRUCTUREShhACEDh-1h-1BFGEGACDBFhhh-1h插入插入 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURESFGDhAh-1CEBhhAEhhCDh-1hBFG插入插入hhACEDh-1h-1BFGEGACDBFhhh-1h Department of Computer Science&Technology,Nanjing University fall 2009DATA
26、 STRUCTUREShhh-1h-1ACEDBFGACEBFGDhhhh-1ACEDBFGhhh-1hhhh-1hACEBFGD Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES Department of Computer Science&Technology,Nanjing University f
27、all 2009DATA STRUCTURES161631633163113161611931693112691611 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES18183163167391826117326161199716147112626911 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES1518318167311714916151126
28、26149从空树开始的建树过程从空树开始的建树过程 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURESn下面的算法将通过递归方式将新结点作为叶结点插入下面的算法将通过递归方式将新结点作为叶结点插入并逐层修改各结点的平衡因子。并逐层修改各结点的平衡因子。n在发现不平衡时立即执行相应的平衡化旋转操作，使在发现不平衡时立即执行相应的平衡化旋转操作，使得树中各结点重新平衡化。得树中各结点重新平衡化。n在程序中，用变量在程序中，用变量success记载新结点是否存储分配记载新结点是否存
29、储分配成功，并用它作为函数的返回值。成功，并用它作为函数的返回值。n算法从树的根结点开始，递归向下找插入位置。在找算法从树的根结点开始，递归向下找插入位置。在找到插入位置到插入位置(空指针空指针)后，为新结点动态分配存储空间，后，为新结点动态分配存储空间，将它作为叶结点插入，并置将它作为叶结点插入，并置success为为1，再将，再将taller置为置为1，以表明插入成功。在退出递归沿插入路径向，以表明插入成功。在退出递归沿插入路径向上返回时做必要的调整。上返回时做必要的调整。Department of Computer Science&Technology,Nanjing Universit
30、y fall 2009DATA STRUCTUREStemplate int AVLTree:Insert(AVLNode*&tree,Type x,int&taller)/int success;if(tree=NULL)tree=new AVLNode(x);success=(tree!=NULL)?1:0;if(success)taller=1;else if(x data)success=Insert(tree-left,x,taller);if(taller)Department of Computer Science&Technology,Nanjing University fa
31、ll 2009DATA STRUCTURES switch(tree-balance)case-1:LeftBalance(tree,taller);break;case 0:tree-balance=-1;break;case 1:tree-balance=0;taller=0;else if(x tree-data)success=Insert(tree-right,x,taller);if(taller)switch(tree-balance)case-1:tree-balance=0;taller=0;break;case 0:tree-balance=1;break;case 1:R
32、ightBalance(tree,taller);Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES return success;Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES De
33、partment of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES0hhh-1不旋转1hh-1pp Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES-1h+1hh不旋转0hhpp高度减1 Departmen
34、t of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES1hhh-1左单旋ph0q1hh-1phq-1 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES1hh-1左单旋ph1q0h-1phq0h-1h-1 De
35、partment of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES01hh-1p-1qh-1或h-2h-1或h-2h-1rh-1h-1h-1h-100pqr右左双旋高度减1 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURESABCDEFGHIJKLMNOPQRST0000000-1-1-1-1-1-1-111111 Department of Computer Science&
36、Technology,Nanjing University fall 2009DATA STRUCTURESABCDEFGHIJKLMNOPQRST0000000-1-1-1-1-1-1-111111POOPOOP Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURESABCDEFGHIJKLMNOQRST000000-1-1-1-1-1-1-111111ORRM Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURESABCDEFGHIJKLMNOQRST000000-1-1-1-1-1-1-110010 MMME Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURESABCDEFGHIJNKLMOR00000-100-1-1-1-1010000TQ0S Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES
