comments on this Binary Searh Tree template?

N

Nobody

This is sort of my first attempt at writing a template container class, just
wanted some feedback if everything looks kosher or if there can be any
improvements. This is a template class for a binary search tree. Note there
is a requirement for this to be a Win32/MFC "friendly" class, thus the use
of CObject and POSITION. There is also a requirement for there not to be a
separate iterator class.

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

template <class TYPE, class ARG_TYPE>
class CBinarySearchTree : public CObject
{
// Constructors
public:
CBinarySearchTree();
// Attributes
public:
int GetCount() const;
POSITION GetRoot() const;
POSITION GetLeft(POSITION& pos) const;
POSITION GetRight(POSITION& pos) const;
ARG_TYPE GetElement(POSITION& pos) const;
// Operations
public:
BOOL Insert(ARG_TYPE newElement);
BOOL Remove(ARG_TYPE element);
void RemoveAll();
POSITION Find(ARG_TYPE element);
// Implementation
public:
virtual ~CBinarySearchTree();
protected:
struct _TREENODE
{
TYPE element;
_TREENODE* pLeft;
_TREENODE* pRight;
};
protected:
_TREENODE* m_pRoot;
UINT m_nCount;
protected:
BOOL Insert(ARG_TYPE newElement, _TREENODE*& pNode);
BOOL Remove(ARG_TYPE element, _TREENODE*& pNode);
LPVOID FindMin(_TREENODE* pNode);
};

////////////////////////////////////////////////////////////////////////////
/

template <class TYPE, class ARG_TYPE>
CBinarySearchTree<TYPE, ARG_TYPE>::CBinarySearchTree()
{
m_pRoot = NULL;
m_nCount = 0;
}

template <class TYPE, class ARG_TYPE>
CBinarySearchTree<TYPE, ARG_TYPE>::~CBinarySearchTree()
{
RemoveAll();
}

template <class TYPE, class ARG_TYPE>
int CBinarySearchTree<TYPE, ARG_TYPE>::GetCount() const
{
return m_nCount;
}

template <class TYPE, class ARG_TYPE>
POSITION CBinarySearchTree<TYPE, ARG_TYPE>::GetRoot() const
{
return (POSITION)m_pRoot;
}

template <class TYPE, class ARG_TYPE>
POSITION CBinarySearchTree<TYPE, ARG_TYPE>::GetLeft(POSITION& pos) const
{
return (POSITION)(((_TREENODE*)pos)->pLeft);
}

template <class TYPE, class ARG_TYPE>
POSITION CBinarySearchTree<TYPE, ARG_TYPE>::GetRight(POSITION& pos) const
{
return (POSITION)(((_TREENODE*)pos)->pRight);
}

template <class TYPE, class ARG_TYPE>
ARG_TYPE CBinarySearchTree<TYPE, ARG_TYPE>::GetElement(POSITION& pos) const
{
return ((_TREENODE*)pos)->element;
}

template <class TYPE, class ARG_TYPE>
BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Insert(ARG_TYPE newElement)
{
return Insert(newElement, m_pRoot);
}

template <class TYPE, class ARG_TYPE>
BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Remove(ARG_TYPE element)
{
return Remove(element, m_pRoot);
}

template <class TYPE, class ARG_TYPE>
void CBinarySearchTree<TYPE, ARG_TYPE>::RemoveAll()
{
while (m_pRoot != NULL)
Remove(m_pRoot->element);
}

template <class TYPE, class ARG_TYPE>
POSITION CBinarySearchTree<TYPE, ARG_TYPE>::Find(ARG_TYPE element)
{
return NULL;
}

template <class TYPE, class ARG_TYPE>
BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Insert(ARG_TYPE newElement,
_TREENODE*& pNode)
{
if (pNode != NULL)
{
if (newElement < pNode->element)
return Insert(newElement, pNode->pLeft);

if (newElement > pNode->element)
return Insert(newElement, pNode->pRight);
}
else
{
pNode = new _TREENODE;

if (!pNode)
return FALSE;

m_nCount++;

pNode->element = newElement;
pNode->pLeft = NULL;
pNode->pRight = NULL;

return TRUE;
}

return TRUE;
}

