Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

C++ Programming

Binary Search Tree


Hi,

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

thanks

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

> "Defected" writes:

>> 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.

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 Wikstrm

* Erik Wikstrm:

> On 2007-05-19 18:35, osmium wrote:
>> "Defected" writes:

>>> 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.

> 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.

--
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?

Defected wrote:
> Hi,

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

> thanks

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

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

Alf P. Steinbach wrote:
> * Erik Wikstrm:
>> Not really, a map is a class

A map is not necessarily 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,

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/products/ocaml_for_scientists/?usenet

* Jon Harrop:

> Alf P. Steinbach wrote:
>> * Erik Wikstrm:
>>> Not really, a map is a class

> 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.

>>> 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,

> 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.

--
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?

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

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

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

You mean this one?
http://books.google.com/books?id=NLngYyWFl_YC&pg=PA273&vq=red-black+t...

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

Good show, Zeppe!

osmium wrote:
> "Defected" writes:

>> 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.

What book are you referring to? Guess its not the C++ Templates book.
Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc