Проблема дерева Андерсона

Question

Думаю, я бы использовал дерево Андерсона для чего-то.Поэтому я начал портировать на C ++ версию Julienne Walker, найденную здесь: http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_andersson.aspx

Теперь у меня работают вставки.Но проблема в том, что если я скомпилирую с оптимизацией, это вылетает.Даже -O1 вылетает.

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.Print();

    return 0;
}

Answer 1

Ваша функция make_node утверждает, что возвращает значение, но не содержит оператора возврата.

Answer 2

1. Используйте правильный список инициализатора конструкции:

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

2. Удалите встроенные ключевые слова из ваших функций.Inline должен быть зарезервирован для очень маленьких функций (общее правило - одна или две строки максимум), функции, которые вы пытаетесь встроить, слишком велики и, скорее всего, будут более неэффективными, чем обычные вызовы.

3. Ваше значение nil должно быть const static.Также не мешало бы инициализировать его некоторым легко узнаваемым значением, которое может помочь при отладке.

4. В skew () и split () вы не выполняете никаких проверок, чтобы убедиться, чтоt допустим или ссылки t действительны до разыменования указателя.

5. Как уже отмечали другие, ваш make_node не возвращает созданный им узел.

6. В insert ваш цикл for не проверяет, чтобы убедиться, что он не обращается за пределы памяти (> 64-я запись пути)

Answer 3

struct AaNode не должно быть шаблоном в вашем случае.Попробуйте удалить его и посмотрите, что произойдет.

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

        ~AaNode()
        {}


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

Но в любом случае make_node () должна вернуть значение.Я не знаю, как ты вообще смог это скомпилировать.