473,219 Members | 1,453 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,219 software developers and data experts.

What methods are useful in a BTree?

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.


Jul 22 '05 #1
5 2028
Nobody wrote:
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.

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?

Jul 22 '05 #2

"Nobody" <no****@cox.net> wrote in message
news:K4GVb.28004$1O.944@fed1read05...
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
Jul 22 '05 #3
"Nobody" <no****@cox.net> wrote
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
Jul 22 '05 #4
> >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.
Jul 22 '05 #5
"Nobody" <no****@cox.net> wrote
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.


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
Jul 22 '05 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

0
by: Jane Austine | last post by:
Hello. How do I change the BTree sorting order with bsddb, instead of the default lexicographical order? After studying sleepycat's document, I found there is a function call for setting the...
92
by: Reed L. O'Brien | last post by:
I see rotor was removed for 2.4 and the docs say use an AES module provided separately... Is there a standard module that works alike or an AES module that works alike but with better encryption?...
2
by: Mike C. Fletcher | last post by:
I'm looking at rewriting parts of Twisted and TwistedSNMP to eliminate __del__ methods (and the memory leaks they create). Looking at the docs for 2.3's weakref.ref, there's no mention of whether...
4
by: Spam Me Please | last post by:
I have a tree like this struct BTree{ int left; char c; int right; }; #define END -1 int main(int argc, char *argv)
7
by: Trvl Orm | last post by:
I am working with 2 frames, Left and Right and the main code is in the left frame, which has been attached. Can someone please help me with this code. I am new to JavaScript and can't figure it...
7
by: Simon Peng | last post by:
-- ---------------- Simon Peng xqpeng@tsinghua.org.cn
5
by: Franco, Gustavo | last post by:
Hi, I have a question, and please I need a answer. How can I finalize a thread running with Application.Run (I need the message loop!!!) without call Thread.Abort?. I want to call...
1
by: Brian Maguire | last post by:
Can too many btree indexes cause page level locking? I read this... http://www.postgresql.org/docs/7.4/static/locking-indexes.html
4
by: Amar | last post by:
Hi All, I need to select data from a database table containing huge amount of data. Now I am storing data using one primary key and I am just using simple select statement, and this process...
0
by: VivesProcSPL | last post by:
Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for...
3
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 3 Jan 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). For other local times, please check World Time Buddy In...
0
by: jianzs | last post by:
Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
2
by: jimatqsi | last post by:
The boss wants the word "CONFIDENTIAL" overlaying certain reports. He wants it large, slanted across the page, on every page, very light gray, outlined letters, not block letters. I thought Word Art...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.