Question? Leave a message!




BINARY SEARCH TREES

BINARY SEARCH TREES
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Website URL
Comment
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 3.2 BINARY SEARCH TREES BSTs ‣ ordered operations ‣ deletion ‣ Algorithms FOUR TH EDITION ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu3.2 BINARY SEARCH TREES BSTs ‣ ordered operations ‣ deletion ‣ Algorithms ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduBinary search trees Definition. A BST is a binary tree in symmetric order. root a left link a subtree A binary tree is either: Empty. right child of root Two disjoint binary trees (left and right). null links Anatomy of a binary tree parent of A and R Symmetric order. Each node has a key, key S left link of E and every node’s key is: E X 9 A R value Larger than all keys in its left subtree. associated C H with R Smaller than all keys in its right subtree. keys smaller than E keys larger than E Anatomy of a binary search tree 3Binary search tree demo Search. If less, go left; if greater, go right; if equal, search hit. successful search for H S E X A R C H M 4Binary search tree demo Insert. If less, go left; if greater, go right; if null, insert. insert G S E X A R C H G M 5BST representation in Java Java definition. A BST is a reference to a root Node. A Node is composed of four fields: A Key and a Value. A reference to the left and right subtree. smaller keys larger keys private class Node BST private Key key; private Value val; Node key val private Node left, right; public Node(Key key, Value val) left right this.key = key; this.val = val; BST with smaller keys BST with larger keys Binary search tree Key and Value are generic types; Key is Comparable 6BST implementation (skeleton) public class BSTKey extends ComparableKey, Value root of BST private Node root; private class Node / see previous slide / public void put(Key key, Value val) / see next slides / public Value get(Key key) / see next slides / public void delete(Key key) / see next slides / public IterableKey iterator() / see next slides / 7BST search: Java implementation Get. Return value corresponding to given key, or null if no such key. 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; Cost. Number of compares is equal to 1 + depth of node. 8BST insert Put. Associate value with key. inserting L S E X A R H C Search for key, then two cases: M Key in tree ⇒ reset value. P search for L ends at this null link Key not in tree ⇒ add new node. S E X A R H C M P create new node L S E X A R C H M reset links L P on the way up Insertion into a BST 9BST insert: Java implementation Put. Associate value with key. concise, but tricky, recursive code; public void put(Key key, Value val) read carefully 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; Cost. Number of compares is equal to 1 + depth of node. 10best case H C S Tree shape R X A E Many BSTs correspond to same set of keys. typical case S best case Number of compares for search/insert is equal to 1 + depth of node. H E X C S A R R X A E C H A best case typical case worst case S H C E X C S E A R R X A E R C H S X typical case S A worst case E X C BST possibilities E A R C H R S X A Bottom line. Tree shape depends on order of insertion. worst case C E BST possibilities 11 R S X BST possibilities H H HBST insertion: random order visualization Ex. Insert keys in random order. 12Sorting with a binary heap Q. What is this sorting algorithm? 0. Shuffle the array of keys. 1. Insert all keys into a BST. 2. Do an inorder traversal of BST. A. It's not a sorting algorithm (if there are duplicate keys) Q. OK, so what if there are no duplicate keys? Q. What are its properties? 13Correspondence between BSTs and quicksort partitioning P H T S U D O E I A Y C M L Remark. Correspondence is 1–1 if array has no duplicate keys. 14BSTs: mathematical analysis Proposition. If N distinct keys are inserted into a BST 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 N distinct keys are inserted in random order, expected height of tree is 4.311 ln N. How Tall is a Tree? How Tall is a Tree? Bruce Reed CNRS, Paris, France Bruce Reed CNRS, Paris, France reedmoka.ccr.jussieu.fr reedmoka.ccr.jussieu.fr 3 ABSTRACT purpose of this note to prove that for /3 ½ + , we 3 ABSTRACT have: Let H be the height of a random purpose binary of search this note tree to on prove n that for /3 ½ + , we nodes. We show that there exists constants a = 4.31107... have: Let H be the height of a random binary search tree on n THEOREM 1. E(H) = logn -/31oglogn + O(1) and and/3 = 1.95... such that E(H) = clogn -/31oglogn + nodes. We show that there exists constants a = 4.31107... Var(Hn) = O(1) . O(1), We also show that Var(H) = O(1). THEOREM 1. E(H) = logn -/31oglogn + O(1) and and/3 = 1.95... such that E(H) = clogn -/31oglogn + Var(Hn) = O(1) . O(1), We also show that Var(H) = O(1). Remark By the definition of a, /3 = 3 7"g" The first defi- Categories and Subject Descriptors nition given is more suggestive of why this value is correct, Remark By the definition of a, /3 = 3 7"g" The first defi- Categories and Subject Descriptors as we will see. E.2 Data Structures: Trees nition given is more suggestive of why this value is correct, But… Worst-case height is N. For more information on random binary search trees, one as we will see. E.2 Data Structures: Trees may consult 6,7, 1, 2, 9, 4, and 8. For more information on random binary search trees, one 1. THE RESULTS Remark After I announced these results, Drmota(unpublished) may consult 6,7, 1, 2, 9, 4, and 8. exponentially small chance when keys are inserted in random order A binary search tree is a binary tree to each node of which 1. THE RESULTS developed an alternative proof of the fact that Var(Hn) = Remark After I announced these results, Drmota(unpublished) we have associated a key; these keys axe drawn from some O(1) using completely different techniques. As our two A binary search tree is a binary tree to each node of which developed an alternative proof of the fact that Var(Hn) = totally ordered set and the key at v cannot be larger than proofs illuminate different aspects of the problem, we have we have associated a key; these keys axe drawn from some O(1) using completely different techniques. As 15our two the key at its right child nor smaller than the key at its left decided to submit the journal versions to the same journal totally ordered set and the key at v cannot be larger than proofs illuminate different aspects of the problem, we have child. Given a binary search tree T and a new key k, we and asked that they be published side by side. the key at its right child nor smaller than the key at its left decided to submit the journal versions to the same journal insert k into T by traversing the tree starting at the root child. Given a binary search tree T and a new key k, we and asked that they be published side by side. and inserting k into the first empty position at which we insert k into T by traversing the tree starting at the root 2. A MODEL arrive. We traverse the tree by moving to the left child of the and inserting k into the first empty position at which we If we construct a binary search tree from a permutation current node if k is smaller than the 2. current A MODEL key and moving arrive. We traverse the tree by moving to the left child of the of 1, ..., n and i is the first key in the permutation then: to the right child otherwise. Given some permutation of If we construct a binary search tree from a permutation current node if k is smaller than the current key and moving i appears at the root of the tree, the tree rooted at the a set of keys, we construct a binary search tree from this of 1, ..., n and i is the first key in the permutation then: to the right child otherwise. Given some permutation of left child of i contains the keys 1, ..., i - 1 and its shape permutation by inserting them in the given order into an i appears at the root of the tree, the tree rooted at the a set of keys, we construct a binary search tree from this depends only on the order in which these keys appear in initially empty tree. left child of i contains the keys 1, ..., i - 1 and its shape permutation by inserting them in the given order into an the permutation, mad the tree rooted at the right child of i The height Hn of a random binary search tree T, on n depends only on the order in which these keys appear in initially empty tree. contains the keys i + 1, ..., n and its shape depends only on nodes, constructed in this manner starting from a random the permutation, mad the tree rooted at the right child of i The height Hn of a random binary search tree T, on n the order in which these keys appear in the permutation. equiprobable permutation of 1,..., n, is known to be close contains the keys i + 1, ..., n and its shape depends only on nodes, constructed in this manner starting from a random From this observation, one deduces that Hn is also the num- to alogn where a = 4.31107... is the unique solution on the order in which these keys appear in the permutation. equiprobable permutation of 1,..., n, is known to be close ber of levels of recursion required when Vazfilla Quicksort 2, ) of the equation a log((2e)/a) = 1 (here and elsewhere, From this observation, one deduces that Hn is also the num- to alogn where a = 4.31107... is the unique solution on (i.e. the version of Quicksort in which the first element in log is the natural logarithm). First, Pittel10 showed that ber of levels of recursion required when Vazfilla Quicksort 2, ) of the equation a log((2e)/a) = 1 (here and elsewhere, the permuation is chosen as the pivot) is applied to a random H,/log n 3' almost surely as n + c for some positive (i.e. the version of Quicksort in which the first element in log is the natural logarithm). First, Pittel10 showed that permutation of 1, ..., n. constant 7. This constant was known not to exceed c 11, the permuation is chosen as the pivot) is applied to a random H,/log n 3' almost surely as n + c for some positive Our observation also allows us to construct Tn from the top and Devroye3 showed that "7 = a, as a consequence of the permutation of 1, ..., n. constant 7. This constant was known not to exceed c 11, down. To ease our exposition, we think of T, as a labelling fact that E(Hn) clogn. Robson12 has found that Hn Our observation also allows us to construct Tn from the top and Devroye3 showed that "7 = a, as a consequence of the of a subtree of T, the complete infinite binary tree. does not vary much from experiment to experiment, and down. To ease our exposition, we think of T, as a labelling fact that E(Hn) clogn. Robson12 has found that Hn We will expose the key associated with each node t of T. seems to have a fixed range of width not depending upon n. of a subtree of T, the complete infinite binary tree. does not vary much from experiment to experiment, and To underscore the relationship with Quicksort, we refer to Devroye and Reed5 proved that Var(Hn) = O((log log n)2), We will expose the key associated with each node t of T. seems to have a fixed range of width not depending upon n. the key at t as the pivot at t. Suppose then that we have but this does not quite confirm Robson's findings. It is the To underscore the relationship with Quicksort, we refer to Devroye and Reed5 proved that Var(Hn) = O((log log n)2), exposed the pivots for some of the nodes forming a subtree the key at t as the pivot at t. Suppose then that we have but this does not quite confirm Robson's findings. It is the of Too, rooted at the root of T. Suppose further that for exposed the pivots for some of the nodes forming a subtree some node t of T¢, all of the ancestors of t are in T, and of Too, rooted at the root of T. Suppose further that for Permission to make digital or hard copies of all or part of this work for we have chosen their pivots. Then, these choices determine some node t of T¢, all of the ancestors of t are in T, and personal or classroom use is granted without fee provided that copies Permission to make digital or hard copies of all or part of this work for the set of keys Kt which will appear at the (possibly empty) we have chosen their pivots. Then, these choices determine are not made or distributed for profit or commercial advantage and that personal or classroom use is granted without fee provided that copies subtree of T, rooted at t, but will have no effect on the order copies bear this notice and the full citation the on set the of first keys page. Kt To which copy will appear at the (possibly empty) are not made or distributed for profit or commercial advantage and that in which we expect the keys in Kt to appear. Indeed each otherwise, to republish, to post on servers subtree or to redistribute of T, rooted to lists, at t, but will have no effect on the order copies bear this notice and the full citation on the first page. To copy permutation of Kt is equally likely. Thus, each of the keys requires prior specific permission and/or a fee. in which we expect the keys in Kt to appear. Indeed each otherwise, to republish, to post on servers or to redistribute to lists, in Kt will be equally likely to be the pivot. We let nt be STOC 2000 Portland Oregon USA permutation of Kt is equally likely. Thus, each of the keys requires prior specific permission and/or a fee. the number of keys in this set and specify the pivot at t by Copyright ACM 2000 1-58113-184-4/00/5...5.00 in Kt will be equally likely to be the pivot. We let nt be STOC 2000 Portland Oregon USA the number of keys in this set and specify the pivot at t by Copyright ACM 2000 1-58113-184-4/00/5...5.00 479 479 ST implementations: summary guarantee guarantee average case average case operations operations implementation implementation on keys on keys search insert search hit insert sequential search equals() N N ½ N N (unordered list) binary search compareTo() lg N N lg N ½ N (ordered array) BST compareTo() N N 1.39 lg N 1.39 lg N Why not shuffle to ensure a (probabilistic) guarantee of 4.311 ln N? 163.2 BINARY SEARCH TREES BSTs ‣ ordered operations ‣ deletion ‣ Algorithms ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduMinimum and maximum Minimum. Smallest key in table. Maximum. Largest key in table. max() max S min() E X min A R H C M Examples of BST order queries Q. How to find the min / max? 18Floor and ceiling Floor. Largest key ≤ a given key. Ceiling. Smallest key ≥ a given key. floor(G) max() S min() E X A R ceiling(Q) H C M floor(D) Examples of BST order queries Q. How to find the floor / ceiling? 19Computing the floor fififi nding nding nding floor(G) floor(G) floor(G) Case 1. k equals the key in the node SSS EEE XXX The floor of k is k. AAA RRR HHH CCC GGG is less than is less than is less than SSS s s so o o MMM Case 2. k is less than the key in the node floor(G) floor(G) floor(G) m m must b ust b ust be e e on the le on the le on the left ft ft The floor of k is in the left subtree. SSS EEE XXX AAA RRR Case 3. k is greater than the key in the node CCC HHH MMM The floor of k is in the right subtree GGG is g is g is gr r reat eat eate e er than r than r than EEE s s so o o floor(G) floor(G) floor(G) c c co o ould b uld b uld be e e (if there is any key ≤ k in right subtree); on the r on the r on the rig ig ight ht ht SSS EEE XXX otherwise it is the key in the node. AAA RRR CCC HHH MMM floor(G) floor(G) floor(G)in le in le in left ft ft s s sub ub ubt t tr r ree is ee is ee is null null null SSS EEE XXX AAA RRR r r res es esult ult ult CCC HHH MMM 20 C C Computing the omputing the omputing the flflfl oor func oor func oor function tion tion