BinarySearch品品TreesAbinarysearchtreeisaAninordertraversalofabinarytree storingkeys (orpinarysearchtreesvisitsthekey-valueentries)at itskeysininareasingorderinternal nodesand satisfyingthe following property:Letu,y,andwbethreenodessuchthatuisintheleftsubtreeof andwisinthe right subtree of v.Wehavekey(u)<key(y)<key(wDifferentnodescanhavethesamekeyExternalnodesdonotstoreitems6BinarySearchTrees
Binary Search Trees 6 Binary Search Trees A binary search tree is a binary tree storing keys (or key-value entries) 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) ◼ Different nodes can have the same key. External nodes do not store items An inorder traversal of a binary search trees visits the keys in increasing order
SearchAlgorithm TreeSearch(k,v)Tosearchfora keykwetracea downwardif TisExternal (v)pathstartingat therootreturnyThenextnodevisitedifk<key(v)dependsonthereturn TreeSearch(k, Tleft()outcomeoftheelse if k=key(v)comparisonofk withreturn ythe key of the currentelsek>kev(v))nodereturn TreeSearch(k, Tright(v)If we reach a leaf, thekey is not found and wereturn nullExample:find(4)CallTreeSearch(4,root)BinarySearchTrees
Binary Search Trees 7 Search 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 null Example: find(4): ◼ Call TreeSearch(4,root) Algorithm TreeSearch(k, v) if T.isExternal (v) return v if k < key(v) return TreeSearch(k, T.left(v)) else if k = key(v) return v else { k > key(v) } return TreeSearch(k, T.right(v)) < > =
InsertionTo performoperation insert(k,o)we searchforkeyk(usingTreeSearch)AlgorithmTreeiNsert(k,X,V):Input:A.searchkey,an associatevalue x and a node v of T to startwithOutput:a new.node w in the subtreeT()that stores the entry (k, x)W<TreeSearch(k,y)Ifk=key(w)thenreturn TreeInsert(k,X,Tleft(w))T.insertAtExternal(w,(k,x))ReturnExample:insert5Example:insertanother5?8BinarySearchTrees
Binary Search Trees 8 Insertion To perform operation insert(k, o), we search for key k (using TreeSearch) Algorithm TreeINsert(k, x, v): Input: A search key, an associate value x and a node v of T to start with Output: a new node w in the subtree T(v) that stores the entry (k, x) W TreeSearch(k,v) If k=key(w) then return TreeInsert(k, x, T.left(w)) T.insertAtExternal(w, (k, x)) Return Example: insert 5 Example: insert another 5? < > > w w
DeletionToperformoperationremove(k),we searchforkeykAssumekeykisinthetreeand letybethe nodestoringkIf nodeyhas aleaf childwweremoveyandwfromthetreewithoperationremoveExternal(w),whichremoveswanditsparentandreplacev withtheremaining child.Example:remove4BinarySearchTrees
Binary Search Trees 9 Deletion To perform operation remove ( k), we search for key k Assume key k is in the tree, and 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 removeExternal ( w), which removes w and its parent and replace v with the remaining child. Example: remove 4 v w < >
Deletion (cont.)We considerthecasewherethekeyktoberemovedisstored at a node whosechildren arebothinternalwe find the internal node wthat follows yin an inordertraversalwecopykey(w)intonodeywe removenode wand itsleftchildz(whichmustbealeaf)bymeansofoperationremoveExternal(z)Example:remove310BinarySearchTrees
Binary Search Trees 10 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 removeExternal(z) Example: remove 3 v w z v