數(shù)據(jù)結(jié)構(gòu)英文教學(xué)課件：chapter7 Searching

1、Chapter 7Searching Data StructureSoftware College Northeastern UniversityOverview Searching Problem Static Searching problem Binary Search Tree AVL TreeData StructureSoftware College Northeastern University7.1 Searching ProblemSearch Table - An collect of objects for being searchedType - static sear

2、ch table(靜態(tài)搜索表): the table to be searched is never altered - dynamic search table(動態(tài)搜索表): the table to be searched can be altered Attributes - key（關(guān)鍵字）: A group of one or more attributes that uniquely identifies an object. Data StructureSoftware College Northeastern UniversitySearching ProblemSearch

3、ing problem Give a key value X and a search table A, return the position of X in A or an indication that is not presented. If X occurs more than once, return any occurrence.Data StructureSoftware College Northeastern UniversitySearching ProblemThe complexity of searching algorithms The number of com

4、parisons - unsuccessful search - The worse-case successful search - The average of search（AVL-平均比較次數(shù)）Data StructureSoftware College Northeastern UniversityStatic Searching Problemdifferent searching algorithms: Sequential search(順序搜索),Block search（塊搜索）,Binary search（二分搜索）Data StructureSoftware Colle

5、ge Northeastern University7.2 Static Searching Problem: Sequential Searching(順序搜索)Storage search table: Array with unsorted objectsAlgorithm - Sequential Searching - Steps through the array sequentially until a match is found or reaching the end of array Data StructureSoftware College Northeastern U

6、niversitySequential Searching:Definitionstatic search tabletemplate class dataList; template class Node friend class dataList;public: Node ( const Type & value ) : key ( value ) Type getKey ( ) const return key; /讀關(guān)鍵碼 void setKey ( Type k ) key = k; /修改關(guān)鍵碼private: Type key;/關(guān)鍵碼 other; /其他域;Data Stru

7、ctureSoftware College Northeastern Universitytemplate class dataList public: dataList ( int sz = 10 ) : ArraySize (sz), Element (new Node sz+1) virtual dataList ( ) delete Element; friend ostream &operator (ostream & OutStream, const dataList & OutList ); friend istream & operator ( istream & InStre

8、am, dataList & InList );protected: Node *Element; /數(shù)據(jù)表中存儲數(shù)據(jù)的數(shù)組 int ArraySize, CurrentSize; /數(shù)組最大長度和當(dāng)前長度;Sequential Searching:DefinitionData StructureSoftware College Northeastern Universitytemplate class searchList : public dataList /作為派生類的靜態(tài)搜索表的類定義public: searchList ( int sz = 10 ) : dataList (sz)

9、virtual searchList ( ) virtual int Search ( const Type & x ) const;Sequential Searching:DefinitionData StructureSoftware College Northeastern Universitytemplate istream & operator ( istream & InStream, dataList & InList ) /從輸入流對象InStream輸入數(shù)據(jù)到數(shù)據(jù)表InList cout InList.CurrentSize; cout “輸入數(shù)組元素值 : n”; for

10、 ( int i = 1; i = InList.CurrentSize; i+ ) cout “元素 ” i InList.Elementi; return InStream;Sequential Searching:DefinitionData StructureSoftware College Northeastern Universitytemplate ostream & operator ( ostream & OutStream, const dataList & OutList ) /將數(shù)據(jù)表OutList內(nèi)容輸出到輸出流對象OutStream OutStream “數(shù)組內(nèi)容

11、: n”; for ( int i = 1; i = OutList.CurrentSize+1; i+ ) OutStream OutList.Elementi ; OutStream endl; OutStream “數(shù)組當(dāng)前大小 : ” OutList.CurrentSize endl; return OutStream;Sequential Searching:DefinitionData StructureSoftware College Northeastern Universitytemplate int searchList :Search ( const Type & x )

