Request for comment on BST class

[rpdm]

How can this BST class be better?

#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <conio.h>

using namespace std;

template <class KeyType, class ValueType>
class BST 
{
public:
    BST(): mroot(0), mcount(0) {}
    BST(BST const& tree) { *this = clone(tree.mroot); }
    BST& operator=(BST const& tree)
    {
        if (this != &tree)
        {
            mroot = clone(tree.mroot);
            mcount = tree.mcount;
        }
        return *this;
    }
    ~BST() { remove_all(mroot); }
    void add(KeyType key, ValueType value, bool at_root=false) 
    { 
        add(mroot, key, value, at_root);
        ++mcount; 
    }
    void remove(KeyType key) { if (remove(mroot, key)) --mcount; }
    bool exists(KeyType key) const { return find(mroot, key) != 0; }
    ValueType value(KeyType key) const
    {
        node* found = find(mroot, key);
        return found ? found->value : ValueType();
    }
    int count() const { return mcount; }
    void print() const { print(mroot); }
private:
    class node 
    {
    public:
        node(KeyType key, ValueType value, node* left, node* right)
            : key(key), value(value), left(left), right(right) {}
    public:
        KeyType key;
        ValueType value;
        node* left;
        node* right;
    };
    void rotate(node*& oldroot, node*& newroot, node*& swapsibling)
    {
        node* tmp = newroot;
        newroot = swapsibling;
        swapsibling = oldroot;
        oldroot = tmp;
    }
    void add(node*& root, KeyType key, ValueType value, bool at_root=false)
    {
        if (!root)
            root = new node(key, value, 0, 0);
        else if (key < root->key) 
        {
            add(root->left, key, value, at_root);
            if (at_root) 
                rotate(root, root->left, root->left->right);
        }
        else 
        {
            add(root->right, key, value, at_root);
            if (at_root) 
                rotate(root, root->right, root->right->left);
        }
    }
    bool remove(node*& root, KeyType key)
    {
        if (!root)
            return false;
        if (key == root->key)
        {
            if (!root->left && !root->right)
            {
                delete root;
                root = 0;
                return true;
            }
            else if (root->left)
                rotate(root, root->left, root->left->right);
            else
                rotate(root, root->right, root->right->left);
        }
        if (key < root->key)
            return remove(root->left, key);
        else
            return remove(root->right, key);
    }
    node *clone(node* root) const
    {
        if (!root)
            return root;
        node *curr = new node(root->key, root->value, 0, 0);
        curr->left = clone(root->left);
        curr->right = clone(root->right);
        return curr;
    }
    node* find(node* root, KeyType key) const
    {
        if (!root || key == root->key)
            return root;
        else if (key < root->key)
            return find(root->left, key);
        else
            return find(root->right, key);
    }
    void remove_all(node*& root)
    {
        if (!root)
            return;
        remove_all(root->right);
        remove_all(root->left);
        delete root;
    }
    void print(node* root, int depth=0) const
    {
        if (root) 
        {
            print(root->right, depth + 1);
            cout << setw(depth * 4) << "(" << root->key <<","<< root->value <<")" << endl;
            print(root->left, depth + 1);
        }
    }
private:
    node* mroot;
    int mcount;
};

int main()
{
    srand(unsigned(time(0)));
    while (true)
    {
        system("CLS");
        BST<int, int> tree;
        for (int x = 0; x < 10; ++x) 
            tree.add(x, x, rand() % 2 != 0);
        tree.print();
        cout << "Hit ENTER to repeat..." << flush;
        if (getch() != '\r')
        {
            cout << endl;
            break;
        }
    }
}

[Intrade]

It looks good.

Nobody else responded. I didn't want you to feel ignored ;p

[mrnutty]

I don't like your consistency with your naming conventions. Don't abbreviate it. Just name your variable something that we all can understand. For example, instead of BST(bull shit tree?) call it BinarySearchTree.

So as to your program, in no particular oder:

1) You need to abstract your program more. Define a *interface called Tree. Then
have BinarySearchTree inherit from Tree. This lets user do things like so :

Tree tree = FastInsertRemoveTree();
//code here

Tree anotherTree = BinarySearchTree();

Or if the user wants to change from using BinarySearchTree() to say, GeneralSearchTree() then all he simply has to do is change the rvalue constructor.

2) You need to do error checking.
3) The print function really doesn't make sense to be a member function. Make it a regular function.
4) Follow C++ convention of naming. Usually, in tree data structure, we call the function "insert" instead of "add", and "erase" instead of "remove" and "find" instead of "exists". Its not a big deal, but its better to follow conventions.
5) If you can, implement an iterator, so that will make some of your functions work well with stl.

6) For this function :

ValueType value(KeyType key) const{
   node* found = find(mroot, key);
   return found ? found->value : ValueType();
}

the problem with this is that, found->value can essentially be the same as ValueType(). That makes it a problem because when it can confuse the user whether
the function is returning badValue or good value. Thats why iterator is a good solution to this problem. Or just return NULL.

7) Instead of KeyType and ValueType, you can concise it more by using something like std::pair to make your code easier to read/write/maintain.
8) For this code :

node(KeyType key, ValueType value, node* left, node* right)
            : key(key), value(value), left(left), right(right) {}

I'd rather have this

explicit node(KeyType key = KeyType(), ValueType value = ValueType(), node* left = NULL, node* right = NULL)
            : key(key), value(value), left(left), right(right) {}

Just to remove some repetitive typing, not a big deal. Other than that, its seems fine. So far.

[rpdm]

Thanks for the good suggestions. I'll try to add some of them, but I have a few questions.

Don't abbreviate it. Just name your variable something that we all can understand. For example, instead of BST(bull shit tree?) call it BinarySearchTree.

I get your point, but how many coders won't know what BST means? ;)

1) You need to abstract your program more.

Why? I see the benefit if I wanted a general tree, but a BST is the most abstract class I need. Isn't it bad to over abstract?

2) You need to do error checking.

I can't find any places that can fail and aren't checked somehow. Where do I need to add error checking?

3) The print function really doesn't make sense to be a member function. Make it a regular function.

It has to be at least a friend though, right? Can you explain the difference between a member function and a friend function that makes a friend function better here?

[mrnutty]

>>I get your point, but how many coders won't know what BST means?
A lot! Make a poll. Follow good conventions. There is no need to abbreviate the name. Its not as clear as writing it out fully.

>>Why? I see the benefit if I wanted a general tree, but a BST is the most abstract class I need. Isn't it bad to over abstract?
No, the more abstract you get, the better your code will be in terms of reusability and maintainance. You need to start thinking about these things early so when you are on a job, you can produce the best possible code.

>> can't find any places that can fail and aren't checked somehow. Where do I need to add error checking? By error checking, I meant proper error checking. If something fails, then the user should know about it.

>>It has to be at least a friend though, right? Can you explain the difference between a member function and a friend function that makes a friend function better here?
Not if you have proper implementation. If you provide access to each element in the tree, then one can print his own data. I am not saying give the user access to the nodes, but rather have have some type of traversal.

[alwaysLearning0]

OK, So far looks good, but do you want more generic?

IF NO, then dont have to read any more.
But YES ? Then you can add policy design pattern with it using template.

there are several kind of BST (RED-BLACK, AA, AVL, SPLAY.. it goes on and on)
All are self balancing binary search tree, travesing is same, but adding/deleting is different.

So you can add policy in this class now for adding/deleting policy.

example:

template <
  class KeyType, 
  class ValueType,
  template <class> class BSTPolicy=RedBlackTree
 >
class BST : public BSTPolicy <KeyType,ValueType> 
{
 ----- Here Goes BST CODE --
}

BSTPolicy is defiened as, BSTPolicy will implement two method, one is add, another is remove.

This is one of the most powerfull feature of templalte..

ENJOY!!

Happy coding.