Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2008·March 4, 2008 11:40:49 AMBinary Search TreesReferences: Algorithms in Java, Chapter 12 Intro to Programming, Section 4.4 http://www.cs.princeton.edu/algs4/42bst‣basic implementations‣randomized BSTs‣deletion in BSTs2Elementary implementations: summaryChallenge. Efficient implementations of search and insert.implementationworst caseaverage caseorderediteration?operationson keyssearchinsertsearch hitinsertunordered arrayNNN/2Nnoequals()unordered listNNN/2Nnoequals()ordered arraylg NNlg NN/2yescompareTo()ordered listNNN/2N/2yescompareTo()3‣binary search tree‣randomized BSTs‣deletion in BSTsDef. A BST is a binary tree in symmetric order.A binary tree is either:•Empty.•A key-value pair and two disjoint binary trees.Symmetric order. Every node’s key is:•Larger than all keys in its left subtree.•Smaller than all keys in its right subtree.4Binary search treesthewasitoftimesbestBinary search treeBST with smaller keysBST with larger keyskeyleftrightvalBSTNodeA BST is a reference to a root node.A Node is comprised of four fields:•A Key and a Value.•A reference to the left and right subtree.5BST representationKey and Value are generic types;Key is Comparablesmaller keys larger keysprivate class Node{ private Key key; private Value val; private Node left; private Node right;}it2rootbest1nullnullwas2nullthe1of1nullnulltimes1nullnullkeyvalleftrightpublic class BST<Key extends Comparable<Key>, Value>{ private Node root; private class Node { private Key key; private Value val; private Node left, right; public Node(Key key, Value val) { this.key = key; this.val = val; } } public void put(Key key, Value val) { /* see next slides */ } public Val get(Key key) { /* see next slides */ }}6BST implementation (skeleton)instance variableinstance variableGet. Return value corresponding to given key, or null if no such key.7BST searchSearching in a BSTbestitthewasbestitthewasbestbestbestbestittheofofofwastimes is after itso go to the righttimes is before wasso go to the leftunsuccessful searchfor a node with key times times is after thebut the right link is nullso the BST has no node having that keythe is after itso go to the rightsuccess! ofitthewasofitthewasofitthewasthe is before was so go to the leftsuccessful searchfor a node with key theSearching in a BSTbestitthewasbestitthewasbestbestbestbestittheofofofwastimes is after itso go to the righttimes is before wasso go to the leftunsuccessful searchfor a node with key times times is after thebut the right link is nullso the BST has no node having that keythe is after itso go to the rightsuccess! ofitthewasofitthewasofitthewasthe is before was so go to the leftsuccessful searchfor a node with key theGet. Return value corresponding to given key, or null if no such key.Running time. Proportional to depth of node.8BST search: Java implementation public Value get(Key key) { Node x = root; while (x != null) { int cmp = key.compareTo(x.key); if (cmp < 0) x = x.left; else if (cmp > 0) x = x.right; else if (cmp == 0) return x.val; } return null; }Put. Associate value with key.9BST insertInserting a new node into a BSTtimesinserttimestimes is after theso it goes on the rightthewasthewasbestitbestitbestitbestittheofofofwastimes is after itso go to the righttimes is before wasso go to the leftthewasofPut. Associate value with key. Running time. Proportional to depth of node.10BST insert: Java implementation public void put(Key key, Value val) { root = put(root, key, val); } private Node put(Node x, Key key, Value val) { if (x == null) return new Node(key, val); int cmp = key.compareTo(x.key); if (cmp < 0) x.left = put(x.left, key, val); else if (cmp > 0) x.right = put(x.right, key, val); else if (cmp == 0) x.val = val; return x; }concise, but tricky, recursive code;read carefully!11BST construction exampleConstructing a BSTbestofitthetimeswasbestofitthetimesworstwasbestofitthewasbestitthewasitthewasititwaskeyinsertedwasthebestoftimesworstitConstructing a BSTbestofitthetimeswasbestofitthetimesworstwasbestofitthewasbestitthewasitthewasititwaskeyinsertedwasthebestoftimesworstit12BST insertion: visualizationEx. Insert keys in random order.13Correspondence between BSTs and quicksort partitioningRemark. Correspondence is 1-1 if no duplicate keys.ACEIKLMOPQRSTUUE•Many BSTs correspond to same input data.•Cost of search/insert is proportional to depth of node.Remark. Tree shape depends on order of insertion.14Tree shapeWorst-case BSTsbestitofthetimeswasworstbestworstitwasoftimestheworstwastimestheofitbestTypical BSTs constructed from randomly ordered keysitofthebestwasworsttimesTypical BSTs constructed from randomly ordered keysthetimesworstwasbestofitbest case typical case worst case15BSTs: mathematical analysisProposition. If keys are inserted in random order, the expected number of compares for a search/insert is ~ 2 ln N.Pf. 1-1 correspondence with quicksort partitioning.Proposition. [Reed, 2003] If keys are inserted in random order,expected height of tree is ~ 4.311 ln N – 1.953 ln ln N.But… Worst-case for search/insert/height is N (but occurs with exponentially small chance when keys are inserted in random order).16ST implementations: summaryNext challenge. Ordered iteration.implementationguaranteeaverage caseorderediteration?operationson keyssearchinsertsearch hitinsertunordered arrayNNN/2Nnoequals()unordered listNNN/2Nnoequals()ordered arraylg NNlg NN/2yescompareTo()ordered listNNN/2N/2yescompareTo()BSTNN1.38 lg N1.38 lg N?compareTo()Traversing the tree inorder yields keys in ascending order.To implement an iterator: need a non-recursive version.Inorder traversal17 public void show() { return show(root); } private void show(Node x) { if (x == null) return; show(x.left); StdOut.println(x.key + " " + x.val); show(x.right); }Recursive inorder traversal of a binary search treeBST with smaller keyssmaller keys, in orderall keys, in orderlarger keys, in orderBST with larger keysBSTkeykeyleftrightvalTo process a node:•Follow left links until empty (pushing onto stack).•Pop and process.•Follow right link (push onto stack).Non-recursive inorder traversal18stack contentsvisit(E) visit(B) visit(A) print A
View Full Document
Unlocking...