12、 const /順序搜索的迭代算法，0號元素為監(jiān)視哨，數(shù)據(jù)對象從/下標(biāo)1開始存放，成功則返回對象的位置，否則返回0 Element0.setKey ( x ); int i = CurrentSize; while (Elementi.getKey ( ) != x ) ; return i;i-Sequential SearchingData StructureSoftware College Northeastern Universityconst int Size = 10;main ( ) /順序搜索的主過程 searchList List1 (Size); float Target;

13、 int Location; cin List1; cout List1; /輸入/輸出數(shù)據(jù)表List1 cout Target; if ( ( Location = List1.search (Target ) ) != 0 ) cout “ 找到下標(biāo) ” Location endl; else cout “ 沒有找到.n”;Sequential SearchingData StructureSoftware College Northeastern University Consider all possible cases Find the number of comparisons f

14、or each case Add the number of comparisons and divide by the number of casesSequential Searching:AnalyzationData StructureSoftware College Northeastern University Successful Search： best： 1 worst： n average：ASLnP1+(n-1)P2+2Pn-1+Pn ASLss=(n+n-1+2+1)/n = (n+1)/2Unsuccessful search : n +1 Average Searc

15、h： ASLss=(n+1)/4+(n+1)/2 =3*(n+1)/4Sequential Searching: AnalyzationData StructureSoftware College Northeastern UniversityAdvantage: simple algorithm elements storing in array are not required sortedDisadvantage: searching waste a lot of time - O(n)Sequential Searching: AnalyzationData StructureSoft

16、ware College Northeastern University7.3 Binary SearchA sequential search of a list begins at the beginning of the list and continues until the item is found or the entire list has been searchedA binary search looks for an item in a list using a divide-and-conquer strategyData StructureSoftware Colle

17、ge Northeastern UniversityMeaning of Divide and ConquerIn military, “divide and conquer” is a kind of strategy.In computer science, “divide and conquer” is a programming technique by breaking down a problem into one or more sub problems.“Divide and conquer” is usually implemented by recursion.Data S

18、tructureSoftware College Northeastern UniversityStructure of Divide and ConquerDivideBreak a problem into sub problem(s)ConquerSolve all sub problem(s)CombineSolve the problem using the results of the sub problem(s)Data StructureSoftware College Northeastern UniversityBinary SearchingIf the terms in

19、 a sequence are ordered, a binary search algorithm is more efficient than linear search.The binary search algorithm iteratively restricts the relevant search interval until it closes in on the position of the element to be located.Data StructureSoftware College Northeastern UniversityBinary Search:

20、Examplea c d f g h j l m o p r s u v x zbinary search for the letter jcenter elementsearch intervalData StructureSoftware College Northeastern Universitya c d f g h j l m o p r s u v x zbinary search for the letter jcenter elementsearch intervalBinary Search: ExampleData StructureSoftware College No

21、rtheastern Universitya c d f g h j l m o p r s u v x zbinary search for the letter jcenter elementsearch intervalBinary Search: ExampleData StructureSoftware College Northeastern Universitya c d f g h j l m o p r s u v x zbinary search for the letter jcenter elementsearch intervalBinary Search: Exam

22、plefound !Data StructureSoftware College Northeastern University搜索成功的例子 搜索失敗的例子Data StructureSoftware College Northeastern UniversityBinary Search:Algorithm Binary search algorithm assumes that the items (from low=0 to high=n-1) in the list being searched are sorted：template class orderedList : publ

23、ic dataList /有序表的類定義,繼承了數(shù)據(jù)表public: orderedList (int sz = 10) : dataList (sz) virtual orderedList ( ) virtual int Search ( const Type & x ) const; Data StructureSoftware College Northeastern UniversityBinary Search: algorithmThe algorithm begins at the middle of the list in a binary search mid=(low+h

24、igh)/2Compare the item for which we are searching with the item in the middle keyElementmid.key :search in the second half from low=mid+1 to highData StructureSoftware College Northeastern UniversityBinary Search: algorithmOnce again we examine the “middle” element The process continues with each co