template <class TYPE, class ARG_TYPE>
BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Remove(ARG_TYPE element, _TREENODE*&
pNode)
{
_TREENODE* pTempNode = NULL;

if (!pNode)
return TRUE;

if (element < pNode->element)
{
Remove(element, pNode->pLeft);
}
else if (element > pNode->element)
{
Remove(element, pNode->pRight);
}
else if (pNode->pLeft != NULL && pNode->pRight != NULL)
{
pTempNode = (_TREENODE*)FindMin(pNode->pRight);
pNode->element = pTempNode->element;
Remove(element, pNode->pRight);
}
else
{
pTempNode = pNode;

if (m_nCount > 0)

m_nCount--;

if (!pNode->pLeft)
pNode = pNode->pRight;
else if (!pNode->pRight)
pNode = pNode->pLeft;

delete pTempNode;
}

return TRUE;
}

template <class TYPE, class ARG_TYPE>
LPVOID CBinarySearchTree<TYPE, ARG_TYPE>::FindMin(_TREENODE* pNode)
{
if (!pNode)
return NULL;
else if (!pNode->pLeft)
return (LPVOID)pNode;

return FindMin(pNode->pLeft);
}


Thanks!
 
J

John Harrison

Miscellaneous comments below

Nobody said:
This is sort of my first attempt at writing a template container class, just
wanted some feedback if everything looks kosher or if there can be any
improvements. This is a template class for a binary search tree. Note there
is a requirement for this to be a Win32/MFC "friendly" class, thus the use
of CObject and POSITION. There is also a requirement for there not to be a
separate iterator class.

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

template <class TYPE, class ARG_TYPE>
class CBinarySearchTree : public CObject
{
// Constructors
public:
CBinarySearchTree();
// Attributes
public:
int GetCount() const;
POSITION GetRoot() const;
POSITION GetLeft(POSITION& pos) const;
POSITION GetRight(POSITION& pos) const;
ARG_TYPE GetElement(POSITION& pos) const;
Click to expand...

None of the above three functions modify the pos argument, therefore it
should be

ARG_TYPE GetElement(const POSITION& pos) const;

As you have coded it the following is illegal C++

mytree.GetElement(mytree.GetRoot())

which is a bit of a restriction. As it happens MSVC++ does not enforce this,
but that is MSVC++'s problem, there's still no excuse for using non-const
references where const references are correct.

Also can't you make GetLeft, GetRight and GetElement static? It would make
them very slightly more useable (in the absense of a seperate iterator
class).

// Operations
public:
BOOL Insert(ARG_TYPE newElement);
BOOL Remove(ARG_TYPE element);
Click to expand...

bool not BOOL. bool is standard C++, BOOL is not. Try to avoid non-standard
code when there is no good reason for it. (Being more like MFC is not a good
enough reason).
void RemoveAll();
POSITION Find(ARG_TYPE element);
// Implementation
public:
virtual ~CBinarySearchTree();
protected:
struct _TREENODE
Click to expand...

Names with an underscore followed by a capital letter are reserved for
compiler and standard library uses. So _TREENODE is not legal.
{
TYPE element;
_TREENODE* pLeft;
_TREENODE* pRight;
};
protected:
_TREENODE* m_pRoot;
UINT m_nCount;
Click to expand...

Ditto unsigned not UINT. Actually probably should be size_t (64 bit
computing is round the corner, size_t will be a 64 bit type when it arrives)
protected:
BOOL Insert(ARG_TYPE newElement, _TREENODE*& pNode);
BOOL Remove(ARG_TYPE element, _TREENODE*& pNode);
LPVOID FindMin(_TREENODE* pNode);
Click to expand...

Ditto, void* not LPVOID.
};
Click to expand...

No copy constructor or assignment operator. You can implement these easily
enough using the member functions you have already defined, so why not do
it?
////////////////////////////////////////////////////////////////////////////
/

template <class TYPE, class ARG_TYPE>
CBinarySearchTree<TYPE, ARG_TYPE>::CBinarySearchTree()
{
m_pRoot = NULL;
m_nCount = 0;
}

template <class TYPE, class ARG_TYPE>
CBinarySearchTree<TYPE, ARG_TYPE>::~CBinarySearchTree()
{
RemoveAll();
}

