說明數(shù)據(jù)結構2009級chapterTechnology

1、 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESChapter 7 搜索結構搜索結構 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES靜態(tài)搜索結構靜態(tài)搜索結構 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESn通常稱用于

2、搜索的數(shù)據(jù)集合為通常稱用于搜索的數(shù)據(jù)集合為搜索結構搜索結構，它是，它是由同一數(shù)據(jù)類型的對象由同一數(shù)據(jù)類型的對象(或記錄或記錄)組成。組成。n在每個對象中有若干屬性，其中有一個屬性，在每個對象中有若干屬性，其中有一個屬性，其值可唯一地標識這個對象其值可唯一地標識這個對象,稱為稱為關鍵碼關鍵碼。n使用基于關鍵碼的搜索，搜索結果應是唯一的。使用基于關鍵碼的搜索，搜索結果應是唯一的。但在實際應用時，搜索條件是多方面的，可以但在實際應用時，搜索條件是多方面的，可以使用基于屬性的搜索方法，但搜索結果可能不使用基于屬性的搜索方法，但搜索結果可能不唯一。唯一。n實施搜索時有兩種不同的環(huán)境。實施搜索時有兩種不同

3、的環(huán)境。u靜態(tài)環(huán)境靜態(tài)環(huán)境 靜態(tài)搜索表靜態(tài)搜索表u動態(tài)環(huán)境動態(tài)環(huán)境 動態(tài)搜索表動態(tài)搜索表 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) /構造函數(shù) 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 ( ) /析構函數(shù);template class BST : public BinaryTree private: BstNode *root; /根指針 Type RefValue; /數(shù)據(jù)輸入停止的標志 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) /構造函數(shù) BST ( Type value ); /構造函數(shù) BST ( ); /析構函數(shù) 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); /創(chuàng)建結點 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 ) 輸入數(shù)據(jù), 建立二叉搜索樹。RefValue 是輸入/結束標志。這個值應取不可能在輸入序列中/出現(xiàn)的值, 例如輸入序列的值都是正整數(shù)時, /取RefValue為0或負數(shù)。 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在發(fā)現(xiàn)不平衡時立即執(zhí)行

31、相應的平衡化旋轉操作，使在發(fā)現(xiàn)不平衡時立即執(zhí)行相應的平衡化旋轉操作，使得樹中各結點重新平衡化。得樹中各結點重新平衡化。n在程序中，用變量在程序中，用變量success記載新結點是否存儲分配記載新結點是否存儲分配成功，并用它作為函數(shù)的返回值。成功，并用它作為函數(shù)的返回值。n算法從樹的根結點開始，遞歸向下找插入位置。在找算法從樹的根結點開始，遞歸向下找插入位置。在找到插入位置到插入位置(空指針空指針)后，為新結點動態(tài)分配存儲空間，后，為新結點動態(tài)分配存儲空間，將它作為葉結點插入，并置將它作為葉結點插入，并置success為為1，再將，再將taller置為置為1，以表明插入成功。在退出遞歸沿插入路徑

32、向，以表明插入成功。在退出遞歸沿插入路徑向上返回時做必要的調(diào)整。上返回時做必要的調(diào)整。 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