Our implementation of the treeSearch utility, from Code Fragment 11.3, relies on recursion. For a large unbalanced tree, it is possible that Java€™s call stack will reach its limit due to the recursive depth. Give an alternative implementation of that method that does not rely on the use of recursion.

Transcribed Image Text:

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