25、mparison cutting in half the portion of the list where the item might be Data StructureSoftware College Northeastern Universitytemplate int orderedList :BinarySearch ( const Type & x, const int low, const int high ) const /折半搜索的遞歸算法 int mid = -1; if ( low = high ) mid = ( low + high ) / 2; if ( Elem

26、ent mid.getKey( ) x ) mid = BinarySearch ( x, low, mid -1 ); return mid;Binary Search: Recursive algorithmData StructureSoftware College Northeastern Universitytemplate int orderedList : BinarySearch ( const Type & x ) const /折半搜索的迭代算法 int high = , low = 0, mid; while ( ) mid = ( low + high ) / 2; i

27、f ( Elementmid.getKey ( ) x ) ; else return mid; return -1;CurrentSize-1low = highlow = mid + 1high = mid - 1Binary Search: Non-recursive algorithmData StructureSoftware College Northeastern UniversityBinary Search:improvingIf the item is not found ,return the maximum item that is smaller than that

28、one and the minimum item that is bigger than that one.template int orderedList : BinarySearch ( const Type & x ,int &i, int&j) ;Data StructureSoftware College Northeastern Universitytemplate int orderedList : BinarySearch ( const Type & x ,int &i,int &j) const int high = CurrentSize-1, low = 0, mid;

29、 while (low =high) mid = ( low + high ) / 2; if ( Elementmid.getKey ( ) x ) high=mid-1; else i = j = mid; return mid; i = high;j=low; return -1;Binary Search: Non-recursive algorithmData StructureSoftware College Northeastern University1 2 3 4 5 6 7 8 9 10 116391471025811Left child nullKey=21Key=85B

30、inary Search: analyzation 05 13 19 21 37 56 64 74 80 88 92 successful worst： log2 n +1 unsuccessful worst： log2 n +1Data StructureSoftware College Northeastern UniversityASLbs=P1C1+P2C2+PnCn = j2j-1 = log2(n+1)-1 log2(n+1)-1 example： successful for searching among 11 elements (1+2*2+3*4+4*4)/11 =363

31、91471025811Binary Search: analyzationData StructureSoftware College Northeastern UniversityBinary Search Trees A Binary Search Tree (BST) data structure is a binary tree with an ordering property BSTs are used to maintain an order and faster retrieval, insertion, and removal of individual elements B

32、STs are used to solve dynamic Searching ProblemsData StructureSoftware College Northeastern UniversityBinary Search TreesA Binary Search Tree (BST) isan empty treeconsists of a node called the root and two children, left and right, each of which are themselves binary search trees. Each BST contains

33、a key at the root that is greater than all keys in the left BST while also being less than all keys in the right BST. Key fields are unique, duplicates not allowed.Data StructureSoftware College Northeastern UniversityA Binary Search Tree50752512352841669081959110054Data StructureSoftware College No

34、rtheastern UniversityAre these BSTs?5075251245669050752512557390Is this a BST?Is this a BST?Data StructureSoftware College Northeastern UniversityBST Algorithms Think about an algorithm that retrieves a node. It is similar to binary search. Start at root, go left or right until?_(Ex: target = 65) (E

35、x: target = 60)Assuming the BST is balanced, what is the tightest upper bound in Big-Oh?50752512366590Data StructureSoftware College Northeastern University455333789619012451253337896190A Binary Search TreeData StructureSoftware College Northeastern University#include template class BST;template cla

36、ss BstNode : public BinTreeNode /二叉搜索樹結(jié)點類friend class BST ; protected: Type data; BstNode *leftChild, *rightChild; public: BstNode ( ) : leftChild (NULL), rightChild (NULL) BstNode ( const Type d ) : data (d), leftChild (NULL), rightChild (NULL) Binary Search Tree:Definition(1)Data StructureSoftware

37、 College Northeastern UniversityBstNode ( const Type d = 0, BstNode *L = NULL, BstNode *R = NULL) : data (d), leftChild (L), rightChild (R) BstNode ( ) ;Binary Search Tree:Definition(2)Data StructureSoftware College Northeastern Universitytemplate class BST : public : BinaryTree private: BstNode *ro

