How to make a recursive insert for a binary tree more effective (efficient)?

Question

This code is modified from a Stanford resource located here.

I started with this after some modifying to C++ conventions:

#include <iostream>
#include <string>

using namespace std;

template < typename A, typename B > class binary_tree
{
    public:

    class node 
    {
            public:
            A key;
        B value;
            node* left;
            node* right;
    };

    typedef node* nodePointer;

    nodePointer HP;

    nodePointer newNode( A key, B value ) 
    {
            nodePointer NP = new( node );
            NP->key = key;
                NP->value = value;
            NP->left = NULL;
            NP->right = NULL;
                return NP;
    }

    void insert( A key, B value )
    {
        insertI( this->HP, key, value );
    }

    nodePointer insertI( nodePointer NP, A key, B value ) 
    {
        if ( NP == NULL ) 
        {
            return newNode( key, value );
        }
        else 
        {
            if (key < NP->key) 
            {
                NP->left = insertI( NP->left, key, value );
            }
            else 
            {      
                NP->right = insertI( NP->right, key, value );
            }
            return NP;
        }
    }

    binary_tree(A key, B value)
    { 
        this->HP = insertI(NULL, key, value );
    }
};

To eliminate passing by value the key/value pair for each activation frame I updated the insertI() parameters to pass by const reference like this:

nodePointer insertI( nodePointer NP, const A& key, const B& value ) 
{
    if ( NP == NULL ) 
    {
        return newNode( key, value );
    }
    else 
    {
        if (key < NP->key) 
        {
            NP->left = insert( NP->left, key, value );
        }
        else 
        {      
            NP->right = insert( NP->right, key, value );
        }
        return NP;
    }
}

Right now I can only define the function inline b.c. I'm using an online compiler. But what is faster - inline, or defined outside of the class?

Also, this is just a stub, obviously the class over all needs more work. This question just regards the insertI() function.

Is there anything else I can do to make the insert more efficient?

Links

(http://en.wikipedia.org/wiki/Binary_search_tree#Searching)

(http://en.wikipedia.org/wiki/Binary_search_algorithm)

Another Approach

Tail Recursion

Notes

This operation requires O(log n) time in the average case, but needs O(n) time in the worst case, when the unbalanced tree resembles a linked list (degenerate tree).

Related

Answer 1

Does it really make sense to improve the efficiency of the insert method if you do not implement the tree-balancing part? If you insert items such as 1>2>3>4>... you will always end-up in O(n) operation to insert the next item.

I'd suggest to first auto-balance your tree and then there will be matter to improvement. And if recursion is an issue you can easily remove it with something such as:

nodePointer newOne = newNode(...);

if(NP== NULL)
    return newOne;

while(NP != NULL) {
    if(key < NP->key) {
        if(NP->left == NULL) {NP->left = newOne; return;} // finally inserted
        else                 NP = NP->left;

    } else {
        if(NP->right== NULL) {NP->right= newOne; return;} // finally inserted
        else                 NP = NP->right;
    }
}

// Should never reach this line

Answer 2

But what is faster - inline, or defined outside of the class?

Defining methods in the class declaration can be worth it for small methods. For larger functions the jump is negligible.

Is there anything else I can do to make the insert more efficient?

I wouldn't use recursion in places where a simple loop would suffice. Compilers are pretty good at optimizing recursion, but the same is true for loop optimization.

You can balance the tree to improve runtime. For example:
http://en.wikipedia.org/wiki/Red–black_tree

Also, this occurs to me:

void insert(const A& key, const B& value) {
  node** cur = &HP;
  while (*cur != NULL) {
    cur = &(key < (*cur)->key ? (*cur)->left : (*cur)->right);
  }
  *cur = new node(key, value);
}

Traversing the pointers themselves rather than the nodes that contain them.