Modify the binary search tree implementation to make it an AVL tree. public clas

Question

Modify the binary search tree implementation to make it an AVL tree. public class BinarySearchTreeND < K extends Comparable < ? super K > > // ANY class that extends the base comparable type (K) // of this data structure instance may be inserted { static final int DEPTHDELTA = 5; // used to create a text tree display BSTNodeND < K > root = null; public void insert (K d) { insertNode (new BSTNodeND < K > (d)); } // end insert, public version public void insertNode (BSTNodeND < K > n) { if (root == null) root = n; else insertNode (n, root); } // end insert Node public K find (K d) { if (root == null) return null; BSTNodeND < K > t = findValue (d, root); return (t==null)?null:t.data; } // end find method public K max () { if (root == null) return null; return findMax(root).data; } // end max method public int getSize () { return getSize (root);} public void remove (K d) { root = remove (d, root); } // end remove data public String toString () { if (root == null) return null; return toString(root);} private void insertNode (BSTNodeND < K > d, BSTNodeND < K > n) { d.parent = n; if (d.data.compareTo (n.data) > 0) if (n.right == null) n.right = d; else insertNode (d, n.right); else if (n.left == null) n.left = d; else insertNode (d, n.left); } // end method insertNode private BSTNodeND < K > findValue (K d, BSTNodeND < K > n) { if (n.data.compareTo(d) == 0) return n; if (n.data.compareTo (d) > 0) return (n.left==null)?null:findValue (d, n.left); return (n.right == null)?null:findValue(d, n.right); } // end findValue private BSTNodeND < K > findMax (BSTNodeND < K > n) { if (n.right == null) return n; return findMax(n.right); } // end findValue private int getSize (BSTNodeND < K > t) { if (t == null) return 0; return getSize (t.left) + getSize (t.right) + 1; } // end getSize node private BSTNodeND < K > removeRoot (BSTNodeND < K > t) { if (t.left == null) { if (t.right != null) t.right.parent = t.parent; return t.right; } if (t.right == null) { t.left.parent = t.parent; // t.left != null because of earlier if test case return t.left; } BSTNodeND < K > newTop = findMax(t.left); remove (newTop.data, t); // lose the node instance, leave tree intact t.data = newTop.data; // just replace the data at the internal node return t; } // end remove data, tree private BSTNodeND < K > remove (K d, BSTNodeND < K > t) { if (t == null) return null; if (d.compareTo (t.data) < 0) t.left = remove (d, t.left ); else if (d.compareTo (t.data)> 0) t.right = remove (d, t.right); else // d equals t.data t = removeRoot (t); return t; } // end remove data, tree private String toString (BSTNodeND < K > n) { return toTreeString (5, n, '>'); } // end toString // removed use of parent reference, added label parameter, 5/13/2012 private String toTreeString (int depth, BSTNodeND < K > n, char label) { // depth = 0 is bad return ((n.left == null)?"":toTreeString (depth + DEPTHDELTA, n.left, '/')) + String.format ("%" + depth + "s%s ", label, n) // ND: fixed 4/17/2009 + ((n.right == null)?"":toTreeString (depth + DEPTHDELTA, n.right, '\')); } // end method toTreeString private String toInOrderString (BSTNodeND < K > n) { return ((n.left == null)?"":toInOrderString(n.left )) + n + " " + ((n.right == null)?"":toInOrderString(n.right)); } // end toInOrderString private String toPreOrderString (BSTNodeND < K > n) { return n + " " + ((n.left == null)?"":toPreOrderString(n.left )) + ((n.right == null)?"":toPreOrderString(n.right)); } // end toPreOrderString private String toPostOrderString (BSTNodeND < K > n) { return ((n.left == null)?"":toPostOrderString(n.left )) + ((n.right == null)?"":toPostOrderString(n.right)) + n + " "; } // end to PostOrderString // See: http://en.wikipedia.org/wiki/Tree_traversal private String toLevelOrderString (BSTNodeND < K > n) { String st = ""; BSTNodeND < K > node; java.util.ArrayDeque < BSTNodeND < K > > q = new java.util.ArrayDeque < BSTNodeND < K > > (); q.add (n); // start queue by adding this (root?) to queue while (q.size() > 0) { node = q.remove(); // remove the head of queue st += (node.data + " "); // process head data to String if (node.left != null) q.add (node.left); // insert left child at end of queue if (node.right != null) q.add (node.right); // insert right child at end or queue } // end queue processing return st.toString(); } // end to LevelOrderString // main and example methods follow public static void main (String args []) { integerExample (); stringExample (); Scanner st = new Scanner (System.in); while (menu(st)); System.out.println ("...Bye"); } // end main static boolean menu (Scanner st) { System.out.println ("enter integer values, q to quit:"); String line = st.nextLine(); if (line.length() == 0) return true; // just causes crash on next line Scanner tokens = new Scanner (line).useDelimiter ("[,\s]+"); // allow comma+space separators if (! tokens.hasNextInt()) if (tokens.hasNext() && tokens.next().equalsIgnoreCase ("q")) return false; else return true; BinarySearchTreeND tree = new BinarySearchTreeND (); while (tokens.hasNextInt()) tree.insert (tokens.nextInt()); System.out.println ("Tree: " + tree); System.out.println ("Tree in-order: " + tree.toInOrderString (tree.root)); System.out.println ("Tree pre-order: " + tree.toPreOrderString (tree.root)); System.out.println ("Tree post-order: " + tree.toPostOrderString (tree.root)); System.out.println ("Tree level-order: " + tree.toLevelOrderString(tree.root)); if (tokens.hasNext() && tokens.next().equalsIgnoreCase ("q")) return false; return true; } // end menu public static void integerExample () { BinarySearchTreeND < Integer > x = new BinarySearchTreeND < Integer > (); int arr [] = { 40, 20, 60, 10, 30, 50, 70, 5, 15, 25, 35, 45, 55, 65, 75, 60, 45, 50, 40, 55, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 }; int rem [] = {}; for (int y: arr) x.insert (y); System.out.println ("X: " + x); System.out.println ("X in-order: " + x.toInOrderString(x.root)); System.out.println ("X pre-order: " + x.toPreOrderString(x.root)); System.out.println ("X post-order: " + x.toPostOrderString(x.root)); System.out.println ("X level-order: " + x.toLevelOrderString(x.root)); Integer t = x.find(10); System.out.println ("find: " + t); System.out.println ("find: " + x.find(20)); System.out.println ("Size: " + x.getSize()); System.out.println ("MAX: " + x.max()); for (int y: rem) { System.out.println ("Removing: " + y); x.remove (y); System.out.println ("result: " + x); } System.out.println ("X: " + x); } // end integerExample public static void stringExample () { // The following is an example using a user-defined class, see below // notice the use of the generic parameter Example String [] sa = {"one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"}; BinarySearchTreeND < Example > ex = new BinarySearchTreeND < Example > (); for (String s: sa) ex.insert (new Example (s)); System.out.println ("Example using strings: " + ex); } // end stringExample // needs to be internal class so, eg, AVLNode in AVLND can extend this internal node class class BSTNodeND < L extends Comparable< ? super L > > { L data; BSTNodeND < L > left, right, parent; BSTNodeND (L d) {data = d;} BSTNodeND (L d, BSTNodeND p) {data = d; parent = p;} public String toString () { return data.toString();} // end toString method } // end class BSTNodeND } // end class BinarySearchTreeND // A class that can be used with the BinarySearchTreeND data structure // Notice the use of the generic parameter Example class Example implements Comparable < Example > { String data; public Example (String d) { data = d;} // you, of course, will want a more interesting compareTo method public int compareTo (Example e) { return data.compareTo (e.data); } // end compareTo method public String toString () { return data; } // end toString } // end class Example

Explanation / Answer

please write the code with proper indentation,so that it will be easy to understand by others.

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.