What methods are useful in a BTree?

[Nobody]

I am trying to write a BTree class, just wondering if I missed any useful
methods. This is my class definition so far (excuse the MFC portions, its a
project requirement):

template <class TYPE, class ARG_TYPE = const TYPE&>

class CBTree : public CObject

{

// Constructors

public:

CBTree();

// Operations

public:

// InsertNode

// DeleteNode

// GetRootNode

// GetLeftNode

// GetRightNode

// GetParentNode

// void RemoveAll();

// BOOL IsEmpty() const;

// Implementation

public:

virtual ~CBTree();

};

Would GetNodeCount() be useful in a BTree class? How about a copy
constructor?

I'm thinking it might be cool to have some kind of wrapper functions for
navigating the tree pre-order, in-order and post-order rather then just node
accessor functions?

Thanks.

 

[Gianni Mariani]

I am trying to write a BTree class, just wondering if I missed any useful
methods. This is my class definition so far (excuse the MFC portions, its a
project requirement): ....

Would GetNodeCount() be useful in a BTree class? How about a copy
constructor?

std::map is a good place to start.

 

[John Harrison]

I am trying to write a BTree class, just wondering if I missed any useful
methods. This is my class definition so far (excuse the MFC portions, its a
project requirement):

template <class TYPE, class ARG_TYPE = const TYPE&>

class CBTree : public CObject

{

// Constructors

public:

CBTree();

// Operations

public:

// InsertNode

// DeleteNode

// GetRootNode

// GetLeftNode

// GetRightNode

// GetParentNode

I wouldn't have any of the above.

Inserting nodes it an implementation detail, the user of a btree is
iterested in inserting values, not nodes. Have InsertValue and construct the
node internally in that method. Ditto replace DeleteNode with DeleteValue.

GetRoot etc can only be useful in iterating through the tree, again they are
implementation details. You should write a seperate iterator class which
starts iterating at the beginning or end of the tree and can move forwards
or backwards though it.

You are thinking too much in terms of implementation, not in terms of what
the user actually wants.

// void RemoveAll();

// BOOL IsEmpty() const;

// Implementation

public:

virtual ~CBTree();

};

Would GetNodeCount() be useful in a BTree class?

Yes, knowing the size of a BTree is definitely useful. But again, the user
doesn't care about nodes, rename GetNodeCount as GetSize.

How about a copy
constructor?

Absolutely, and an assignment operator.

I'm thinking it might be cool to have some kind of wrapper functions for
navigating the tree pre-order, in-order and post-order rather then just node
accessor functions?

Yes definitely. As I said already get rid of the node accessor functions.

Thanks.

You've missed out a Find or IsMember type function. That could return a
boolean, but even better would be for it two return one of you navigation
wrapper objects, so you can start navigating at the point where you found
the value.

Look at the STL classes std::set or std::map for a good btree like
interface.

john

 

[Claudio Puviani]

I am trying to write a BTree class, just wondering if I missed any useful
methods.

Firstly, it's apparent to me from your code snippet that what you're talking
about is a binary tree and not a B-tree.

Either way, you need to decide if what you're writing is a fundamental data
structure (like a raw tree) or an abstract data type (like a container). A FDS
is useful as a building block for ADTs, but not very usable on its own. An ADT
gives you a usable interface, but you deliberately give up access to some of the
properties of the underlying data structure.

For example, std::set and std::map are typically built on top of a red-black
tree (a transformation of a 2-3-4 tree). Their interface, however, doesn't
reflect that; they're just containers. Aside from complexity guarantees that the
standard imposes, you could re-implement std::set or std::map using AVL trees,
B-trees, sorted vectors, a file, encrypted and compressed socket connections to
a remote data server... all without changing the interface.

On the other hand, if the relationships between the data items are meaningful in
some way, you may need to resort to a raw data structure like an unbalanced
tree, a heap, a circular buffer, etc..

As a rule, if you can't list your reasons for chosing one approach over the
other without hesitation, stick with containers. The std::set and std::map
interfaces should be more than good enough for your B-tree, assuming that's what
you're actually implementing.

Would GetNodeCount() be useful in a BTree class?

Why? A user of your class will want to know how many values you have stored in
it, not how many gizblitz you're using internally.

How about a copy constructor?

Doh! Seriously. If you can't answer this question, don't even try to write a
container class.

As repetitive as this is, study the standard containers. There are reasons
they're written as they are.

Claudio Puviani

 

[Nobody]

How about a copy constructor?

Doh! Seriously. If you can't answer this question, don't even try to write a
container class.

I didn't mean is a copy constructor useful on a fundamental basis, I meant
is it useful in a real world basis. I may be in the minority here, but I
don't think copy constructors are useful for collection classes. I think it
is poor code to go around copying a 50,000 node AVL tree rather than passing
around a pointer to it.

 

[Claudio Puviani]

I didn't mean is a copy constructor useful on a fundamental basis, I meant
is it useful in a real world basis. I may be in the minority here, but I
don't think copy constructors are useful for collection classes. I think it
is poor code to go around copying a 50,000 node AVL tree rather than passing
around a pointer to it.

Firstly, whether or not someone wants to copy a container isn't for the
container designer to decide. There can be sound, and even necessary, reasons
for copying a containter. The user needs to checkpoint before a modification and
might need to backtrack on error. The user needs to spawn two independent
branches from the same data set. The user needs to modify a temporary copy of
the data.

Secondly, you're stopping the user from copying a 10-element container with your
draconian I-know-better-than-the-user approach. If the user's requirements make
it perfectly acceptable to copy containers of a certain size, why should that
user be constrained by the container designer's myopia?

Thirdly, but most importantly, you cripple your class by not allowing its
instances to be stored in other containers or as part of value-semantic objects.
Combining containers is such a fundamental practice that not being aware of it
disqualifies you from using the term "real world". If you had any real world
experience, you'd have encountered dozens, if not hundreds, of cases of maps of
vectors, maps of maps, vectors of objects containing sets, and far more
convoluted constructs.

Plain and simple, non-value semantic containers are BAD design.

Claudio Puviani