Re: comments on this Binary Searh Tree template?

From: Nobody (nobody_at_cox.net)
Date: 02/14/04 

Date: Sat, 14 Feb 2004 00:47:50 -0800

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.

"John Harrison" <john_andronicus@hotmail.com> wrote in message
news:c0kkar$165v2l$1@ID-196037.news.uni-berlin.de...
> Miscellaneous comments below
>
> "Nobody" <nobody@cox.net> wrote in message
> news:%ZjXb.33476$1O.26297@fed1read05...
> > 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;
>
> 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);
>
> 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
>
> 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;
>
> 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);
>
> Ditto, void* not LPVOID.
>
> > };
>
> 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)
>
> 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;
>
> 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;
>
> 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!
> >
>
> john
>
>

Relevant Pages

  • Re: Ebay Paypal?
    ... Okay, I don't understand several things here. ... someone with over 100 feedback wouldn't know how to modify an auction. ...
    (alt.guitar.bass)
  • Re: Jazzica mods and effects
    ... looking for a cheap tele to modify into something I could modify and ... will it fit into the existing mount that comes with the JCustom? ... This is almost an acoustic guitar with a pickup in the neck, ... feedback, the guitar comes with plugs for the f-holes. ...
    (rec.music.makers.guitar.jazz)
  • Re: Jazzica mods and effects
    ... looking for a cheap tele to modify into something I could modify and ... will it fit into the existing mount that comes with the JCustom? ... feedback, the guitar comes with plugs for the f-holes. ... Change the tone Cap for other value ...
    (rec.music.makers.guitar.jazz)
  • RE: Microsoft.ApplicationBlocks.Data
    ... Thank you very much for your feedback. ... you can just modify it an rebuild the assembly to make it work. ... Prev by Date: ...
    (microsoft.public.dotnet.framework.adonet)