说明数据结构2009级chapterTechnology

1、 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESChapter 7 搜索结构搜索结构 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES静态搜索结构静态搜索结构 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESn通常称用于

2、搜索的数据集合为通常称用于搜索的数据集合为搜索结构搜索结构，它是，它是由同一数据类型的对象由同一数据类型的对象(或记录或记录)组成。组成。n在每个对象中有若干属性，其中有一个属性，在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象其值可唯一地标识这个对象,称为称为关键码关键码。n使用基于关键码的搜索，搜索结果应是唯一的。使用基于关键码的搜索，搜索结果应是唯一的。但在实际应用时，搜索条件是多方面的，可以但在实际应用时，搜索条件是多方面的，可以使用基于属性的搜索方法，但搜索结果可能不使用基于属性的搜索方法，但搜索结果可能不唯一。唯一。n实施搜索时有两种不同的环境。实施搜索时有两种不同

3、的环境。u静态环境静态环境 静态搜索表静态搜索表u动态环境动态环境 动态搜索表动态搜索表 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES定义定义 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES351545504025102030 Department of Computer Science & Technology, Nanjing

4、University fallDATA STRUCTURES512345641C131332122133132123123123 132 213 231 312 321 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES#include template class BST;template Class BstNode : public BinTreeNode friend class BST ; Department of Computer Science &

5、Technology, Nanjing University fallDATA 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 ) d

6、ata = d; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Type GetData ( ) return data; BstNode ( ) /析构函数;template class BST : public BinaryTree private: BstNode *root; /根指针 Type RefValue; /数据输入停止的标志 void MakeEmpty ( BstNode *& ptr ); void Insert ( Type x,

7、BstNode *& ptr ); /插入 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES void Remove ( Type x, BstNode *& ptr ); /删除 void PrintTree ( BstNode * ptr ) const; BstNode *Copy ( const BstNode * ptr ); /复制 BstNode *Find ( Type x, BstNode * ptr ); /搜索 BstNode *M

8、in ( BstNode * ptr ) const; /求最小 BstNode *Max ( BstNode * ptr ) const; /求最大public: Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES BST ( ) : root (NULL) /构造函数 BST ( Type value ); /构造函数 BST ( ); /析构函数 const BST& operator = ( const BST& Value ); void Mak

9、eEmpty ( ) 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 ( root )-data; Department of Computer Science & Technology, Nanjing University fallDA

10、TA STRUCTURES void Insert ( Type x ) Insert ( x, root ); /插入新元素 void Remove ( Type x ) Remove ( x, root ); /删除含x的结点有三种基本操作：有三种基本操作：查找查找插入插入删除删除 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES二叉搜索树（二叉排序树）二叉搜索树（二叉排序树）对于树中的每个结点对于树中的每个结点x，它的左子树中所，它的左子树中所有关键码小于有关键码

11、小于x的关键码，而它的右子树的关键码，而它的右子树中所有关键码大于中所有关键码大于x的关键码。的关键码。有三种基本操作：有三种基本操作：查找查找插入插入删除删除 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES351545504025102030 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Sc

12、ience & Technology, Nanjing University fallDATA 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 Find ( x, ptr-rightChild

13、); else return ptr; /相等,搜索成功 Department of Computer Science & Technology, Nanjing University fallDATA 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

14、( temp-data rightChild; /右子树 else temp = temp-leftChild; /左子树 return NULL; /搜索失败 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES35154550402510203028插入新结点插入新结点28 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department

15、of Computer Science & Technology, Nanjing University fallDATA 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

16、ptr-data ) /在右子树插入 Insert ( x, ptr-rightChild ); Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES 535378537865537865175378658717537865091787537865811787095378651517870981 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStem

17、plate BST : BST ( Type value ) 输入数据, 建立二叉搜索树。RefValue 是输入/结束标志。这个值应取不可能在输入序列中/出现的值, 例如输入序列的值都是正整数时, /取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 fallDATA STRUCTURE

18、S351545504025102030 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES基本思想：基本思想：首先查找，确定被删除结点是否在二叉搜首先查找，确定被删除结点是否在二叉搜索树中。索树中。分情况讨论：分情况讨论：（删除结点为（删除结点为ptr指针所指，其双亲结点为指针所指，其双亲结点为f结点指针结点指针所指，被删除结点的左子树和右子树分别用所指，被删除结点的左子树和右子树分别用pl和和pr表表示）示） Department of Computer Science