template <class TYPE, class ARG_TYPE>
int CBinarySearchTree<TYPE, ARG_TYPE>::GetCount() const
{
return m_nCount;
}

template <class TYPE, class ARG_TYPE>
POSITION CBinarySearchTree<TYPE, ARG_TYPE>::GetRoot() const
{
return (POSITION)m_pRoot;
}

template <class TYPE, class ARG_TYPE>
POSITION CBinarySearchTree<TYPE, ARG_TYPE>::GetLeft(POSITION& pos) const
{
return (POSITION)(((_TREENODE*)pos)->pLeft);
}

template <class TYPE, class ARG_TYPE>
POSITION CBinarySearchTree<TYPE, ARG_TYPE>::GetRight(POSITION& pos) const
{
return (POSITION)(((_TREENODE*)pos)->pRight);
}

template <class TYPE, class ARG_TYPE>
ARG_TYPE CBinarySearchTree<TYPE, ARG_TYPE>::GetElement(POSITION& pos) const
{
return ((_TREENODE*)pos)->element;
}

template <class TYPE, class ARG_TYPE>
BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Insert(ARG_TYPE newElement)
{
return Insert(newElement, m_pRoot);
}

template <class TYPE, class ARG_TYPE>
BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Remove(ARG_TYPE element)
{
return Remove(element, m_pRoot);
}

template <class TYPE, class ARG_TYPE>
void CBinarySearchTree<TYPE, ARG_TYPE>::RemoveAll()
{
while (m_pRoot != NULL)
Remove(m_pRoot->element);
}

template <class TYPE, class ARG_TYPE>
POSITION CBinarySearchTree<TYPE, ARG_TYPE>::Find(ARG_TYPE element)
{
Huh?

return NULL;
}

template <class TYPE, class ARG_TYPE>
BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Insert(ARG_TYPE newElement,
_TREENODE*& pNode)
Click to expand...

I'd like to see this function return true if an element was inserted and
false if you attempt to insert a duplicate element, and a exception thrown
for the out of memory error.

This code is not exception safe, but I guess you aren't too worried about
that.
{
if (pNode != NULL)
{
if (newElement < pNode->element)
return Insert(newElement, pNode->pLeft);

if (newElement > pNode->element)
return Insert(newElement, pNode->pRight);
}
else
{
pNode = new _TREENODE;

if (!pNode)
return FALSE;
Click to expand...

More MCVC++ specific code. new does return NULL on memory exhaustion in
standard C++, it throws an exception instead.
m_nCount++;

pNode->element = newElement;
pNode->pLeft = NULL;
pNode->pRight = NULL;
Click to expand...

I think the above is better written like this


_TREENODE* tmp;
tmp = new _TREENODE(newElement);
if (tmp == 0) // MSVC++ specific code, new can return NULL in MSVC++
throw std::bad_alloc(); // do the right thing on memory
exhaustion
pNode = tmp;
++m_nCount;

You'll have to add the constructor for _TREENODE.

This code has two points, it does the correct thing on memory exhaustion,
and it is exception safe, i.e. if either you run out of memory, or if
copying the newElement throws an exception then your tree is left unchanged,
that is not the case with your current code.
return TRUE;
}

return TRUE;
}

template <class TYPE, class ARG_TYPE>
BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Remove(ARG_TYPE element, _TREENODE*&
pNode)
{
_TREENODE* pTempNode = NULL;

if (!pNode)
return TRUE;

if (element < pNode->element)
{
Remove(element, pNode->pLeft);
}
else if (element > pNode->element)
{
Remove(element, pNode->pRight);
}
else if (pNode->pLeft != NULL && pNode->pRight != NULL)
{
pTempNode = (_TREENODE*)FindMin(pNode->pRight);
pNode->element = pTempNode->element;
Remove(element, pNode->pRight);
}
else
{
pTempNode = pNode;

if (m_nCount > 0)

m_nCount--;

if (!pNode->pLeft)
pNode = pNode->pRight;
else if (!pNode->pRight)
pNode = pNode->pLeft;

delete pTempNode;
}

return TRUE;
}

