Example of a black/red binary search tree

[MT]

(specifically for XtoTheZ, but others may like to critique me)

public class CDCollection {

  CDNode root;

  public CDCollection() {
    root = null;
  }

  public void addCD(CD toAdd) {
    CDNode curr = root, parent = null;
    int direction = 0;
    if (root==null) {
      root = new CDNode(toAdd);
      return;
    }
    for (;;) {
      if(curr==null) {
        if (direction < 0)
          parent.left = new CDNode(toAdd);
        else
          parent.right = new CDNode(toAdd);
        return;
      }
      direction = toAdd.toString().compareTo(curr.data.toString());
      if (direction == 0)
        return;
      parent = curr;
      if (direction < 0)
        curr = curr.left;
      else
        curr = curr.right;
    }
  }

  public boolean contains(CD me) {
    return contains(me,root);
  }

  public boolean contains(CD me, CDNode top) {
    if (top==null)
      return false;
    int direction = me.toString().compareTo(top.data.toString());
    if (direction == 0)
      return true;
    if (direction < 0)
      return contains(me,top.left);
    return contains(me,top.right);
  }

  public void printElems() {
    printElems(root);
  }

  public void printElems(CDNode top) {
    if (top!=null) {
      printElems(top.left);
      System.out.println(top.data.toString());
      printElems(top.right);
    }
  }

  public static void main(String[] args) {
    CDCollection c = new CDCollection();
    CD myfavouritecdever = new CD("When your in love with a beautiful woman","DR HOOK!",9.99,7);
    c.addCD(new CD("My Favourites","Winker",9.99,10));
    c.addCD(new CD("Awful songs","some guy",19.99,5));
    c.addCD(new CD("MT Rocks","A Believer",9.99,22));
    c.addCD(new CD("Rubbish single","Gayboy",9.99,3));
    c.printElems();
    System.out.println(c.contains(myfavouritecdever));
    c.addCD(myfavouritecdever);
    System.out.println(c.contains(myfavouritecdever));
  }

  class CDNode {
    CDNode left;
    CDNode right;
    CD data;

    CDNode(CD data) {
      this.data = data;
    }
  }

}

code which XtoTheZ was supplied with (and enforced to use, otherwise I wouldnt have had to sort on toString method :/)

public class CD {

  private String name,singer;
  private double price;
  private int numtracks;

  public CD(String name, String singer, double price, int numTracks) {
    this.price = price;
    this.singer = singer;
    this.name = name;
    this.numtracks = numTracks;
  }

  public String toString() {
    StringBuffer sb = new StringBuffer();
    sb.append('[');
    sb.append(singer);
    sb.append("] [");
    sb.append(name);
    sb.append("] [");
    sb.append(price);
    sb.append("] [");
    sb.append(numtracks);
    sb.append(']');
    return sb.toString();
  }
}

[xtothez]

MT rocks.


However:
[21:52] <XtoTheZ> as tempted as i am to hand that in, i'll can bet they'll come and ask me what it means
[21:52] <XtoTheZ> and as i dont have a fking clue...
[21:53] <@MT> heh

[queball]

That's not red/black, that's just a normal binary tree, you utter tard.

[queball]

that's my critque btw

[MT]

you right as always, i just wanted to simulate interest!

[MT]

Originally posted by MT
you right as always, i just wanted to simulate interest!

Translation: I was shit and got it wrong.

whats red/black searching then ?

[Gayle29uk]

Originally posted by Idi
whats red/black searching then ?

http://www.cis.ohio-state.edu/~gurar...is680Ch11.html

I never really understood them so I've never used one. Good job I've never had to sort a large data pool

Originally posted by Gayle28uk
http://www.cis.ohio-state.edu/~gurar...is680Ch11.html

I never really understood them so I've never used one. Good job I've never had to sort a large data pool

i have decided i dislike red/black search trees. they make my head turn gloopy.

[Nodrog]

Red black trees are horrible. Its one of those things you get forced to learn in academia algorithm classes, but I suspect youd never ever use them outside of college, unless you were building a data structures library from scratch, which is something about 1 in 100043 people will do.

I COULD BE WRONG THOUGH!!

[W]

Originally posted by Nodrog
Red black trees are horrible. Its one of those things you get forced to learn in academia algorithm classes, but I suspect youd never ever use them outside of college, unless you were building a data structures library from scratch, which is something about 1 in 100043 people will do.

I COULD BE WRONG THOUGH!!

There are other, better, ways at getting a good binary search tree. So even if you do build a data structures library from scratch (assuming it has some functional purpose, and isn't just for educational purposes) you won't really use it anyway. Or so I seem to recall from way back when I learned the stuff.

[Nodrog]

Originally posted by W
There are other, better, ways at getting a good binary search tree. So even if you do build a data structures library from scratch (assuming it has some functional purpose, and isn't just for educational purposes) you won't really use it anyway. Or so I seem to recall from way back when I learned the stuff.

hmmm, ill take your word for it if youve actually studied it to any level. As far as I know however, r/b is the most allround efficient binary tree in existence, and its used quite often within libraries. Java Collections makes use of it for quite a few things iirc, although I dont know aobut any other popular libraries.