归并排序、桶排序

1、Data Structures, Fall 2016Zhang Xi School of Computer Science, BUPTCH7 SearchData Structure, Fall 2016OutlinenSearch Table Sequential SearchBinary SearchIndexing SearchnBinary Search TreesBinary search treeAVL treeB- TreenHash TableWhat is hashingHash FunctionCollision ResolutionnOpen AddressingnReh

2、ashingnSeparate ChainingAnalysis of HashingData Structure, Fall 2016Search TablenSearch Table: A set of the same type of data elements. Key: The value of data item in the data element. It is used to identify the data elements.Primary Key and Second Key.Attributes:(1) There is no fixed relationship b

3、etween the elements.(2) Any relationship can be defined on the set for operation convenience.Data Structure, Fall 2016Search TablenSearch Based on the search value of key, find out the element whose key value is the same as search value. It returns the position of the element located in. Data Struct

4、ure, Fall 2016Operations on search table(1) Search a given element in the search table;(2) Get attributes of a given element;(3) Insert an element into the search table;(4) Delete an element from the search table.Static search table: Only do search on the search table Dynamic search table: Need do s

5、earch, insertion and deletion on the search tableSearch TableData Structure, Fall 2016Basic conceptsGiven: Distinct keys k1, k2, , kn and collection T of n records of the form (k1, I1), (k2, I2), , (kn, In) where Ij is the information associated with key kj for 1 = j = n.nSearch Problem: For key val

6、ue K, locate the record (kj, Ij) in T such that kj = K.nSearching is a systematic method for locating the record(s) with key value kj = K.Data Structure, Fall 2016Successful vs. UnsuccessfulnA successful search is one in which a record with key kj = K is found.nAn unsuccessful search is one in which

7、 no record with kj = K is found (and presumably no such record exists). nWe often ask how many times one key is compared with another during a search. This gives us a good measure of the total amount of work that the algorithm will do.Data Structure, Fall 2016Approaches to SearchnSequential and list

8、 methods (lists, tables, arrays). nTree indexing methods.nDirect access by key value (hashing)Data Structure, Fall 2016SearchComparison CalculationSearchLinear Search Tree SearchHash SearchData Structure, Fall 2016OutlinenSearch Table Sequential SearchBinary SearchIndexing SearchnBinary Search Trees

9、Binary search treeAVL treeB- TreenHash TableWhat is hashingHash FunctionCollision ResolutionnOpen AddressingnRehashingnSeparate ChainingAnalysis of HashingData Structure, Fall 2016#define LIST_SIZE 20typedef struct KeyType key; OtherType other_data; ElemType;typedef struct ElemType *elem; int length

10、; SSTable; Sequential SearchData Structure, Fall 2016 Searching on ListsnThe records that are stored in the list being searched (generally called the list) must conform to the following minimal standards:Every Record is associated to a key.Key objects can be compared with the standard operators = ,

11、!= , , = .Record objects can be compared to each other or to a Key.Data Structure, Fall 2016 Sequential SearchnGeneral Idea: Begin at one end of the list and scan down it until the desired key is found or the end is reached. nA successful search return the position of the record; A unsuccessful sear

12、ch return 0.int S_search ( SSTable ST , KeyType K, int n) ST0.key = K；/* a sentinel */ for (i = n ; STi.key != K ；i - )；/* compare backwards*/ return i；/*return the position, or 0 */ Data Structure, Fall 2016Example: search for key = 8 i012n-3n-2n-1nSTkey1001007138iiiiiiIf unsuccessful，then i = 0; S

13、equential SearchData Structure, Fall 2016i012n-3n-2n-1nSTkey1001008138iii = n-2 Example: search for key = 8 Sequential SearchData Structure, Fall 2016nTo analyze the behavior of an algorithm that makes comparisons of keys, we shall use the count of these key comparisons as our measure of the work do

14、ne.nAverage Search Length(ASL)n1iiinn2211cpcpcpcpASLnWhere Pi is probability(frequency) of search i-th record;nCi is the count of key comparisons when search it. Sequential Search AnalysisData Structure, Fall 2016The number of comparisons of keys done in sequential search of a list of length n isnSu

