Anderson tree problem

Thought I'd use an Anderson tree for something. So I started porting to C++ the Julienne Walker version found here: http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_andersson.aspx

Now I have insertions working. But the problem is if I compile with optimisations it crashes. Even -O1 crashes it.

template <class Tv>
class AaTree
{
private:

    template <typename Tdata>
    struct AaNode
    {
        AaNode()
        {
            level = 0;
            link[0] = 0L;
            link[1] = 0L;
        }

        ~AaNode()
        {}


        int level;
        Tdata data;
        AaNode<Tdata>* link[2];
    };


    AaNode<Tv>* root;
    AaNode<Tv>* nil;  // sentinel

    inline AaNode<Tv>* make_node(Tv data, int level)
    {
        AaNode<Tv>* rn = new AaNode<Tv>();
        rn->data = data;
        rn->level = level;
        rn->link[0] = rn->link[1] = nil;
    }

    inline AaNode<Tv>* skew(AaNode<Tv>* t)
    {
        if (t->link[0]->level == t->level && t->level != 0)
        {
            AaNode<Tv>* save = t->link[0];
            t->link[0] = save->link[1];
            save->link[1] = t;
            t = save;
        }

        return t;
    }


    inline AaNode<Tv>* split(AaNode<Tv>* t)
    {
        if (t->link[1]->link[1]->level == t->level && t->level != 0)
        {
            AaNode<Tv>*save = t->link[1];
            t->link[1] = save->link[0];
            save->link[0] = t;
            t = save;
            ++t->level;
        }

        return t;
    }


    AaNode<Tv>* _insert(AaNode<Tv>* root, Tv data)
    {
        if (root == nil)
            root = make_node(data, 1);
        else {
            AaNode<Tv>* it = root;
            AaNode<Tv>* path[64];
            int top=0, dir=0;

            for (;;) 
            {
                path[top++] = it;
                dir = it->data < data;

                if (it->link[dir] == nil)
                    break;

                it = it->link[dir];
            }

            it->link[dir] = make_node(data, 1);

            while (--top >= 0) 
            {
                if (top != 0)
                    dir = path[top - 1]->link[1] == path[top];

                path[top] = skew(path[top]);
                path[top] = split(path[top]);

                    if ( top != 0 )
                    path[top - 1]->link[dir] = path[top];
                else
                    root = path[top];
            }
        }

        return root;
    }       

    void _print(AaNode<Tv>* root)
    {
        if (root != nil)
        {
            _print(root->link[0]);
            printf("level(%d): %d\n", root->level, root->data);
            _print(root->link[1]);
        }
    }


public:
    AaTree()
        : root(0L)
    {
        nil = new AaNode<Tv>();
        root = nil;
    }

    ~AaTree()
    {}

    void Insert(Tv data)
    {
        root = _insert(root, data);
    }

    void Delete(Tv data)
    {
        root = _remove(root, data);
    }

    void Print()
    {
        _print(root);
    }   
};


int main(int argc, char* argv[])
{
    AaTree<int> tree;

    for (int i = 0; i < 100; i++)
        tree.Insert(i);

    tree.Prin开发者_如何转开发t();

    return 0;
}

Your make_node function claims to return a value, but contains no return statement.

struct AaNode should not be a template in your case. Try to remove it and see what will happen.

struct AaNode
    {
        AaNode()
        {
            level = 0;
            link[0] = 0L;
            link[1] = 0L;
        }

        ~AaNode()
        {}


        int level;
        Tv  data;
        AaNode* link[2];
    };

But in any case make_node() must return a value. I don't know how you even able to compile this.

1. Use a proper construction initializer list:

   AaNode()
   :
       level(0),
       data(),
       link()
   {
       link[0] = 0L;
       link[1] = 0L;
   }
   

2. Remove the inline keywords from your functions. Inline should be reserved for very small functions (general guideline is one or two lines max), the functions you are attempting to inline are too large and will most likely be more inefficient than calling normally.

3. Your sentinal value nil should probably be const static. Also it wouldn't hurt to initialize it with some easily recognisable value which may aid in debugging.

4. In skew() and split() you are not doing any checking to make sure that t is valid or that t's links are valid before dereferencing the pointer.

5. As others have noted, your make_node does not return the node it creates.

6. In insert your for loop doesnt check to make sure its not accessing out of bounds memory (> 64th entry of path)