6.006 Intro to Algorithms Recitation 03 February 9, 2011Binary Search TreeA binary search tree is a data structure that allows for key lookup, insertion, and deletion. It is abinary tree, meaning every node of the tree has at most two child nodes, a left child and a rightchild. Each node of the tree holds the following information:• x.key - Value stored in node x• x.left- Pointer to the left child of node x. NIL if x has no left child• x.right - Pointer to the right child of node x. NIL if x has no right child• x.parent - Pointer to the parent node of node x. NIL if x has no parent, i.e. x is the root ofthe treeLater on this week, we will learn about binary search trees that holds data in addition to thefour listed above but for now we will focus on the vanilla binary search tree.A binary search tree has two simple properties:• For each node x, every value found in the left subtree of x is less than or equal to the valuefound in x• For each node x, every value found in the right subtree of x is greater than or equal to thevalue found in x6.006 Intro to Algorithms Recitation 03 February 9, 2011BST OperationsThere are operations of a binary search tree that take advantage of the properties above to searchfor keys. There are other operations that manipulate the tree to insert new key or remove old oneswhile maintaining these two properties.find(x, k)Description: Find key k in a binary search tree rooted at x. Return the node that contains k if itexists or NIL if it is not in the treefind(x, k)while x != NIL and k != x.keyif k < x.keyx = x.leftelsex = x.rightreturn xAnalysis: At worst case, find goes down the longest branch of the tree. In this case, findtakes O(h) time where h is the height of the tree6.006 Intro to Algorithms Recitation 03 February 9, 2011insert(x, k)Description: Insert key k into the binary search tree Tinsert(T, k)z.key = k //z is the node to be insertedz.parent = NILx = root(T)while x != NIL //find where to insert zz.parent = xif z.key < x.keyx = x.leftelsex = x.rightif z.parent = NIL //in the case that T was an empty treeroot(T) = z //set z to be the rootelse if z.key < z.parent.key //otherwise insert zz.parent.left = zelsez.parent.right = zAnalysis: At worst case, insert goes down the longest branch of the tree to find whereto insert and then makes constant time operations to actually make the insertion. In this case,insert takes O(h) time where h is the height of the treefind-min(x) and find-max(x)Description: Return the node with the minimum or maximum key of the binary search tree rootedat node xfind-min(x)while x.left != NIL6.006 Intro to Algorithms Recitation 03 February 9, 2011x = x.leftreturn xAnalysis: At worst case, find-min goes down the longest branch of the tree before findingthe minimum element. In this case, find-min takes O(h) time where h is the height of the treenext-larger(x) and next-smaller(x)Description: Return the node that contains the next larger (the successor) or next smaller (thepredecessor) key in the binary search tree in relation to the key at node xCase 1: x has a right sub-tree where all keys are larger than x.key. The next larger key will bethe minimum key of x’s right sub-treeCase 2: x has no right sub-tree. We can find the next larger key by traversing up x’s ancestryuntil we reach a node that’s a left child. That node’s parent will contain the next larger keynext-larger(x)if x.right != NIL //case 1return find-min(x.right)y = x.parentwhile y != NIL and x = y.right //case 2x = yy = y.parentreturn y6.006 Intro to Algorithms Recitation 03 February 9, 2011Analysis: At worst case, next-larger goes through the longest branch of the tree if x isthe root. Since find-min can take O(h) time, next-larger could also take O(h) time whereh is the height of the treedelete(x)Description: Remove the node x from the binary search tree, making the necessary adjustments tothe binary search tree to maintain its properties. (Note that this operation removes a specified nodefrom the tree. If you wanted to delete a key k from the tree, you would have to first call find(k)to find the node with key k and then call delete to remove that node)Case 1: x has no children. Just delete it (i.e. change parent node so that it doesn’t point to x)Case 2: x has one child. Splice out x by linking x’s parent to x’s childCase 3: x has two children. Splice out x’s successor and replace x with x’s successordelete(x)if x.left = NIL and x.right = NIL //case 1if x.parent.left = xx.parent.left = NILelsex.parent.right = NILelse if x.left = NIL //case 2aconnect x.parent to x.rightelse if x.right = NIL //case 2bconnect x.parent to x.leftelse //case 3y = next-larger(x)connect y.parent to y.rightreplace x with y6.006 Intro to Algorithms Recitation 03 February 9, 2011Analysis: In case 3, delete calls next-larger, which takes O(h) time. At worst case,delete takes O(h) time where h is the height of the treeinorder-tree-walk(x)Description: Print out the keys in the binary search tree rooted at node x in sorted orderinorder-tree-walk(x)if x != NILinorder-tree-walk(x.left)print x.keyinorder-tree-walk(x.right)Analysis: inorder-tree-walk goes through every node and traverses to each node’s leftand right children. Overall, inorder-tree-walk prints n keys and traverses 2n times, result-ing in O(n)
View Full Document
Unlocking...