Go Back   MacRumors Forums > Apple Systems and Services > Programming > Mac Programming

Reply
 
Thread Tools Search this Thread Display Modes
Old Apr 22, 2006, 12:15 PM   #1
grapes911
Demi-God (Moderator emeritus)
 
grapes911's Avatar
 
Join Date: Jul 2003
Location: Citizens Bank Park
Red-Black Trees

I have to implement a red-black tree in C++ for a project, but I don't know much about red-black trees. I've been trying to do my research for a few days now, but I still feel pretty lost.

1. Here is what I know:
a. They are binary trees.
b. Every node is either red or black.
c. The root is black.
d. Every path from the root to a leaf contains the same number of black nodes.
e. Red nodes can only have black children.
f. Every leaf is NULL and black.

2. Are this properties correct? Are there any other properties that I need to know?

3. I'm assuming it is more common to use an array rather than pointers. Is this true?

4. What make a node red or black? And what advantage do I get out of having red and black nodes.

5. Anyone know of any good sites with good examples?
__________________
grapes911 is offline   0 Reply With Quote
Old Apr 22, 2006, 12:30 PM   #2
Mitthrawnuruodo
Moderator
 
Mitthrawnuruodo's Avatar
 
Join Date: Mar 2004
Location: Bergen, Norway
Introductions to Algorithms has a whole chapter (13) dedicated to Red-Black threes, but I'm afraid I cannot type in those 30 pages here...

Maybe they have the book at your local public library. They don't provide code, but even better, the algorithm in a very easy-to-understand notation.

I don't think we ever implemented the algorithm in either of my C++ or Java courses...

Edit: On the other hand, Google is a friend, as ever: http://www.cs.fiu.edu/~weiss/dsaa_c++/code/
__________________
Those who fail to learn history are doomed to repeat it; those who fail to learn history correctly... why, they are simply doomed.
Mitthrawnuruodo is offline   0 Reply With Quote
Old Apr 22, 2006, 04:49 PM   #3
cait-sith
macrumors regular
 
Join Date: Apr 2004
Location: canada
Is this for a university course?
__________________
"`The first ten million years were the worst,' said Marvin, `and the second ten million, they were the worst too. The third ten million I didn't enjoy at all. After that I went into a bit of a decline.'"
cait-sith is offline   0 Reply With Quote
Old Apr 22, 2006, 05:08 PM   #4
grapes911
Thread Starter
Demi-God (Moderator emeritus)
 
grapes911's Avatar
 
Join Date: Jul 2003
Location: Citizens Bank Park
Quote:
Originally Posted by Mitthrawnuruodo
Introductions to Algorithms has a whole chapter (13) dedicated to Red-Black threes, but I'm afraid I cannot type in those 30 pages here...

Maybe they have the book at your local public library. They don't provide code, but even better, the algorithm in a very easy-to-understand notation.

I don't think we ever implemented the algorithm in either of my C++ or Java courses...

Edit: On the other hand, Google is a friend, as ever: http://www.cs.fiu.edu/~weiss/dsaa_c++/code/
I have some books (none with very good examples). I'm having trouble just understanding the concept, let alone the code. Thank you though.

Quote:
Originally Posted by cait-sith
Is this for a university course?
Yep.
__________________
grapes911 is offline   0 Reply With Quote
Old Apr 22, 2006, 07:37 PM   #5
Mitthrawnuruodo
Moderator
 
Mitthrawnuruodo's Avatar
 
Join Date: Mar 2004
Location: Bergen, Norway
Quote:
Originally Posted by grapes911
I have some books (none with very good examples). I'm having trouble just understanding the concept, let alone the code. Thank you though.
Well, that's the brilliant thing about the above mentioned Algorithm book. It explains how the trees work, in detail, with illustrations...
__________________
Those who fail to learn history are doomed to repeat it; those who fail to learn history correctly... why, they are simply doomed.
Mitthrawnuruodo is offline   0 Reply With Quote
Old Apr 23, 2006, 03:30 AM   #6
Voidness
macrumors 6502a
 
Voidness's Avatar
 
Join Date: Aug 2005
Location: Null
When I had an assignment to implement an AVL Tree last semester, I found this Java applet to be helpful in understanding the concept. It also has a mode for Red-Black Trees, which I didn't study:

http://webpages.ull.es/users/jriera/...e%20applet.htm

Also, Wikipedia has a detailed entry for Red-Black Trees:

http://en.wikipedia.org/wiki/Red-black_tree


Hope this helps.

Just curious, which language are you using? I used C++ with my AVL tree.
__________________
TextCrafter for iOS ~ Craft & Share Text
void...
Voidness is offline   0 Reply With Quote
Old Apr 23, 2006, 07:16 PM   #7
superbovine
macrumors 68030
 
superbovine's Avatar
 
Join Date: Nov 2003
http://www.ddj.com/184410531

one of the containers in the STL is a red-black tree (if remember right), anyway if you dig around you can probably find a good example from the stl.
superbovine is offline   0 Reply With Quote

Reply
MacRumors Forums > Apple Systems and Services > Programming > Mac Programming

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Similar Threads
thread Thread Starter Forum Replies Last Post
Black and Red Speck Candyshell Case iphoneguy4life iPhone Accessories 3 Oct 4, 2012 12:02 AM

Forum Jump

All times are GMT -5. The time now is 05:47 PM.

Mac Rumors | Mac | iPhone | iPhone Game Reviews | iPhone Apps

Mobile Version | Fixed | Fluid | Fluid HD
Copyright 2002-2013, MacRumors.com, LLC