Programming Forums > Application Development > C++

Vylrath · Nov 15th, 2005, 9:46 PM

Hi ... I'm having trouble implementing a binary search tree.

I've decided to use classes instead of structures, so my basic structure has a node class that a tree class #includes. Since I am trying to use information hiding, I have made the left and right pointers private, and created functions to access the nodes (setLeft, setRight).

My problem comes up when I need to insert a new element: in one particular case I need to set the left node of the left node to NULL. Since the helper functions can't be stacked, like setLeft(setLeft(NULL)), I have had to create crazy functions called setLeftLeft(NULL).

I know if I made these data pointers public I could just use the -> function such as left->left->data = NULL, but would that be considered bad practice to make all of my variables public?

Thanks for the help! Hope I was clear in discussing my problem!

stevengs · Nov 15th, 2005, 11:52 PM

Usually recursion is used for this type of work. You dont want to change the left node of the left node of the left node... you want to call the method that changes the left node, and have this method decide whether it will change the current node or descend. I may, however, have misunderstood you or the problem, can you show us your code?

Narue · Nov 16th, 2005, 8:53 AM

>so my basic structure has a node class that a tree class #includes
It's more or less customary to have either a nested node class in the tree class or make the tree class a friend of the node class so that you can access the private data. But since a node is often strictly data and should only be accessible by the tree and anything that can be considered private to the tree, it makes more sense to make it a structure that's private to the file where you define the tree:

(Toggle Plain Text)

#include <ostream>

namespace {
  template <typename T>
  struct node {
    T data;
    node *left, *right;

    node ( const T& init )
      : data ( init ), left ( 0 ), right ( 0 )
    {}
  };
}

namespace jsw {
  template <typename T>
  class tree {
    node<T> *root;
  public:
    // Public interface
    tree(): root ( 0 ) {}
    void insert ( const T& data ) { root = insert_r ( root, data ); }
    friend std::ostream& operator<< ( std::ostream& out, const tree<T>& t )
    {
      t.inorder_r ( out, t.root );
      return out;
    }
  private:
    // Private interface
    node<T> *insert_r ( node<T> *root, const T& data )
    {
      if ( root == 0 )
        root = new node<T> ( data );
      else if ( data < root->data )
        root->left = insert_r ( root->left, data );
      else
        root->right = insert_r ( root->right, data );

      return root;
    }

    void inorder_r ( std::ostream& out, const node<T> *root ) const
    {
      if ( root != 0 ) {
        inorder_r ( out, root->left );
        out<< root->data <<' ';
        inorder_r ( out, root->right );
      }
    }
  };
}

>but would that be considered bad practice to make all of my variables public?
You're taking the "public data is evil" mindset to its illogical conclusion. Overuse of anything is a bad practice, even when you're overusing something that's normally a good practice.

Since you're probably not going to ever let the end-users have access to a node (they'll use iterators and the tree public interface exclusively, which is good practice), the access restrictions on your node structure are largely irrelevant.

Vylrath · Nov 16th, 2005, 8:17 PM

Thanks for the replies.

This is the first time I'm creating a BST from scratch, so I didn't even think about friends, nested classes, or even just structures.

Yes, I do use recursion in my algorithms, but when inserting, say to the left child of the root, I would initialize the left and right child of the root's left child to NULL. Heh, sounds very wordy and hard to explain. But anyway it works now, thanks! I appreciate it!

Narue · Nov 17th, 2005, 7:40 AM

>so I didn't even think about friends, nested classes, or even just structures.
And you shouldn't! When implementing a data structure for the first time, it's better IMO to eschew fluffy OOP stuff in favor of a simpler approach. For example, have a basic structure and write a few functions to work on trees using that structure. Here's the same program without using a class or any kind of helpers for convenience:

(Toggle Plain Text)

#include <ostream>

namespace jsw {
  template <typename T>
  struct node {
    T data;
    node *left, *right;

    node ( const T& init )
      : data ( init ), left ( 0 ), right ( 0 )
    {}
  };