15、ccessful search:nbest case: 1 comparison. nworst case: n comparisons.naverage case: nUnsuccessful search: n+1 comparisons.nSequential search can be used for lists stored in arrays as well as for linked lists.2/ ) 1() 1(11ninpcpASLniniiiisq Sequential Search AnalysisData Structure, Fall 2016OutlinenS

16、earch Table Sequential SearchBinary SearchIndexing SearchnBinary Search TreesBinary search treeAVL treeB- TreenHash TableWhat is hashingHash FunctionCollision ResolutionnOpen AddressingnRehashingnSeparate ChainingAnalysis of HashingData Structure, Fall 2016Binary SearchnOrdered List: An ordered list

17、 is a list in which each entry contains a key, such that the keys are in order. That is, if entry i comes before entry j in the list, then the key of entry i is less than or equal to the key of entry j .All List operations except insert and replace apply without modification to an ordered list.Metho

18、ds insert and replace must fail when they would otherwise disturb the order of a list.nBinary search can be used for ordered lists stored in arrays.Data Structure, Fall 2016Binary SearchnIdea: In searching an ordered list, first compare the target to the key in the center of the list. If it is small

19、er, restrict the search to the left half; otherwise restrict the search to the right half, and repeat. In this way, at each step we reduce the length of the list to be searched by half.nImplementationKeep two indices, Low and High, that will bracket the part of the list still to be searched. The tar

20、get key will be found between the indices Low and High, inclusive.Data Structure, Fall 2016AlgorithmnInitialization: Set Low=0 and high= Length of List.nRepeat the following:If Low High, Return 1 to indicate Item not found.mid= location of middle element in the sublist.If K STmid.key, then Low= mid+

21、1. /Search right half of listElse Return mid as location of the target. /Search successful2High)(LowmidData Structure, Fall 2016Ex： search key=21 in the following presorted list. 05，13，19，21，37，56，64，75，80，88，92 05，13，19，21，37，56，64，75，80，88， 92 Order: 0 1 2 3 4 5 6 7 8 9 10 low mid highmid = (low+h

22、igh)/2;if key=amid, succeed;When keyamid, next range for checking is mid+1,highBinary Search ExampleData Structure, Fall 2016AnalysisnDecision tree : The decision tree (also called comparison tree or search tree) of an algorithm is obtained by tracing the action of binary search algorithm, represent

23、ing each comparison of keys by a node of the tree (which we draw as a circle). nBranches (lines) drawn down from the circle represent the possible outcomes of the comparison. When the algorithm terminates, we put either F (for failure) or the location where the target is found at the end of the appr

24、opriate branch, and draw as a square.Data Structure, Fall 2016nThe number of comparisons done by an algorithm in a particular search is the number of internal node traversed in going from the top of the tree down the appropriate path to a node.05 13 19 21 37 56 64 75 80 88 92927537138864215801956Dat

25、a Structure, Fall 2016 The depth of a decision tree h= log2n1- ) 1(log1) 1(log121.2221 122110nnnnhnCPASLnihiibn）（n For ordered list of length n, its average search length will be O (log n).Data Structure, Fall 2016OutlinenSearch Table Sequential SearchBinary SearchIndexing SearchnBinary Search Trees

26、Binary search treeAVL treeB- TreenHash TableWhat is hashingHash FunctionCollision ResolutionnOpen AddressingnRehashingnSeparate ChainingAnalysis of HashingData Structure, Fall 2016Indexing SearchData Structure, Fall 2016Indexing Search1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42

27、 44 38 24 48 60 58 74 57 86 5322 48 861 7 13Index tableSearch k=38Data Structure, Fall 2016 ASL=ASLIndexing table +ASLSublist For search list of length n, it is divided into b sublist and the length of a sublist is s = n/b if using binary search in indexing table, the average search length will beif

28、 using sequential search in indexing table, the average search length will be2/ ) 1(1)/1 (log2ssn)2/()2(2/ ) 1(2/ ) 1(2snsssbSearch Analysis Data Structure, Fall 2016 For list of length 10000, Sequential search: ASL=(n+1)/2=5000 Indexing search: ASL= log2(b+1)-1+ (S+1) /2 57 or ASL= (b+1)/2+ (S+1)/2

29、 = 101Binary search: ASL=log2(n+1)-1 14 Search Analysis Data Structure, Fall 2016Sequential SearchBinary SearchIndexing SearchingASLLargestSmallestMiddleList StructureOrdered 、Unordered OrderedStorage StructureArray、Linked ListArrayArray、Linked ListSearching comparisonData Structure, Fall 2016Outlin

30、enSearch Table Sequential SearchBinary SearchIndexing SearchnBinary Search TreesBinary search treeAVL treeB- TreenHash TableWhat is hashingHash FunctionCollision ResolutionnOpen AddressingnRehashingnSeparate ChainingAnalysis of HashingData Structure, Fall 2016Why B- TreenGoals of IndexingStore large

31、 filesSupport multiple search keysSupport efficient insert, delete, and range queriesnDifficulties when storing tree index on disk:Tree must be balanced.Each path from root to leaf should cover few disk pagesnThe B-Tree is now the standard file organization for applications requiring insertion, dele

32、tion, and key range searches.Data Structure, Fall 2016B-Tree Definition (多路查找树多路查找树)nA B-Tree of order m has these propertiesThe root is either a leaf or has at least two children.Each node, except for the root and the leaves, has k-1 values and k children ( m/2 k m) .All leaves are at the same leve

33、l in the tree, so the tree is always height balanced.nB-Tree node is usually selected to match the size of a disk block.A B-Tree node could have hundreds of children.Data Structure, Fall 2016 3 7 20 25 79 84 93 35 41 51 53 66 68 71 76 12 30 69 78 54tF F FFF FFFF FFF F FFF FFF FFabcdeghfi F refers to

34、 failure node, which can be reached during a search only if the value, say x being searched for is not in the tree. F can be ignored in our following slides.Data Structure, Fall 2016nB-Trees are always balanced.nB-Trees keep similar-valued records together on a disk page, which takes advantage of lo

35、cality of reference.nB-Tree node is usually selected to match the size of a disk block.nB-Trees guarantee that every node in the tree will be full at least to a certain minimum percentage. This improves space efficiency while reducing the typical number of disk fetches necessary during a search or u

36、pdate operation.Data Structure, Fall 20162) B-Tree SearchnSearch in a B-Tree is similar with search in BST.nSearch keys in current node. If search key is found, then return record. If current node is a leaf node and key is not found, then report unsuccessful.nOtherwise, follow the proper branch and

