0

Take for example the assignment I'm working on. We're to use a binary search tree for one piece of a set of data and then a linked list for another piece in the set. The suggested method by the professor was:

struct treeNode
{
    data * item;
    treeNode *left, *right;
};

struct listNode
{
    data * item;
    listNode *next, *prev;
};

class collection
{
public:
         ........
}

Where data is a class containing the particulars of each record. Obviously as it's set up, a treeNode can't exist in the linked list.

Wouldn't it be much simpler to:

struct node
{
    data * item;
    node *listNext, *listPrev, *treeLeft, *treeRight;
};

then we can declare:

node * listHead;
node * treeRoot;

and include both insertion algorithms into the class.

Is there something I'm missing?

3 Answers 3

0

Actually, the data items are to be inserted into both lists. The (mundane) purpose of the assignment is to sort the data sets in two different elements in the set.

So with that said, wouldn't I be saving memory? Combining the 2 nodes I end up with 5 pointers, if I left them separate I'd be using 6. Also I really only have one group of data this way. if I had 250 data items to keep track of, I'd have one group of 1250 pointers instead of 2 lists of 750. Maybe I'm misunderstanding what actually gets allocated with pointer calls.

0

You can do that, but you are wasting memory with the extra pointers. Also, it tends to be more confusing to mix types like that. Am I correct in assuming that the data is either put into the list or put into the tree, but not inserted into both? There's really not much reason to have them both use the same structure if they are different data types anyway. If you are inserting the same data into both types, you could potentially switch from traversing the tree to traversing the list if you had any use for such an action.

Since you're inserting the data into both lists, It would save memory to use your composite node structure. I would insert into the binary tree first, then insert the allocated node into the linked list. You wouldn't really end up with a pure linked list or a binary search tree, but it would be able to be traversed like either one.

0

What was the answer?

If your data is less than (hmmm) megabytes, don't worry about memory consumption. 1 or 2 Gigabytes is typical in normal computers today.

How big are the items? 32 char? 64k of compressed multimedia? Something big?

How reasonable is it to organize one item using both techniques? If the data are really the same, then a 5 pointer structure is interesting- someone could find a node in one ordering and then browse related nodes in the other ordering.

Are the items unrelated, some chalk, some cheese? Are they multidimensional? personnel records? Audio file descriptions? Recipes?

In school, a good teacher is trying to give you experience with common techniques and disciplines. Just like art class, or composition. Pencil, pastels, 5 paragraph essay. So the teacher might want you to write two different classes & constructors. Use one struct for one part of the data, different one for other data. Or the same. Just because.

Outside of school, the data comes in a format and there are operations desired on it/with it. "Use cases" are stories about how data is used, what has to be kept, what algorithms are used.

The point of this might be bimodal searching, 2 pairs of orthogonal pointers. It might be Unions, where each item is asssociated with a list or a tree, but not both at the same time. It might be a flurry of lightwieght subsets, trees and lists, that are compared and contrasted...

When in doubt, "data structures + algorithms = programs". But it pays to know what point the teacher is trying to make, and whether you want to follow their lead. (Usually, in school, you do.)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.