38、ot; /二叉搜索樹的根指針 Type RefValue; /數(shù)據(jù)輸入停止的標(biāo)志 BstNode *lastfound; /最近搜索到的結(jié)點的指針 void MakeEmpty ( BstNode *& ptr ); void Insert ( const Type & x, BstNode *& ptr ); void Remove ( const Type & x, BstNode *& ptr ); Binary Search Tree:Definition(3)Data StructureSoftware College Northeastern Universityvoid Prin

39、tTree ( BstNode *ptr ) const; BstNode *Copy (const BstNode *ptr ); BstNode *Find (const Type & x, BstNode * ptr ) const; BstNode *Min ( BstNode * ptr ) const; /求最小 BstNode *Max ( BstNode * ptr ) const; /求最大 Binary Search Tree:Definition(4)Data StructureSoftware College Northeastern University friend

40、 class BSTIterator; /中序游標(biāo)類public: BST ( ) : root (NULL) BST ( Type value ) : RefValue (value), root (NULL) BST ( ); const BST & operator = ( const BST & Value ); void MakeEmpty ( ) MakeEmpty (root); root = NULL; void PrintTree ( ) const PrintTree ( root ); Binary Search Tree:Definition(4)Data Struct

41、ureSoftware College Northeastern Universityint Find ( const Type & x ) const return Find ( x, root ) != NULL; Type Min ( ) return Min ( root )data ; Type Max ( ) return Max ( root )data ; void Insert ( const Type & x ) Insert ( x, root ); void Remove ( const Type & x ) Remove ( x, root ); Data Struc

42、tureSoftware College Northeastern Universitytemplate BstNode * BST : Find (const Type & x, BstNode * ptr ) const /二叉搜索樹的遞歸的搜索算法 if ( ptr = NULL ) return NULL; /搜索失敗 else if ( x ptrdata ) /在右子樹遞歸搜索 return Find ( x, ); else return ptr; /相等,搜索成功ptrleftChildptrrightChildBinary Search Tree: Recursive alg

43、orithmData StructureSoftware College Northeastern Universitytemplate BstNode * BST : Find (const Type & x, BstNode * ptr ) const /二叉搜索樹的迭代的搜索算法 if ( ptr != NULL ) BstNode * temp = ptr; while ( temp != NULL ) if ( tempdata = x ) return temp; /成功 if ( tempdata x ) temp = temprightChild; /右子樹 else temp

44、 = templeftChild; /左子樹 return NULL; /搜索失敗Binary Search Tree: Non-Recursive algorithmData StructureSoftware College Northeastern UniversityBinary Search Trees:Searching ComplexityDegenerate（退化的） only one child -O(n)Balanced mostly two children -O(log2n)Complete always two children -O(log2n)Degenerate

45、 binary treeBalanced binary treeComplete binary treeData StructureSoftware College Northeastern UniversitySearching sequence :45，24，53，45，12，24，90455324452445455312244553241290NULL Search 45 Search 24 Search 53 search 45 search 12 search 24 search 9045531224455324Binary Search Trees: InsertionData S

46、tructureSoftware College Northeastern Universitytemplate void BST:Insert (const Type & x, BstNode * & ptr) /遞歸的二叉搜索樹插入算法 if ( ptr = NULL ) /空二叉樹 ptr = new BstNode (x); /創(chuàng)建含 x 結(jié)點 if ( ptr = NULL ) cout Out of space endl; exit (1); else if ( x ptrdata ) /在右子樹插入 Insert ( x, ptrrightChild );Algorithm:In

47、sertingData StructureSoftware College Northeastern Universitytemplate BST : BST ( Type value ) /輸入數(shù)據(jù)，建立二叉搜索樹的算法, RefValue是/輸入結(jié)束標(biāo)志 Type &x; root = NULL; RefValue = value; cin x; while ( x.key != RefValue ) Insert ( x, root ); cin x; Data StructureSoftware College Northeastern Universitytemplate BstNo