  template <typename T>
  typename node<T> *insert_r ( node<T> *root, const T& data )
  {
    if ( root == 0 )
      root = new node<T> ( data );
    else if ( data < root->data )
      root->left = insert_r ( root->left, data );
    else
      root->right = insert_r ( root->right, data );

    return root;
  }

  template <typename T>
  void inorder_r ( std::ostream& out, const node<T> *root )
  {
    if ( root != 0 ) {
      inorder_r ( out, root->left );
      out<< root->data <<' ';
      inorder_r ( out, root->right );
    }
  }
}

template <typename T>
std::ostream& operator<< ( std::ostream& out, const jsw::node<T> *t )
{
  jsw::inorder_r ( out, t );
  return out;
}

It's slightly harder to use, but much easier to implement correctly. You can focus on the important parts (the algorithms) and add wrappers for end-user convenience after you're confident in the underlying operations.

Nov 15th, 2005, 9:46 PM	#1
Vylrath Newbie Join Date: Nov 2005 Posts: 2 Rep Power: 0	Binary Search Tree Question Hi ... I'm having trouble implementing a binary search tree. I've decided to use classes instead of structures, so my basic structure has a node class that a tree class #includes. Since I am trying to use information hiding, I have made the left and right pointers private, and created functions to access the nodes (setLeft, setRight). My problem comes up when I need to insert a new element: in one particular case I need to set the left node of the left node to NULL. Since the helper functions can't be stacked, like setLeft(setLeft(NULL)), I have had to create crazy functions called setLeftLeft(NULL). I know if I made these data pointers public I could just use the -> function such as left->left->data = NULL, but would that be considered bad practice to make all of my variables public? Thanks for the help! Hope I was clear in discussing my problem!

Nov 15th, 2005, 11:52 PM	#2
stevengs Professional Programmer Join Date: May 2005 Location: Bad Nauheim, Germany Posts: 436 Rep Power: 4	Usually recursion is used for this type of work. You dont want to change the left node of the left node of the left node... you want to call the method that changes the left node, and have this method decide whether it will change the current node or descend. I may, however, have misunderstood you or the problem, can you show us your code? __________________ -Steven "Is this a piece of your brain?" - Basil Fawlty

Nov 16th, 2005, 8:53 AM	#3
Narue Professional Programmer Join Date: Sep 2005 Posts: 419 Rep Power: 4	>so my basic structure has a node class that a tree class #includes It's more or less customary to have either a nested node class in the tree class or make the tree class a friend of the node class so that you can access the private data. But since a node is often strictly data and should only be accessible by the tree and anything that can be considered private to the tree, it makes more sense to make it a structure that's private to the file where you define the tree: (Toggle Plain Text) #include <ostream> namespace { template <typename T> struct node { T data; node left, right; node ( const T& init ) : data ( init ), left ( 0 ), right ( 0 ) {} }; } namespace jsw { template <typename T> class tree { node<T> root; public: // Public interface tree(): root ( 0 ) {} void insert ( const T& data ) { root = insert_r ( root, data ); } friend std::ostream& operator<< ( std::ostream& out, const tree<T>& t ) { t.inorder_r ( out, t.root ); return out; } private: // Private interface node<T> insert_r ( node<T> root, const T& data ) { if ( root == 0 ) root = new node<T> ( data ); else if ( data < root->data ) root->left = insert_r ( root->left, data ); else root->right = insert_r ( root->right, data ); return root; } void inorder_r ( std::ostream& out, const node<T> root ) const { if ( root != 0 ) { inorder_r ( out, root->left ); out<< root->data <<' '; inorder_r ( out, root->right ); } } }; } #include <ostream> namespace { template <typename T> struct node { T data; node left, right; node ( const T& init ) : data ( init ), left ( 0 ), right ( 0 ) {} }; } namespace jsw { template <typename T> class tree { node<T> root; public: // Public interface tree(): root ( 0 ) {} void insert ( const T& data ) { root = insert_r ( root, data ); } friend std::ostream& operator<< ( std::ostream& out, const tree<T>& t ) { t.inorder_r ( out, t.root ); return out; } private: // Private interface node<T> insert_r ( node<T> root, const T& data ) { if ( root == 0 ) root = new node<T> ( data ); else if ( data < root->data ) root->left = insert_r ( root->left, data ); else root->right = insert_r ( root->right, data ); return root; } void inorder_r ( std::ostream& out, const node<T> root ) const { if ( root != 0 ) { inorder_r ( out, root->left ); out<< root->data <<' '; inorder_r ( out, root->right ); } } }; } >but would that be considered bad practice to make all of my variables public? You're taking the "public data is evil" mindset to its illogical conclusion. Overuse of anything is a bad practice, even when you're overusing something that's normally a good practice. Since you're probably not going to ever let the end-users have access to a node (they'll use iterators and the tree public interface exclusively, which is good practice), the access restrictions on your node structure are largely irrelevant. __________________ Even if the voices aren't real, they have some pretty good ideas.

Nov 16th, 2005, 8:17 PM	#4
Vylrath Newbie Join Date: Nov 2005 Posts: 2 Rep Power: 0	Thanks Thanks for the replies. This is the first time I'm creating a BST from scratch, so I didn't even think about friends, nested classes, or even just structures. Yes, I do use recursion in my algorithms, but when inserting, say to the left child of the root, I would initialize the left and right child of the root's left child to NULL. Heh, sounds very wordy and hard to explain. But anyway it works now, thanks! I appreciate it! __________________ Brian Chambers brian.chambers@charter.net

Nov 17th, 2005, 7:40 AM	#5
Narue Professional Programmer Join Date: Sep 2005 Posts: 419 Rep Power: 4	>so I didn't even think about friends, nested classes, or even just structures. And you shouldn't! When implementing a data structure for the first time, it's better IMO to eschew fluffy OOP stuff in favor of a simpler approach. For example, have a basic structure and write a few functions to work on trees using that structure. Here's the same program without using a class or any kind of helpers for convenience: (Toggle Plain Text) #include <ostream> namespace jsw { template <typename T> struct node { T data; node left, right; node ( const T& init ) : data ( init ), left ( 0 ), right ( 0 ) {} }; template <typename T> typename node<T> insert_r ( node<T> root, const T& data ) { if ( root == 0 ) root = new node<T> ( data ); else if ( data < root->data ) root->left = insert_r ( root->left, data ); else root->right = insert_r ( root->right, data ); return root; } template <typename T> void inorder_r ( std::ostream& out, const node<T> root ) { if ( root != 0 ) { inorder_r ( out, root->left ); out<< root->data <<' '; inorder_r ( out, root->right ); } } } template <typename T> std::ostream& operator<< ( std::ostream& out, const jsw::node<T> t ) { jsw::inorder_r ( out, t ); return out; } #include <ostream> namespace jsw { template <typename T> struct node { T data; node left, right; node ( const T& init ) : data ( init ), left ( 0 ), right ( 0 ) {} }; template <typename T> typename node<T> insert_r ( node<T> root, const T& data ) { if ( root == 0 ) root = new node<T> ( data ); else if ( data < root->data ) root->left = insert_r ( root->left, data ); else root->right = insert_r ( root->right, data ); return root; } template <typename T> void inorder_r ( std::ostream& out, const node<T> root ) { if ( root != 0 ) { inorder_r ( out, root->left ); out<< root->data <<' '; inorder_r ( out, root->right ); } } } template <typename T> std::ostream& operator<< ( std::ostream& out, const jsw::node<T> t ) { jsw::inorder_r ( out, t ); return out; } It's slightly harder to use, but much easier to implement correctly. You can focus on the important parts (the algorithms) and add wrappers for end-user convenience after you're confident in the underlying operations. __________________ Even if the voices aren't real, they have some pretty good ideas.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Programming Forums > Application Development > C++

Binary Search Tree Question