【精品数据结构】Search Trees

1、Chapter 11,Search Trees,11.1 Binary Search Trees,1.Definition: A binary search tree is a binary tree that may be empty.A nonempty binary search tree satisfies the following properties: 1)Every element has a key and no two elements have the same key; therefore,all keys are distinct.,11.1 Binary Searc

2、h Trees,2)The keys(if any)in the left subtree of the root are smaller than the key in the root. 3)The keys(if any)in the right subtree of the root are larger than the key in the root. 4)The left and right subtrees of the root are also binary search trees.,11.1 Binary Search Trees,Example:,45,12,53,9

3、0,78,100,61,24,37,3,Leftchild data rightchild,Inherit the linked representation of binary tree,11.1 Binary Search Trees,An indexed binary search tree is derived from an ordinary binary search tree by adding the field LeftSize to each tree node. Value in Leftsize field=number of the elements in the n

4、odes left subtree +1,leftSize leftChild data rightChild,11.1 Binary Search Trees,Example:,11.1 Binary Search Trees,2.ADT specification of BSTree(ADT 11.1) AbstractDataType BSTree instances binary trees,each node has an element with a key field;all keys are distinct;keys in the left subtree of any no

5、de are smaller than the key in the node; those in the right subtree are larger,11.1 Binary Search Trees,operations: Create(): create an empty binary search tree Search(k,e):return in e the element with key k return false if the operation fails, return true if it succeeds Insert(e): insert element e

6、into the search tree Delete(k,e):delete the element with key k and return it in e Ascend():Output all elements in ascending order of key ,11.1 Binary Search Trees,2. ADT specification of IndexedBSTree (ADT 11.2) AbstractDataType IndexedBSTree instances same as for BSTree except that each node has a

7、LeftSize field operations Create(): create an empty indexed binary search tree,11.1 Binary Search Trees,Search(k,e):return in e the element with key k return false if the operation fails, return true if it succeeds IndexSearch(k,e): return in e the kth element Insert(e): insert element e into the se

8、arch tree Delete(k,e): delete the element with key k and return it in e IndexDelete(k,e): delete the kth element and return it in e Ascend(): Output all elements in ascending order of key ,11.1 Binary Search Trees,3.class BSTree Program 11.1 class definition for binary search trees template class BS

9、Tree: public BinaryTree public: bool Search(const K,11.1 Binary Search Trees,BSTree is a drived class of BinaryTree IndexedBSTree may also be defined as a derived class of BinaryTree. 1)search a binary search tree(program 11.2) template bool BSTree:Search(const K while(p)/examine pdata if(kpdata) p=

10、pRightChild; else /found element e=pdata; return true; return false; ,11.1 Binary Search Trees,2)Inserting into a binary search tree First verify if the element is exist in the BSTree if yes, output an error message. Search for insert position,and insert the element,30,5,40,80,2,5,40,2,30,80,35,Inse

11、rt 35,11.1 Binary Search Trees,Program 11.3 template BSTree,11.1 Binary Search Trees,if(epdata) p=pRightChild; else throw BadInput(); /get a node for e and attach to pp BinaryTreeNode *r=new BinaryTreeNode(e); if(root)tree not empty if(eppdata)ppLeftChild=r; else ppRightChild=r;,11.1 Binary Search T

12、rees,else /insertion into empty tree root=r; return *this; We can construct a binary seach tree by add a sequence of keys into a empty binary search tree,11.1 Binary Search Trees,3)Deletion It is necessary to adjust the binary search tree after deleting an element, so that the tree remained is still

13、 a binary tree.There is three cases for deleting node p : P is a leaf P has exactly one nonempty subtree P has exactly two nonempty subtrees,11.1 Binary Search Trees,Example:,11.1 Binary Search Trees,In case 3: we can replace the element to be deleted with either the largest element in the left subt

