Binary Search Tree

[Defected]

Hi,

How i can create a Binary Search Tree with a class ?


thanks

 

[osmium]

How i can create a Binary Search Tree with a class ?

The wordsmiths at C++ decided that right word for "tree" was "map". So get
out your handy-dandy copy of Josuttis and go from there. Page 194.

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

The wordsmiths at C++ decided that right word for "tree" was "map". So get
out your handy-dandy copy of Josuttis and go from there. Page 194.

Not really, a map is a class that allows you to map a key to a value and
have some guarantees on how fast some operations can be performed, on
most implementations a red-black tree, which is not a binary search tree.

To the OP:

To create a binary search tree you should probably have two classes, one
for the nodes and one for the tree. The nodes will be quite simple, they
only have to contain a value and links to child-nodes (and perhaps one
for the parent). The other class contains information about the tree
(number of nodes and so on) and a link to the root-node. It also
contains methods to insert, find, delete and so on. How to perform those
operations on the tree should be in your book on algorithms and data-
structures (or google if you don't have a book).

If you get any problems with getting the code to work then come back
here and post your code and describe your problem. However before
posting read the relevant sections of the FAQ first:

http://www.parashift.com/c++-faq-lite/how-to-post.html

 

[Alf P. Steinbach]

* Erik Wikström:

Not really, a map is a class that allows you to map a key to a value and
have some guarantees on how fast some operations can be performed, on
most implementations a red-black tree, which is not a binary search tree.

On the contrary, a red-black tree is a binary search tree, more
specifically a specific kind of self-balancing binary search tree.

But on the third hand, there's no guarantee std::map is implemented as a
red-black tree.

However, that's the most common implementation, and std::map offers the
same performance characteristics as a binary search tree.

 

[crh]

Hi,

How i can create a Binary Search Tree with a class ?


thanks

Look at this one implementation: http://phpfi.com/235365

 

[osmium]

How i can create a Binary Search Tree with a class ?

I see now that I didn't read the question closely enough, sorry about that.
The question is how to _create_ and my resposne was how to _use_.

The best write up I know of is in _Algorithms + Data Structures = Programs_
by Nicklaus Wirth. You will probably need access to a good college library
to find it.

The hardest part is comprehending the delete function. Save that for the
last thing you do.

 

[Jon Harrop]

* Erik Wikström:

A map is not necessarily a class.

On the contrary, a red-black tree is a binary search tree,

A red-black tree is not necessarily a search tree. It could be used to
implement a grab bag, for example.

 

[Alf P. Steinbach]

* Jon Harrop:

A map is not necessarily a class.

You snipped a lot of context there: Erik's statement that you quoted the
start of was about std::map. And you leave us wondering whether that
snipping and apparent "misunderstanding" is intentional or not. Not the
least, considering your recent language advocacy postings, which were
borderline trolling, as was this.

A red-black tree is not necessarily a search tree. It could be used to
implement a grab bag, for example.

Go get yourself a cup of coffee, then start your change of the world's
terminology by fixing what you can fix, e.g. Wikipedia.

 

[Jon Harrop]

Go get yourself a cup of coffee, then start your change of the world's
terminology by fixing what you can fix, e.g. Wikipedia.

Ah yes, the encyclopaedia by children for children. Anyone reaching for that
to learn about data structures (or anything else) is asking for trouble.
I'd recommend Cormen et al.

 

[Zeppe]

Ah yes, the encyclopaedia by children for children. Anyone reaching for that
to learn about data structures (or anything else) is asking for trouble.
I'd recommend Cormen et al.

You mean this one?
http://books.google.com/books?id=NL...rithms+Cormen&sig=yd0Gq55nV9OzYCM97qRrFFTYMzc

it seems like you have to edit this one as well, because it seems to
agree with wikipedia, the encyclopaedia by children for children.

Regards,

Zeppe

 

[osmium]

You mean this one?
http://books.google.com/books?id=NL...rithms+Cormen&sig=yd0Gq55nV9OzYCM97qRrFFTYMzc

it seems like you have to edit this one as well, because it seems to agree
with wikipedia, the encyclopaedia by children for children.

Good show, Zeppe!

 

[desktop]

The wordsmiths at C++ decided that right word for "tree" was "map". So get
out your handy-dandy copy of Josuttis and go from there. Page 194.

What book are you referring to? Guess its not the C++ Templates book.