Binary Search Tree

Hi,

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


thanks

re: Binary Search Tree

"Defected" writes:
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.

re: Binary Search Tree

On 2007-05-19 18:35, osmium wrote: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

--
Erik Wikström

re: Binary Search Tree

* Erik Wikström: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.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

re: Binary Search Tree

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

re: Binary Search Tree

"Defected" writes:
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.

re: Binary Search Tree

Alf P. Steinbach wrote:A map is not necessarily a class.
A red-black tree is not necessarily a search tree. It could be used to
implement a grab bag, for example.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/product...ntists/?usenet

re: Binary Search Tree

* Jon Harrop: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.

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.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

re: Binary Search Tree

Alf P. Steinbach wrote: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.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/product...ntists/?usenet

re: Binary Search Tree

Jon Harrop wrote:You mean this one?
http://books.google.com/books?id=NLn...CM97qRrFFTYMzc

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

re: Binary Search Tree

"Zeppe" wrote:
Good show, Zeppe!

re: Binary Search Tree

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