14、ree or the smallest element in the right subtree. Next step is to delete the largest element in the left subtree or smallest element in the right subtree.,11.1 Binary Search Trees,deleting from a binary search tree (program 11.4) template BSTree,11.1 Binary Search Trees,while(p,11.1 Binary Search Tr

15、ees,/handling case when p has two children if(pLeftChild,11.1 Binary Search Trees,/move largest from s to p pdata=sdata; p=s; pp=ps; /p has at most one child /save child pointer in c BinaryTreeNode*c; if(pLeftChild)c=pLeftChild; else c=pRightChild;,11.1 Binary Search Trees,/delete p if(p=root)root=c

16、; else /is p left or right child of pp? if(p=ppLeftChild) ppLeftChild=c; else ppRightChild=c; delete p; return *this; ,11.1 Binary Search Trees,4.Height of a binary search tree The height of a binary search tree has influence directly on the time complexity of operations like searching, insertion an

17、d deletion. Worst case: add an ordered elements1,2,3n into an empty binary search tree.,1,2,3,n,O(n),11.1 Binary Search Trees,Best case and average height: O(log2n) Example:53,25,76,20,48,14,60,84,53,25,20,76,60,48,84,14,11.2 AVL Tree,The concept of AVL tree was introduced by Russian scientists G.M.

18、Adelson-Velsky and E.M.Landis in 1962. 1.purpose: the AVL tree was introduced to increase the efficiency of searching a binary search tree, and to decrease the average search length.,11.2 AVL Tree,28,38,48,42,58,68,11.2 AVL Tree,2 Definition of an AVL tree: (1) is a binary search tree (2) |hL-hR|=1

19、where hL and hR are the heights of TL(left subtree) and TR(right subtree), respectively.,11.2 AVL Tree,Height of an AVL tree: the longest path from the root to each leaf node Balance factor bf(x) of a node x : height of right subtree of x height of left subtree of x,Each node:,11.2 AVL Tree,The heig

20、ht of an AVL tree with n elements is O(log n), so an n-element AVL search tree can be searched in O(log n) time.,11.2 AVL Tree,3.inserting into an AVL search tree,11.2 AVL Tree,4.Deletion from an AVL search tree,11.2 AVL Tree,Performance analysis,11.3 B-TREES,1.Indexed sequential access method,ISAM

21、provide good sequential and random access for external memory. ISAM: the available disk space is divided into blocks, a block being the smallest unit of disk space that will be input or output. A block is one track long and elements are in ascending order.,11.3 B-TREES,1). For sequential access, the

22、 blocks are input in order, and the elements in each block are retrieved in ascending order. If each block contains m elements, the number of disk accesses per element retrieved is 1/m,11.3 B-TREES,Random Access:,Max-Key link,Index contais the largest key in each block,Stored in internal memory,Stor

23、ed in external memory,block,11.3 B-TREES,When perform a random access of an element with key k, first search the index for the block that may contain the element, then,retrieved this block and search internally for the desired element. This method is not suitable for inserts and deletes, unless much

24、 space is leaved in each block,11.3 B-TREES,2.m-way Search Trees Definition: An m-way search tree may be empty. If it is not empty, it is a tree that satisfies the following properties: 1) In the corresponding extended search tree(obtained by replacing zero pointer with external nodes), each interna

25、l node has up to m children and between 1 and m-1 elements.,11.3 B-TREES,2) Every node with p elements has exactly p+1children. 3) Consider any node with p elements: k1k2kp, c0,c1,cp be the p+1 children of the node,C0 k1 C1 k2 . kp Cp,11.3 B-TREES,C0: The elements in the subtree with root c0 have ke

26、ys smaller than k1 Cp: Elements in the subtree with root cp have keys larger than kp Ci: Elements in the subtree with root ci have keys larger than ki but smaller than ki+1, 1=i=p.,11.3 B-TREES,Example:,11.3 B-TREES,1)search for 31,11.3 B-TREES,2)insert 31,11.3 B-TREES,2)insert 65,11.3 B-TREES,Delet

27、e 20, 84,11.3 B-TREES,Delete 5, move up 4,11.3 B-TREES,Delete 10, replace it with the largest element in c0(5),11.3 B-TREES,Delete 10, replace it with the smallest element in c1(20),20 80,5,30 40 50 60 70,82 84 86 88,2 3 4,32 36,90 92 94 96 98,A seven search tree,11.3 B-TREES,4)Height of an m-way se

