Hi folks,

Going to try to make this challenge pretty open-ended, and I won't be choosing winners in this one. I will, however, criticize your work and offer [hopefully] helpful suggestions to improve any design you make. I would like this challenge to be educational, but if you submit an undoubtedly horrendous design, prepare to get slammed for it.

The challenge this time is to use C++ template classes to create a tree data structure with the following requirements:

• High efficiency.
  By "efficiency" I refer to memory usage and speed. You can choose which is more important to you, because in most cases, there is a tradeoff between the two. But be sure to say what your particular goal is.
• Methods for insertion, deletion, searching, and serialization.
  You should be able to add, remove, and search for keyed data in your tree structure. "Serialization" refers to the ability to convert the data to a much more linear datatype (like an array).
  Ideally, the array this outputs should be sorted (which isn't hard to achieve if your tree is working properly), but it is not mandatory that it be sorted.
• Compact and clean code.
  Don't include any extra junk in your code. Make it simple to understand and read. Add comments where necessary, but don't go crazy with them. Just describe stuff that isn't plainly obvious by reading the code.
  You can include debugging stuff to help yourself and others debug your tree, but be sure that it's optional (i.e. something you have #ifdef'd out that's only enabled by defining 'DEBUG' or something). Also be sure that any tree code does not print out anything to stdout, stderr, or a file when you have your debugging code disabled (when the debugging code is enabled, of course it's permitted). The only exception for tree code is that file input/output is allowed when you provide options for serializing the structure to a file (a Save/Load functionality). You also can have standard input/output in any test code that uses the tree class, if you want to demonstrate how it works or print out timings, etc.
  When you put code on the board, please use 'code' bbtags to make sure the spacing and so forth is properly preserved. And as far as coding style goes, do your best to follow these helpful guidelines that the Linux kernel developers use.
• Design Explanation
  Don't just paste your code and click 'Submit'. First explain what makes your tree particularly unique, what design goals you had in mind, and how well you think you did at achieving those goals.
• Research
  You are absolutely free to look at code on the internet and get ideas for your own tree. If you've never written a tree before, I suggest you start here. For more interesting ideas, look at AVL trees, red-black trees, splay trees, and so forth.

The interface for the class should be as follows (you can add other functions if you want, but the basic interface must contain these in order for me to review it):

• Tree ()
  The default constructor.
• ~Tree ()
  The destructor.
• bool insert (Key const &_key, Data const &_data)
  Inserts data into the tree.
• bool erase (Key const &_key)
  Deletes a node from the tree, specified by the node's key.
• bool find (Key const &_key, Data &_data) const
  Finds a node in the tree and copies the data from that node to a specified location.
• Data find (Key const &_key) const
  Finds a node in the tree and returns the data at that node.
• bool exists (Key const &_key) const
  Tests whether a key is in the tree or not.
• void empty ()
  Empties the entire tree, but makes no effort to free any of the Data itself, just the Keys (data should be manually freed by the programmer via iterating through an array created by ConvertToDArray, or automatically freed if they're basic types).
• size_t size () const
  Indicates the size of the tree.
• bool replace (Key const &_key, Data const &_data)
  Change the data at the given node.
• DArray< Data > *ConvertToDArray () const
  Converts the tree data into a linearized DArray. The indices of the DArray returned by this function should correlate to the keys at the same indices in the return from the ConvertIndexToDArray() function.
• DArray< Key > *ConvertIndexToDArray () const
  Converts the tree keys into a linearized DArray. The indices of the DArray returned by this function should correlate to the keys at the same indices in the return from the ConvertToDArray() function.
• size_t mem_usage () const
  Returns the memory usage of the tree and its nodes.

Have fun! I might change things above as the challenge progresses.

UPDATE: Amended to drop functions to handle single-key/multiple-data items. Also updated the spec for the DArray conversions.

Were you planning on giving out this mysterious DArray class at all, old chap?

Hairs on a bobbin, old bunt. Hairs on a BOBBIN.

And it's in CrissCross, along with other trees people can base their code on.

The CrissCross source follows linux kernel coding style guidelines, does it?

Not yet. Let me uncrustify it and get back to you.

I don't trust it. It's a lie. You can't make JAVA beautiful.

You can beautify it, but that doesn't make it -beautiful-, per se.

Anyway, I've uncrustified the CrissCross source. Latest SVN looks much more like Linux kernel-style coding.

Its like drawing flowers on the goatse picture. It has been beautified, but it doesn't make it beautiful.

I wish I had skills like you guys.

The only bit of coding I know is some minor dabbles in Visual Basic 6.

Can you hold for say, seven years? I'll be back after I finish High School, and then College, and then I'll be able to rub my beard and go "Hmmm" with the rest of you, sitting in a nice chair and sipping from a mug which says "Actuary of the Year" or some craziness.

I didn't assign an end date for this challenge, so you can complete it whenever you're able.

Also, interesting note: one of my roommates is trying this challenge out. He's got some interesting ideas he's playing with.

Dang smart college people.

We're not even discussing programming in my computer class, apparently we will be using Excel for the rest of our lives.

I don't remember enough about C++ to even attempt this challenge lol.

Oddly, I had just got done writing a QuadTree in C# before this challenge was posted lol.

Is your computer class a programming class? 'Cuz that's what I'm tkaing. Day 1 of school, we were already compiling code. (Granted, it was horrifically basic review... but it was still programming.)

But anyhow, we never got far enough in my Programming 1 class (which uses C++ for the language du jour) to learn about trees or anything... IIRC, we got as far as input/output streams before the year ended.

Guess I'll be joining the observers who nod and make affirmative grunts, all the while thinking "what the holy ass are they talking about?! D':"

-- Griffinhart

The first college-level programming class I took basically covered input/output and that was it. One assignment involved taking a massive text file containing the entire New Testament of the King James Version of the Bible, and allow it to be searched by book, chapter, verse, etc.

Naturally, while everyone else was using an array for searching (pretty much the worst application for an array), I was using an AVL tree.

I did something like this in java, a kd-bucket tree with the dividing hyperplanes placed independantly of the data. I used a type of k-d bounding box efficently test if a better data point (in case of nn) or if a data point could exist at all down the branch (in the case of range searches).

For this particular challenge this is overkill since it only requires a single dimension tree.

However I have grown far to acustom to the class layout of Java and I doupt I could create anything efficient in C++ anymore.