|
12 Jan 2003, 22:40
|
#1
|
/dev/zero Retired Mod
Join Date: May 2000
Posts: 415
|
Example of a black/red binary search tree
(specifically for XtoTheZ, but others may like to critique me)
Code:
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 :/)
Code:
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();
}
}
__________________
#linux : Home of Genius
<idimmu> ok i was chained to a desk with this oriental dude
|
|
|
12 Jan 2003, 22:57
|
#2
|
ŻŻŻŻŻŻŻŻŻ
Join Date: May 2001
Location: Sept 2057
Posts: 1,813
|
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
__________________
in my sig i write down all my previous co-ords and alliance positions as if they matter because I'm not important enough to be remembered by nickname alone.
|
|
|
13 Jan 2003, 00:13
|
#3
|
Ball
Join Date: Oct 2001
Posts: 4,410
|
That's not red/black, that's just a normal binary tree, you utter tard.
|
|
|
13 Jan 2003, 00:14
|
#4
|
Ball
Join Date: Oct 2001
Posts: 4,410
|
that's my critque btw
|
|
|
13 Jan 2003, 00:25
|
#5
|
/dev/zero Retired Mod
Join Date: May 2000
Posts: 415
|
you right as always, i just wanted to simulate interest!
__________________
#linux : Home of Genius
<idimmu> ok i was chained to a desk with this oriental dude
|
|
|
13 Jan 2003, 00:25
|
#6
|
/dev/zero Retired Mod
Join Date: May 2000
Posts: 415
|
Quote:
Originally posted by MT
you right as always, i just wanted to simulate interest!
|
Translation: I was shit and got it wrong.
__________________
#linux : Home of Genius
<idimmu> ok i was chained to a desk with this oriental dude
|
|
|
13 Jan 2003, 00:30
|
#7
|
Guest
|
whats red/black searching then ?
|
|
|
13 Jan 2003, 01:02
|
#8
|
Bitch
Join Date: Jun 2002
Location: North Yorkshire
Posts: 3,848
|
Quote:
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
__________________
ACHTUNG!!!
Das machine is nicht fur gefingerpoken und mittengrabben. Ist easy
schnappen der springenwerk, blowenfusen und corkenpoppen mit
spitzensparken. Ist nicht fur gewerken by das dummkopfen. Das
rubbernecken sightseeren keepen hands in das pockets. Relaxen und vatch
das blinkenlights!!!
|
|
|
13 Jan 2003, 01:17
|
#9
|
Guest
|
i have decided i dislike red/black search trees. they make my head turn gloopy.
|
|
|
13 Jan 2003, 01:33
|
#10
|
Registered User
Join Date: Jun 2000
Posts: 8,476
|
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!!
|
|
|
13 Jan 2003, 04:23
|
#11
|
Gubbish
Join Date: Sep 2000
Location: #FoW
Posts: 2,323
|
Quote:
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.
__________________
Gubble gubble gubble gubble
|
|
|
13 Jan 2003, 06:19
|
#12
|
Registered User
Join Date: Jun 2000
Posts: 8,476
|
Quote:
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.
|
|
|
|
All times are GMT +1. The time now is 19:18.
| |