28、arch tree An m-way search tree of height h may have as few as h elements(one node per level), and as many as mh-1 elements.,11.3 B-TREES,No of nodes,0 m0=1 1 m1=m h-1 mh-1,Sum of nodes mi=(mh-1)/(m-1),i=0,h-1,11.3 B-TREES,The number of elements in a m-way search tree of height h is between h and mh-

29、1 The height of a m-way search tree with n elements is between logm(n+1) and n Example: a 200-way search tree of height 5 can have 2005-1=25*1005-1=32*1010-1 elements.,11.3 B-TREES,3.B-Trees of order m Definition : A B-tree of order m is an m-way search tree. If the B-tree is not empty, the correspo

30、nding extended tree satisfies the following properties: 1)the root has at least two children 2)all internal nodes other than the root have at least m/2 children,11.3 B-TREES,3)all external nodes are at the same level,10 80,2 4 6,20 30 40 50 60 70,82 84 86 88,1,2,3,Picture 11-25 a B-tree of order 7,1

31、1.3 B-TREES,In a B-tree of order 2, each internal node has at least 2 children, and all external nodes must be on the same level, so a B-tree of order 2 is full binary trees In a B-tree of order 3(sometimes also called 2-3 tree) , each internal node has 2 or 3 children,11.3 B-TREES,example,30,20,40,

32、10 15,25,35,45 50,h-1 levels,Level h,A B-tree of order 3,11.3 B-TREES,Properties: 1)all external nodes are on the same level 2)number of external nodes=number of keywords +1 proof: b1=k0+1 ,b2=k1+b1, b3=k2+b2, the number of external nodes =kh-1+kh-2 +k1+k0+1=n+1.,11.3 B-TREES,1)Searching a B-Tree A

33、B-tree is searched using the same algorithm as used for an m-way search tree. Algorithm analysis: the number of disk access is at most h(h is the height of the B-Tree). proof: T is a B-Tree of order m with height h, number of elements in T is n, each time we read a node into memory. The n+1 external

34、 nodes are on level h.,11.3 B-TREES,Number of nodes on the each level of the B-Tree is:,.,level 0 1 Level 1 =2 Level 2 =2m/2 Level 3 =2m/22 Level h = 2m/2h-1,11.3 B-TREES,n+1= 2m/2h-1 , (n+1)/2= m/2h-1 , h-1=log m/2 (n+1)/2, logm(n+1)=h=1+logm/2 (n+1)/2,In the case that each node has m children,Exam

35、ple: n=2*106, m=199 then h=1+log100(102)3=4 search one from 200 branches,11.3 B-TREES,2) Inserting into a B-Tree Property: always happen at one level above the external nodes,11.3 B-TREES,Case 1:number of children in the nodem-insert into the node as ordered,A B-Tree of order 7,11.3 B-TREES,Insert 3

36、,11.3 B-TREES,Case 2. Insert into a node with m children (also called a full node), like insert 25 into the B-Tree in the last example, the full node is split into two nodes. A new pointer will be added to the parent of the full node . Because km/2 is inserted into parent node, it may cause new spli

37、t. If the root is split,the height of the tree will increased by 1.,11.3 B-TREES,Example:,11.3 B-TREES,Insert 44,11.3 B-TREES,Another example: a B-tree of order 5 : insert k,m,j,e,s,i,r,x,c,a b f g,Algorithm analyses: If the insert operation causes s node to split, then the number of disk access is

38、h (to read in the nodes on the search path) +2s (to write out the two split parts of each node that is split)+1 (to write the new node).,11.3 B-TREES,3)deletion from a B-Tree Two cases: The element to be deleted is in a node whose children are external nodes(i.e.the element is in a leaf) The element is to be deleted from a nonleaf.,11.3 B-TREES,a) the element to be deleted is in a leaf Case1: delete it directly if it is in a node which has more than m/2 children,Case2: if it is in