3 1 Binary Search Trees 2 1 6 9 4 8 Ordered Dictionaries Keys are assumed to come from a total order Old operations insert delete find New operations Pred k closestKeyBefore k Succ k closestKeyAfter k Max Min Binary Search Tree 3 1 2 A binary search tree is a binary tree storing keys or key element pairs 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 increasing order 6 2 1 9 4 8 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 findElement 4 Algorithm findElement k v if T isExternal v return NO SUCH KEY if k key v return findElement k T leftChild v else if k key v return element v else k key v return findElement k T rightChild v 2 1 6 9 4 8 Insertion 3 1 4 6 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 reached by the search We insert k at node w and expand w into an internal node Example insert 5 2 9 1 4 8 w 6 2 1 9 4 8 5 w 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 child w we remove v and w from the tree with operation removeAboveExternal w Example remove 4 6 2 1 9 4 v w 8 5 6 2 1 9 5 8 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 follows 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 1 3 v 2 8 6 w 9 5 z 1 5 v 2 8 6 9 Performance 3 1 6 Consider a dictionary with n items implemented by 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 How can we keep the tree more nearly balanced 2 4 Trees 9 2 5 7 10 14 Outline and Reading Multi way search tree 3 3 1 2 4 tree 3 3 2 Definition Search Definition Search Insertion Deletion Comparison of dictionary implementations Multi Way Search Tree A multi 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 between 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 2 6 8 24 15 27 32 30 Multi Way Inorder Traversal We can extend the notion of inorder traversal from binary trees to multi way search trees Namely 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 8 1 12 2 6 8 15 2 10 4 3 6 5 7 9 27 32 14 18 30 11 13 19 16 15 17 Multi 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 k1 we continue the search in child v1 ki 1 k ki i 2 d 1 we continue the search in child vi k kd 1 we continue the search in child vd Reaching an external node terminates the search unsuccessfully Example search for 30 11 2 6 8 24 15 27 32 30 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 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 18 27 32 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 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 depth items 0 1 1 2 h 1 2h 1 h 0 Insertion We insert a new item k o at the parent v of the leaf reached by searching for k We preserve the depth property but We may cause an overflow i e node v may become a 5node Example inserting key 30 causes an overflow 10 15 24 2 8 12 18 10 15 24 2 8 12 18 v 27 32 35 v 27 30 32 35 Overflow and Split We handle an overflow at a 5 node v with a split 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 to the parent node u u u 15 24 32 15 24 v 12 18 27 30 32 35 v1 v2 v3 v4 v5 v 12 18 v 27 30 v1 v2 v3 35 v4 v5 Analysis …