48、de * BST:Min ( BstNode * ptr ) const /求最小template BstNode * BST:Max ( BstNode * ptr ) const /求最大 Binary Search Tree: testData StructureSoftware College Northeastern UniversityBinary Search Tree - Best TimeAll BST operations are O(d), where d is tree depthminimum d is for a binary tree with N nodesWh

49、at is the best case binary search tree? What is the worst case binary search tree?So, best case running time of BST operations is O(log N)Data StructureSoftware College Northeastern UniversityBinary Search Tree - Worst TimeWorst case running time is O(N) What happens when you Insert elements in asce

50、nding order?Insert: 2, 4, 6, 8, 10, 12 into an empty BSTProblem: Lack of “balance”: compare depths of left and right subtreesUnbalanced degenerate treeData StructureSoftware College Northeastern UniversityRearrange the nodes after delete a node.FPPLPRfpFPfpFPfpPRFPfpPLBinary Search Trees: DeleteData

51、 StructureSoftware College Northeastern UniversityRemoving a NodeIf the node is a leaf,it can be deleted immediately.If the node has one child,the node can be deleted after its parent adjusts a link to bypass the node.If the node has two children.The general strategy is to replace the data of this n

52、ode with the smallest data of the right subtree. Data StructureSoftware College Northeastern UniversityData StructureSoftware College Northeastern University Removing a nodetemplate void BST :Remove (const Type &x, BstNode * &ptr) BstNode * temp; if ( ptr != NULL ) if ( x ptrdata ) Remove ( x, ptrri

53、ghtChild );else if ( ptrleftChild != NULL & ptrrightChild != NULL ) temp = Min ( ptrrightChild ); ptrdata = tempdata; Remove ( ptrdata, temp ); Data StructureSoftware College Northeastern Universityelse temp = ptr; if ( ptrleftChild = NULL ) /只有左子樹 ptr = ptrrightChild; else if ( ptrrightChild = NULL

54、 )/ 只有右子樹 ptr = ptrleftChild; delete temp; Data StructureSoftware College Northeastern UniversityBalanced and unbalanced BST4251315243764265713Is this “balanced”?Data StructureSoftware College Northeastern UniversityApproaches to balancing treesDont balanceMay end up with some nodes very deepStrict

55、balanceThe tree must always be balanced perfectlyPretty good balanceOnly allow a little out of balanceAdjust on accessSelf-adjustingData StructureSoftware College Northeastern UniversityBalancing Binary Search TreesMany algorithms exist for keeping binary search trees balancedAdelson-Velskii and Lan

56、dis (AVL) trees (height-balanced trees) Splay trees and other self-adjusting treesB-trees and other multiway search treesData StructureSoftware College Northeastern UniversityPerfect BalanceWant a complete tree after every operationtree is full except possibly in the lower rightThis is expensiveFor

57、example, insert 2 in the tree on the left and then rebuild as a complete treeInsert 2 &complete tree6498155286914Data StructureSoftware College Northeastern UniversityAVL - Good but not Perfect BalanceAVL trees are height-balanced binary search treesBalance factor of a nodeheight(left subtree) - hei

58、ght(right subtree)An AVL tree has balance factor calculated at every nodeFor every node, heights of left and right subtree can differ by no more than 1Store current heights in each nodeData StructureSoftware College Northeastern UniversityHeight of an AVL TreeN(h) = minimum number of nodes in an AVL

59、 tree of height h.BasisN(0) = 1, N(1) = 2InductionN(h) = N(h-1) + N(h-2) + 1Solution (recall Fibonacci analysis)N(h) h ( 1.62)h-1h-2hData StructureSoftware College Northeastern UniversityHeight of an AVL TreeN(h) h ( 1.62)Suppose we have n nodes in an AVL tree of height h.n N(h) (because N(h) was th

60、e minimum)n h hence log n h (relatively well balanced tree!)h 1.44 log2n (i.e., Find takes O(logn)Data StructureSoftware College Northeastern UniversityNode Heights100206498151height of node = hbalance factor = hleft-hrightempty height = -100height=2 BF=1-0=10649151Tree A (AVL)Tree B (AVL)Data Struc