37、repeat the process. 3 7 20 25 79 84 93 35 41 51 53 66 68 71 76 12 30 69 78 54F F FF F FFF F F FF F FF F FFF F FabcdeghfiData Structure, Fall 20163) B- Tree InsertionnTo insert value X into a B-tree, there are 3 steps: nusing the SEARCH procedure for M-way trees (described above) find the leaf node t

38、o which X should be added. nadd X to this node in the appropriate place among the values already there. Being a leaf node there are no subtrees to worry about. nif there are M-1 or fewer values in the node after adding X, then we are finished. If there are M nodes after adding X, we say the node has

39、 overflowed. To repair this, we split the node into three parts:n 1 Left: the first (M-1)/2 values 2 Middle: the middle value (position 1+(M-1)/2) 3 Right: the last (M-1)/2 values Data Structure, Fall 20163) B- Tree Insertionnlets do a sequence of insertions into this B-tree (M=5, so each node other

40、 than the root must contain between 2 and 4 values): Data Structure, Fall 20163) B- Tree InsertionnInsert 17: Add it to the middle leaf. No overflow, so were done. Then Insert 6Data Structure, Fall 20163) B- Tree InsertionInsert 6: Add it to the leftmost leaf. That overflows, so we split it: Left =

41、2 3 Middle = 5 Right = 6 7 Left and Right become nodes; Middle is added to the node above with Left and Right as its children. Data Structure, Fall 20163) B- Tree InsertionInsert 21: Add it to the middle leaf. That overflows, so we split it: left = 17 21 Middle = 22 Right = 44 45 Left and Right beco

42、me nodes; Middle is added to the node above with Left and Right as its children. Data Structure, Fall 20163) B- Tree InsertionInsert 67: Add it to the rightmost leaf. That overflows, so we split it: Left = 55 66 Middle = 67 Right = 68 70 Left and Right become nodes; Middle is added to the node above

43、 with Left and Right as its children. Data Structure, Fall 20163) B- Tree InsertionBut now the node above does overflow. So it is split in exactly the same manner: Left = 5 10 (along with their children) Middle = 22 Right = 50 67 (along with their children) Left and Right become nodes; Middle is add

44、ed to the node above with Left and Right as its children. Left and Right become nodes, the children of Middle. If this was not the root, Middle would be added to the node above and the process repeated. If there is no node above, as in this example, a new root is created with Middle as its only valu

45、e. Data Structure, Fall 20164) B- Tree DeletionData Structure, Fall 2016Removing 6 causes the node it is in to underflow. In this example, we join node 7 with its more populous neighbour 17 22 44 45 and put 10 in between them, to create 7 10 17 22 44 45 4) B- Tree DeletionData Structure, Fall 2016How many values might there be in this combined node? The parent node contributes 1 value. The node that underflowed contributes exactly (M-1)/2-1 values. The neighbouring node contributes somewhere between (M-1)/2 and (M-1) values. 4)