Hi there, I'm new to tree maps and I am trying to write my own version of the pre-defined "remove" function for Tree Maps. I know I need to have two extra functions that find the minimum and maximum values in the map that will be called within the remove function, I just don't know if I'm going about this correctly as I'm struggling to fully understand Tree Maps.

Here's what I currently have (only posting the relevant code for now):

Main (creating two arrays and inserting them into the map):

public static void main(String[] args) {

        //Map<String, Integer> people = new TreeMap<String, Integer>();
        Map<String, Integer> people = new SearchTreeMap<String, Integer>();

        String names[] = {
            "jerry", "paul", "erin", "marty", "kevin",
            "sam", "bill", "john", "bob", "rick", "tim",
        };

        Integer ages[] = { 37, 22, 17, 52, 87, 47, 25, 34, 49, 35, 33, };

        for(int i = 0; i < names.length; ++i) {
            people.put(names[i], ages[i]);
        }

        System.out.println(people);
        System.out.println("size = " + people.size());

        if(people instanceof SearchTreeMap) {
            System.out.println("--------------");
            ((SearchTreeMap<String, Integer>) people).reverseInorderOutput();
            System.out.println("--------------");
        }

        System.out.println();
        System.out.println("remove erin: " + people.remove("erin"));
        System.out.println("remove erin: " + people.remove("erin"));
        System.out.println("remove jerry: " + people.remove("jerry"));
        System.out.println("remove paul: " + people.remove("paul"));

        System.out.println(people);
        System.out.println("size = " + people.size());

        if(people instanceof SearchTreeMap) {
            System.out.println("--------------");
            ((SearchTreeMap<String, Integer>) people).reverseInorderOutput();
            System.out.println("--------------");
        }
    }
}

Remove function (so far):

private Node removeMax(Node n, Mutable<K> key, Mutable<V> val) {
      if(n.right == null) {
      val.set(n.value);
      key.set(n.key);
      return n.left;
      }
      else {
          n.right = removeMax(n.right, key, val);
          return n;
  }
  }


 private Node removeMin(Node n, Mutable<K> key, Mutable<V> val) {
      if(n.left == null) {
      val.set(n.value);
      key.set(n.key);
      return n.right;
      }
      else {
          n.left = removeMin(n.left, key, val);
          return n;
  }
  }


  @Override
  public V remove(Object obj) {

      Mutable<K> save = new Mutable<K>();
      Mutable<V> val = new Mutable<V>();

      //TESTING
      Node n = root;
      System.out.println(n.key + " " + n.value);

      //TESTING MIN/MAX FUNCTION RESULTS
      n = removeMin(n, save, val);
      System.out.println(n.key);
      System.out.println(n.value);

      n = removeMax(n, save, val);
      System.out.println(n.key);
      System.out.println(n.value);


    return null;
  }

As you can see, the actual remove function is bare. I haven't yet worked out the logic for it yet because I want to have the MIN/MAX functions correct first.

Here's a sample output of the above code:

run:
[bill=25, bob=49, erin=17, jerry=37, john=34, kevin=87, marty=52, paul=22, rick=35, sam=47, tim=33]
size = 11
--------------
         tim=33
      sam=47
         rick=35
   paul=22
      marty=52
         kevin=87
            john=34
jerry=37
   erin=17
         bob=49
      bill=25
--------------

jerry 37
jerry
37
jerry
37
remove erin: null
jerry 37
jerry
37
jerry
37
remove erin: null
jerry 37
jerry
37
jerry
37
remove jerry: null
jerry 37
paul
22
marty
52
remove paul: null
[jerry=37, john=34, kevin=87, marty=52, paul=22, null, null, null, null, null, null]
size = 11
--------------
   paul=22
      marty=52
         kevin=87
            john=34
jerry=37
--------------

So as you can see it returns the correct minimum and maximum keys/values ONLY on that one function call (lines 37-40). Also, why is it setting things to null? I'm a little confused by this, any suggestions?

I know this may be a lot to take in for one post, so if you need more of an explanation or code, please let me know! Thank you!

Edited 4 Years Ago by Syrne

CSC 241 huh? Here's how I went about:

//This is the public remove method which call the private remove method recursively
 @Override
  public V remove(Object obj){
      if(isEmpty()){
          return null;
      }
      K key = (K) obj;
      V val = (V) obj;
      if(!containsKey(key)){
          return null;
      }
      Mutable<Boolean> found = new Mutable<>();
      root = remove(root, key, val, found);
      if(found.get()){
          --size;
      }
      return val;
  }

  //This recursive primate remove method is similar to the private remove method for SearchTreeSet (see last assignment)
  private Random flipACoin = new Random();
  private Node remove(Node n, K key, V val, Mutable<Boolean> found){
      if(n == null){
          found.set(false);
          return null;
      }
      int comp = myCompare(key, n.key);
      if(comp < 0){
          n.left = remove(n.left, key, val, found);
          return n;
      }
      if(comp > 0){
          n.right = remove(n.right, key, val, found);
          return n;
      }
      found.set(true);
      if(n.left == null){
          return n.right;
      }
      if(n.right == null){
          return n.left;
      }
      Mutable<K> saveK = new Mutable<>();
      Mutable<V> saveV = new Mutable<>();
      boolean choose_min = (flipACoin.nextInt(2) == 1);
      if(choose_min){
          n.right = removeMin(n.right, saveK, saveV);
      }
      else{
          n.left = removeMax(n.left, saveK, saveV);
      }
      n.key = saveK.get();
      n.value = saveV.get();
      return n;
  }

  //Similar to removeMin in SearchTreeSet except that we consider the each node's key and value
  private Node removeMin(Node n, Mutable<K> saveK, Mutable<V> saveV){
      if(n.left == null){
          saveK.set(n.key);
          saveV.set(n.value);
          return n.right;
      }
      else{
          n.left = removeMin(n.left, saveK, saveV);
          return n;
      }
  }

   //Similar to removeMax in SearchTreeSet except that we consider the each node's key and value
  private Node removeMax(Node n, Mutable<K> saveK, Mutable<V> saveV){
     if(n.right == null){
         saveK.set(n.key);
         saveV.set(n.value);
         return n.left;
     }
     else{
         n.right = removeMax(n.right, saveK, saveV);
         return n;
     }
  }

Make sure you change your variable names a little bit.

This article has been dead for over six months. Start a new discussion instead.