《第03章查找树SearchTrees.ppt》由会员分享，可在线阅读，更多相关《第03章查找树SearchTrees.ppt（35页珍藏版）》请在三一文库上搜索。
1、Search Trees,1,Search Trees,6,9,2,4,1,8,=,Search Trees,2,Ordered Dictionaries,Keys are assumed to come from a total order. New operations: closestKeyBefore(k) closestElemBefore(k) closestKeyAfter(k) closestElemAfter(k),Search Trees,3,Binary Search (3.1.1),Binary search performs operation findElement
2、(k) on a dictionary implemented by means of an array-based sequence, sorted by key at each step, the number of candidate items is halved terminates after O(log n) steps Example: findElement(7),1,3,4,5,7,8,9,11,14,16,18,19,1,3,4,5,7,8,9,11,14,16,18,19,1,3,4,5,7,8,9,11,14,16,18,19,1,3,4,5,7,8,9,11,14,
3、16,18,19,0,0,0,0,m,l,h,m,l,h,m,l,h,l=m =h,Search Trees,4,Lookup Table (3.1.1),A lookup table is a dictionary implemented by means of a sorted sequence We store the items of the dictionary in an array-based sequence, sorted by key We use an external comparator for the keys Performance: findElement ta
4、kes O(log n) time, using binary search insertItem takes O(n) time since in the worst case we have to shift n/2 items to make room for the new item removeElement take O(n) time since in the worst case we have to shift n/2 items to compact the items after the removal The lookup table is effective only
5、 for dictionaries of small size or for dictionaries on which searches are the most common operations, while insertions and removals are rarely performed (e.g., credit card authorizations),Search Trees,5,Binary Search Tree (3.1.2),A binary search tree is a binary tree storing keys (or key-element pai
6、rs) at its internal nodes and satisfying the following property: Let u, v, and w be three nodes such that u is in the left subtree of v and w is in the right subtree of v. We have key(u) key(v) key(w) External nodes do not store items,An inorder traversal of a binary search trees visits the keys in
7、increasing order,Search Trees,6,Search (3.1.3),To search for a key k, we trace a downward path starting at the root The next node visited depends on the outcome of the comparison of k with the key of the current node If we reach a leaf, the key is not found and we return NO_SUCH_KEY Example: findEle
8、ment(4),Algorithm findElement(k, v) if T.isExternal (v) return NO_SUCH_KEY if k key(v) return findElement(k, T.rightChild(v),6,9,2,4,1,8,=,Search Trees,7,Insertion (3.1.4),To perform operation insertItem(k, o), we search for key k Assume k is not already in the tree, and let let w be the leaf reache
9、d by the search We insert k at node w and expand w into an internal node Example: insert 5,6,9,2,4,1,8,6,9,2,4,1,8,5,w,w,Search Trees,8,Deletion (3.1.5),To perform operation removeElement(k), we search for key k Assume key k is in the tree, and let let v be the node storing k If node v has a leaf ch
10、ild w, we remove v and w from the tree with operation removeAboveExternal(w) Example: remove 4,6,9,2,4,1,8,5,v,w,6,9,2,5,1,8,Search Trees,9,Deletion (cont.),We consider the case where the key k to be removed is stored at a node v whose children are both internal we find the internal node w that foll
11、ows v in an inorder traversal we copy key(w) into node v we remove node w and its left child z (which must be a leaf) by means of operation removeAboveExternal(z) Example: remove 3,3,1,8,6,9,5,v,w,z,2,5,1,8,6,9,v,2,Search Trees,10,Performance (3.1.6),Consider a dictionary with n items implemented by
12、 means of a binary search tree of height h the space used is O(n) methods findElement , insertItem and removeElement take O(h) time The height h is O(n) in the worst case and O(log n) in the best case,Search Trees,11,AVL Trees,Search Trees,12,AVL Tree Definition,AVL trees are balanced. An AVL Tree i
13、s a binary search tree such that for every internal node v of T, the heights of the children of v can differ by at most 1.,An example of an AVL tree where the heights are shown next to the nodes:,Search Trees,13,Height of an AVL Tree,Fact: The height of an AVL tree storing n keys is O(log n). Proof:
14、 Let us bound n(h): the minimum number of internal nodes of an AVL tree of height h. We easily see that n(1) = 1 and n(2) = 2 For n 2, an AVL tree of height h contains the root node, one AVL subtree of height n-1 and another of height n-2. That is, n(h) = 1 + n(h-1) + n(h-2) Knowing n(h-1) n(h-2), w
15、e get n(h) 2n(h-2). So n(h) 2n(h-2), n(h) 4n(h-4), n(h) 8n(n-6), (by induction), n(h) 2in(h-2i). Now let i=(floor of h/2) -1 Then we get: n(h) 2 h/2-1 Taking logarithms: h 2log n(h) +2 Thus the height of an AVL tree is O(log n),Search Trees,14,Insertion in an AVL Tree,Insertion is as in a binary sea
16、rch tree Always done by expanding an external node. Example:,w,b=x,a=y,c=z,before insertion,after insertion,Search Trees,15,Trinode Restructuring,let (a,b,c) be an inorder listing of x, y, z perform the rotations needed to make b the topmost node of the three,case 1: single rotation (a left rotation
17、 about a),case 2: double rotation (a right rotation about c, then a left rotation about a),(other two cases are symmetrical),Search Trees,16,Insertion Example, continued,88,44,17,78,32,50,48,62,2,4,1,1,2,2,3,1,54,1,T,0,T,2,T,3,x,y,z,unbalanced.,.balanced,Search Trees,17,Restructuring (as Single Rota
18、tions),Single Rotations:,Search Trees,18,Restructuring (as Double Rotations),double rotations:,Search Trees,19,Removal in an AVL Tree,Removal begins as in a binary search tree, which means the node removed will become an empty external node. Its parent, w, may cause an imbalance. Example:,44,17,78,5
19、0,88,48,62,54,before deletion of 32,after deletion,Search Trees,20,Rebalancing after a Removal,Let z be the first unbalanced node encountered while travelling up the tree from w. Also, let y be the child of z with the larger height, and let x be the child of y with the larger height. We perform rest
20、ructure(x) to restore balance at z. As this restructuring may upset the balance of another node higher in the tree, we must continue checking for balance until the root of T is reached,44,17,78,50,88,48,62,54,w,c=x,b=y,a=z,44,17,78,50,88,48,62,54,Search Trees,21,Running Times for AVL Trees,a single
21、restructure is O(1) using a linked-structure binary tree find is O(log n) height of tree is O(log n), no restructures needed insert is O(log n) initial find is O(log n) Restructuring up the tree, maintaining heights is O(log n) remove is O(log n) initial find is O(log n) Restructuring up the tree, m
22、aintaining heights is O(log n),Search Trees,22,Bouned-Depth Search Trees,9,10 14,2 5 7,Search Trees,23,Outline and Reading,Bounded-Depth Search Trees Multi-way search tree (3.3.1) Definition Search (2,4) tree (3.3.2) Definition Search Insertion Deletion,Search Trees,24,Multi-Way Search Tree,A multi-
23、way search tree is an ordered tree such that Each internal node has at least two children and stores d -1 key-element items (ki, oi), where d is the number of children For a node with children v1 v2 vd storing keys k1 k2 kd-1 keys in the subtree of v1 are less than k1 keys in the subtree of vi are b
24、etween ki-1 and ki (i = 2, , d - 1) keys in the subtree of vd are greater than kd-1 The leaves store no items and serve as placeholders,11 24,2 6 8,15,30,27 32,Search Trees,25,Multi-Way Inorder Traversal,We can extend the notion of inorder traversal from binary trees to multi-way search trees Namely
25、, we visit item (ki, oi) of node v between the recursive traversals of the subtrees of v rooted at children vi and vi + 1 An inorder traversal of a multi-way search tree visits the keys in increasing order,11 24,2 6 8,15,30,27 32,1,3,5,7,9,11,13,19,15,17,2,4,6,14,18,8,12,10,16,Search Trees,26,Multi-
26、Way Searching,Similar to search in a binary search tree A each internal node with children v1 v2 vd and keys k1 k2 kd-1 k = ki (i = 1, , d - 1): the search terminates successfully k kd-1: we continue the search in child vd Reaching an external node terminates the search unsuccessfully Example: searc
27、h for 30,11 24,2 6 8,15,30,27 32,Search Trees,27,(2,4) Tree,A (2,4) tree (also called 2-4 tree or 2-3-4 tree) is a multi-way search with the following properties Node-Size Property: every internal node has at most four children Depth Property: all the external nodes have the same depth Depending on
28、the number of children, an internal node of a (2,4) tree is called a 2-node, 3-node or 4-node,10 15 24,2 8,12,27 32,18,Search Trees,28,Height of a (2,4) Tree,Theorem: A (2,4) tree storing n items has height O(log n) Proof: Let h be the height of a (2,4) tree with n items Since there are at least 2i
29、items at depth i = 0, , h - 1 and no items at depth h, we have n 1 + 2 + 4 + + 2h-1 = 2h - 1 Thus, h log (n + 1) Searching in a (2,4) tree with n items takes O(log n) time,1,2,2h-1,0,items,0,1,h-1,h,depth,Search Trees,29,Insertion,We insert a new item (k, o) at the parent v of the leaf reached by se
30、arching for k We preserve the depth property but We may cause an overflow (i.e., node v may become a 5-node) Example: inserting key 30 causes an overflow,27 32 35,10 15 24,2 8,12,18,10 15 24,2 8,12,27 30 32 35,18,v,v,Search Trees,30,Overflow and Split,We handle an overflow at a 5-node v with a split
31、 operation: let v1 v5 be the children of v and k1 k4 be the keys of v node v is replaced nodes v and v“ v is a 3-node with keys k1 k2 and children v1 v2 v3 v“ is a 2-node with key k4 and children v4 v5 key k3 is inserted into the parent u of v (a new root may be created) The overflow may propagate t
32、o the parent node u,15 24,12,27 30 32 35,18,v,u,v1,v2,v3,v4,v5,15 24 32,12,27 30,18,v,u,v1,v2,v3,v4,v5,35,v“,Search Trees,31,Analysis of Insertion,Algorithm insertItem(k, o) 1. We search for key k to locate the insertion node v 2. We add the new item (k, o) at node v 3. while overflow(v) if isRoot(v
33、) create a new empty root above v v split(v),Let T be a (2,4) tree with n items Tree T has O(log n) height Step 1 takes O(log n) time because we visit O(log n) nodes Step 2 takes O(1) time Step 3 takes O(log n) time because each split takes O(1) time and we perform O(log n) splits Thus, an insertion
34、 in a (2,4) tree takes O(log n) time,Search Trees,32,Deletion,We reduce deletion of an item to the case where the item is at the node with leaf children Otherwise, we replace the item with its inorder successor (or, equivalently, with its inorder predecessor) and delete the latter item Example: to d
35、elete key 24, we replace it with 27 (inorder successor),32 35,10 15 27,2 8,12,18,Search Trees,33,Underflow and Fusion,Deleting an item from a node v may cause an underflow, where node v becomes a 1-node with one child and no keys To handle an underflow at node v with parent u, we consider two cases
36、Case 1: the adjacent siblings of v are 2-nodes Fusion operation: we merge v with an adjacent sibling w and move an item from u to the merged node v After a fusion, the underflow may propagate to the parent u,9 14,2 5 7,10,u,v,9,10 14,u,v,w,2 5 7,Search Trees,34,Underflow and Transfer,To handle an un
37、derflow at node v with parent u, we consider two cases Case 2: an adjacent sibling w of v is a 3-node or a 4-node Transfer operation: 1. we move a child of w to v 2. we move an item from u to v 3. we move an item from w to u After a transfer, no underflow occurs,4 9,6 8,2,u,v,w,4 8,6,2,9,u,v,w,Searc
38、h Trees,35,Analysis of Deletion,Let T be a (2,4) tree with n items Tree T has O(log n) height In a deletion operation We visit O(log n) nodes to locate the node from which to delete the item We handle an underflow with a series of O(log n) fusions, followed by at most one transfer Each fusion and transfer takes O(1) time Thus, deleting an item from a (2,4) tree takes O(log n) time,