template <class TYPE, class ARG_TYPE>
LPVOID CBinarySearchTree<TYPE, ARG_TYPE>::FindMin(_TREENODE* pNode)
{
if (!pNode)
return NULL;
else if (!pNode->pLeft)
return (LPVOID)pNode;

return FindMin(pNode->pLeft);
}


Thanks!
Click to expand...

john
 
J

John Harrison

No copy constructor or assignment operator. You can implement these easily
enough using the member functions you have already defined, so why not do
it?
Click to expand...

Actually scratch that. A copy ctor written that way would not be efficient.
You should use a straightforward recursive tree copy instead.

john
 
N

Nobody

Thanks for the feedback John. Some good technical points here that I will
modify my code for and some style issues that are "to each his own" :).

Ooops, in the code posted, the Find function was not implemented.

Why make the GetElement, GetLeft and GetRight static? I understand they
operate on the node struct and not the tree itself, but does it add anything
to be static?

If those methods were static, wouldn't I have to call them with some ugly
code like:

CBinarySearchTree<int>::GetLeft(pos);

or something of that nature? vs.

tree.GetLeft(pos);

I have always followed the belief of not making class functions or members
static. If a member function is static, it probably shouldn't be a member
function.

Yes, I do need to implement a copy constructor as well.

Again, thanks for the feedback, much appreciated.
 
J

John Harrison

Nobody said:
Thanks for the feedback John. Some good technical points here that I will
modify my code for and some style issues that are "to each his own" :).

Ooops, in the code posted, the Find function was not implemented.

Why make the GetElement, GetLeft and GetRight static? I understand they
operate on the node struct and not the tree itself, but does it add anything
to be static?

If those methods were static, wouldn't I have to call them with some ugly
code like:

CBinarySearchTree<int>::GetLeft(pos);

or something of that nature? vs.

tree.GetLeft(pos);
Click to expand...

No, you can use EITHER syntax if the function is static. The point of making
them static is that you can do node iteration without having the original
tree.
I have always followed the belief of not making class functions or members
static. If a member function is static, it probably shouldn't be a member
function.
Click to expand...

Fair enough, although I wouldn't be as categorical as you are being. But in
this case these three functions should be part of a seperate iterator class,
but you've already ruled that out, so I thought making them static is the
next best thing.

It's going to get very tedious when writing functions that use GetLeft,
GetRight and GetElement to always have to pass the tree itself to that
function as well.
Yes, I do need to implement a copy constructor as well.

Again, thanks for the feedback, much appreciated.
Click to expand...

john
 
J

Jon Willeke

John said:
Miscellaneous comments below



Ditto unsigned not UINT. Actually probably should be size_t (64 bit
computing is round the corner, size_t will be a 64 bit type when it arrives)
Click to expand...

I noticed the following comment in gc.h from Hans Boehm's garbage
collector: "[size_t] and [ptr_diff_t] appear to have incorrect
definitions on many systems. Notably 'typedef int size_t' seems to be
both frequent and WRONG." Comments?
 
J

John Harrison

Jon Willeke said:
John said:
Miscellaneous comments below



Ditto unsigned not UINT. Actually probably should be size_t (64 bit
computing is round the corner, size_t will be a 64 bit type when it
Click to expand...
arrives)

I noticed the following comment in gc.h from Hans Boehm's garbage
collector: "[size_t] and [ptr_diff_t] appear to have incorrect
definitions on many systems. Notably 'typedef int size_t' seems to be
both frequent and WRONG." Comments?
Click to expand...

I believe the standard requires size_t to be an unsigned integral type. Hans
Boehm's garbage collector is very old. I doubt that many compilers get
size_t wrong nowadays.

john
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

BTree implementation - take 2 2
Why is this WordPress comments form not submitting? 1
stl::map iterator 2
What methods are useful in a BTree? 5
Runtime errors with c++ binary search tree 3
Changing references 1
Is there in memory tree structure faster than std::map? 11
Casting template argument 3

Members online

No members online now.
Total: 28 (members: 0, guests: 28)
Robots: 475

Forum statistics

Threads
473,769
Messages
2,569,581
Members
45,056
Latest member
GlycogenSupporthealth

Latest Threads

Top