19、 & Technology, Nanjing University fallDATA STRUCTURES5378651787092345删除45右子树空, 用左子女顶替5378651787092353788817940923删除78左子树空, 用右子女顶替539488170923 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES8853788117940945删除782365538188179409452365在右子树上找中序下第一个结点填补 Departme

20、nt of Computer Science & Technology, Nanjing University fallDATA STRUCTURES template void BST :Remove (const Type& x, BstNode * & ptr) BstNode * temp; if ( ptr != NULL ) if ( x data ) /在左子树中删除 Remove ( x, ptr-leftChild ); else if ( x ptr-data ) /在右子树中删除 Remove ( x, ptr-rightChild ); else

21、 if ( ptr-leftChild != NULL & ptr-rightChild != NULL ) Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES temp = Min( ptr-rightChild ); /找ptr右子树中序下第一个结点 ptr-data = temp-data; /填补上 Remove ( ptr-data, ptr-rightChild ); /在ptr的右子树中删除temp结点 else / ptr结点只有一个或零个子女 t

22、emp = 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 fallDATA STRUCTURES平衡处理平衡处理122133132123123 Department of Computer Science & Technolog

23、y, Nanjing University fallDATA STRUCTURES ABCABCDEDE Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES ABCABCDEDE3200001100 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESABCDE1100template class AVLTree public: struct AVLN

24、ode /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*& Tree, Type x); vo

25、id 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), ro

26、ot (NULL) int Insert (Type x) return Insert (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 fallDATA STR

27、UCTURESh插入插入BACEDhhh-1hhhh-1h-1ABDCEhhh-1BCEADh Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREShhACEDh-1h-1BFGEGACDBFhhh-1h插入插入 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESFGDhAh-1CEBhhAEhhCDh-1hBFG插入插入hhACEDh-1h-1BFG

28、EGACDBFhhh-1h Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREShhh-1h-1ACEDBFGACEBFGDhhhh-1ACEDBFGhhh-1hhhh-1hACEBFGD Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing

29、 University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES161631633163113161611931693112691611 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES18183163167391826117326161199716147112626911 Department o

30、f Computer Science & Technology, Nanjing University fallDATA STRUCTURES151831816731171491615112626149从空树开始的建树过程从空树开始的建树过程 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESn下面的算法将通过递归方式将新结点作为叶结点插入下面的算法将通过递归方式将新结点作为叶结点插入并逐层修改各结点的平衡因子。并逐层修改各结点的平衡因子。n在发现不平衡时立即执行

31、相应的平衡化旋转操作，使在发现不平衡时立即执行相应的平衡化旋转操作，使得树中各结点重新平衡化。得树中各结点重新平衡化。n在程序中，用变量在程序中，用变量success记载新结点是否存储分配记载新结点是否存储分配成功，并用它作为函数的返回值。成功，并用它作为函数的返回值。n算法从树的根结点开始，递归向下找插入位置。在找算法从树的根结点开始，递归向下找插入位置。在找到插入位置到插入位置(空指针空指针)后，为新结点动态分配存储空间，后，为新结点动态分配存储空间，将它作为叶结点插入，并置将它作为叶结点插入，并置success为为1，再将，再将taller置为置为1，以表明插入成功。在退出递归沿插入路径

32、向，以表明插入成功。在退出递归沿插入路径向上返回时做必要的调整。上返回时做必要的调整。 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate int AVLTree :Insert ( AVLNode* &tree, Type x, int &taller ) / int success; if ( tree = NULL ) tree = new AVLNode (x); success = ( tree != NULL ) ? 1 : 0

33、; if ( success ) taller = 1; else if ( x data ) success = Insert ( tree-left, x, taller ); if ( taller ) Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES switch ( tree-balance ) case -1 : LeftBalance ( tree, taller ); break; case 0 : tree-balance = -1; break; c

34、ase 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 : RightBalance ( tree, taller ); Department of Computer Science &

35、; Technology, Nanjing University fallDATA STRUCTURES return success; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjin

36、g University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES0hhh-1不旋转1hh-1pp Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES- -1h+1hh不旋转0hhpp高度减1 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES