Our implementation of the treeSearch utility, from Code Fragment 11.3, relies on recursion. For a large unbalanced
Question:
Transcribed Image Text:
1 /** An implementation of a sorted map using a binary search tree. */ 2 public class TreeMap
1 /** An implementation of a sorted map using a binary search tree. */ 2 public class TreeMap extends AbstractSortedMap { // To represent the underlying tree structure, we use a specialized subclass of the // LinkedBinary Tree class that we name BalanceableBinary Tree (see Section 11.2). protected BalanceableBinary Tree tree = new BalanceableBinary Tree<>(); /** Constructs an empty map using the natural ordering of keys. */ public TreeMap() { super(); tree.addRoot(null); } /** Constructs an empty map using the given comparator to order keys. */ public TreeMap(Comparator comp) { super(comp); tree.addRoot(null); / the AbstractSortedMap constructor // create a sentinel leaf as root 9. 10 11 12 13 // the AbstractSortedMap constructor // create a sentinel leaf as root 14 15 16 /** Returns the number of entries in the map. */ public int size() { return (tree.size() – 1) / 2; } /** Utility used when inserting a new entry at a leaf of the tree */ private void expandExternal(Position> p, Entry entry) { tree.set(p, entry); tree.addLeft(p, null); tree.addRight(p, null); 17 18 // only internal nodes have entries 19 20 21 22 // store new entry at p // add new sentinel leaves as children 23 24 25 26 27 // Omitted from this code fragment, but included in the online version of the code, // are a series of protected methods that provide notational shorthands to wrap // operations on the underlying linked binary tree. For example, we support the // protected syntax root() as shorthand for tree.root() with the following utility: protected Position> root() { return tree.root(); } 28 29 30 31 32 33 /** Returns the position in p's subtree having given key (or else the terminal leaf).*/ private Position> treeSearch(Position> p. K key) { if (isExternal(p)) return p; int comp = compare(key, p.getElement()); if (comp 34 35 36 // key not found; return the final leaf 37 38 39 // key found; return its position 40 return p: else if (comp < 0) return treeSearch(left(p), key); else 41 // search left subtree 42 43 // search right subtree return treeSearch(right(p), key); } 44 45
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 63% (11 reviews)
private Position treeSearchPosition p K key Position walk p while i...View the full answer
Answered By
Mamba Dedan
I am a computer scientist specializing in database management, OS, networking, and software development. I have a knack for database work, Operating systems, networking, and programming, I can give you the best solution on this without any hesitation. I have a knack in software development with key skills in UML diagrams, storyboarding, code development, software testing and implementation on several platforms.
4.90+
47+ Reviews
114+ Question Solved
Related Book For
Data Structures and Algorithms in Java
ISBN: 978-1118771334
6th edition
Authors: Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
Question Posted:
Students also viewed these Computer science questions
-
Consider lines 3133 of Code Fragment 10.8 in our implementation of the class ChainHashMap. We use the difference in the size of a secondary bucket before and after a call to bucket.remove(k) to...
-
If the outermost while loop of our implementation of quickSortInPlace (line 9 of Code Fragment 12.6) were changed to use condition left < right, instead of condition left /** Sort the subarray S[a.b]...
-
In our implementation of the scale function (page 25), the body of the loop executes the command data[j] *= factor. We have discussed that numeric types are immutable, and that use of the *= operator...
-
You are looking at buying a piece of real estate and you intend to borrow as much as you possibly can from a bank to buy the property. The bank you are dealing with has a requirement that the LVR for...
-
Mercury Company has only one inventory pool. On December 31, 2018, Mercury adopted the dollar-value LIFO inventory method. The inventory on that date using the dollar-value LIFO method was $200,000....
-
Artesa, a leading firm in the semiconductor industry, produces digital integrated circuits (ICs) for the communications and defense markets. For the year ended December 31, 2020, Artesa sold 242,400...
-
Drawing on recent examples, consider the extent to which strike action is likely to help trade union members achieve their various aims.
-
Suds Enterprises makes Perfecto Shampoo for professional hair stylists. On July 31, it had 5,000 liters of shampoo in process that were 80 percent complete in regard to conversion costs and 100...
-
4.21 Case Study Competency IV.1RM Determine diagnosis and procedure codes and groupings according to official guidelines. Competency IV.1 Validate assignment of diagnostic and procedural codes and...
-
Refer to Exercise 7.S.6. Construct a 95% confidence interval for the population mean reduction in stem length. Does the confidence interval indicate whether the effect of stress is "horticulturally...
-
Is the search tree of Figure 11.22(a) a (2,4) tree? Why or why not? Figure 11.22(a) 22 5 10 25 3 4 23 24 6 8 14 27 11 13 17 (a)
-
Dr. Amongus claims that the order in which a fixed set of entries is inserted into an AVL tree does not matterthe same AVL tree results every time. Give a small example that proves he is wrong.
-
During the year 2007, U.S. economic performance deteriorated sharply. Can this decline be blamed on inferior monetary or fiscal policy?
-
If $100 of income tax expense was accrued in January and $75 of the income tax payable was paid during the month, what was the balance in income tax payable at january 1? (Hint: Prepare the adjusting...
-
India is Sri Lanka's third-largest trade partner, and one of the largest contributors to foreign direct investment. The main exports to Sri Lanka include engineering items, skimmed milk powder,...
-
Which statement is true about this command: SELECT Fname+"'+ Lname AS Name FROM Author UNION SELECT FirstName + ' ' + LastName FROM Customers UNION SELECT Name FROM Publisher ORDER BY Name; The...
-
The most dangerous particles in polluted air are those with diameters less than 2.5\mu m because they can penetrate deeply into the lungs. A 15-cm -tall closed container holds a sample of polluted...
-
On July 1, 2020, Jen and King agreed to form a partnership from their respective proprietorship businesses and to share profits equally. Jen and King's balance sheet before the formation were: Jen...
-
Mr. Briggs purchased an apartment complex on January 10, 2015, for $2 million with 10% of the price allocated to land. He sells the complex on October 22, 2017, for $2.5 million. Assume that 10% of...
-
Suppose you won a financial literacy competition and are given FJS10000 to invest, with the condition that investment can be done either in, i) Invest in Unit trust of Fiji or Invest in Fijian...
-
We can improve the running time of quicksort in practice by taking advantage of the fast running time of insertion sort when its input is "nearly" sorted. Upon calling quicksort on a subarray with...
-
Consider a sorting problem in which we do not know the numbers exactly. Instead, for each number, we know an interval on the real line to which it belongs. That is, we are given n closed intervals of...
-
Argue that for any constant 0 < 1/2, the probability is approximately 1 - 2 that on a random input array, PARTITION produces a split more balanced than 1 to .
-
speed of 35 mph set to head due west encounters a wind blowing 15 mph due south. What is the approximate resulting speed of the boat?
-
A canoe rental service charges a $20 transportation fee and $30 dollars an hour to rent a canoe. Write an equation representing the cost, y, of renting a canoe for x hours.
-
Sam ran 63,756 feet in 70 minutes. What is Sam's rate in miles per hour? (There are 5,280 feet in one mile. What is Sam's rate as stated?
Study smarter with the SolutionInn App