Help with AA-tree insertion - problems with skew() and split() in loop

Question

Hello all,

I am doing an STL-like AA-tree as a personal project and am running into some trouble. Chopping out the loop containing the skew and split functions gives a working and correct unbalanced binary search tree. However, once the loop is included it goes into an infinite loop. I am trying to insert the numbers 0 to 49 and the skew() and split() loop becomes when 6 is being inserted (The numbers are being inserted in order).

Aside from the infinite loop problem, I have checked the skew() and split() functions repeatedly and, while it looks correct, I suspect there is a problem when the nodes' parents are being set in both functions. I've been pulling my hair out over this. I certainly give my respect to the authors and maintainers of the various STL implementations. Any corrections or help would be much appreciated.

Some notes:

The comparison function being used is essentially the same as std::less. Uses the idiom comp(value1, value2) returning a 0 or 1 to branchlessly calculate the direction that should be taken when traversing the tree, like so: p_node->p_child[comp(value1, value2)];

    //Inserts value into a tree regardless of whether there are duplicates
template <typename Key, typename Value, typename Compare, class Allocator>
typename aa_tree<Key, Value, Compare, Allocator>::iterator 
aa_tree<Key, Value, Compare, Allocator>::insert_duplicate(const value_type &value)
{
    if(anchor.p_parent != &null_node) {
        node_type *p_trv = static_cast<node_type *>(anchor.p_parent);
        node_type *p_parent = static_cast<node_type *>(&null_node);

        while(p_trv != &null_node) {
            p_parent = p_trv;
            p_trv = static_cast<node_type *>(p_trv->p_child[comp(p_trv->value, value)]); //>= move to the right
        }

        node_type *p_node = create_node();
        powerstd_helper::construct(&(p_node->value), value);
        p_node->p_parent = p_parent;
        p_parent->p_child[comp(p_parent->value, value)] = p_node; // >= goes to the right

//The problem is here with the skew and split functions. Chopping this out gives a correct unbalanced BST.

        base_type *p_trv2 = static_cast<base_type *>(p_parent);
        while(p_trv2 != &null_node) {
            skew(p_trv2, &anchor);
            split(p_trv2, &anchor);
            p_trv2 = p_trv2->p_parent;
        }

        return iterator(p_node);
    }

    node_type *p_node = create_node();
    powerstd_helper::construct(&(p_node->value), value);
    p_node->p_parent = &null_node;

    ++tree_size;

    //set root (p_parent), leftmost (p_child[0]), rightmost (p_child[1])
    anchor.p_child[0] = anchor.p_child[1] = anchor.p_parent = static_cast<base_type *>(p_node);

    return iterator(p_node);
}
    #include "aa_tree.hpp"

//maintaining the leftmost and rightmost not done yet
void powerstd_aa_tree::skew(aa_node_base *&p_tree, aa_node_base *p_anchor) //modifies p_root
{
    if(p_tree->p_child[0] != &null_node && p_tree->p_child[0]->level == p_tree->level) {
        aa_node_base *p_left = p_tree->p_child[0];

        //Set the parents of each node
        p_left->p_child[1]->p_parent = p_tree;
        p_left->p_parent = p_tree->p_parent;
        p_tree->p_parent = p_left;

        if(p_tree == p_anchor->p_parent)
            p_anchor->p_parent = p_left;

        //set the nodes
        p_tree->p_child[0] = p_left->p_child[1];
        p_left->p_child[1] = p_tree;
        p_tree = p_left;
    }
}

void powerstd_aa_tree::split(aa_node_base *&p_tree, aa_node_base *p_anchor) //modifies p_root
{
    if(p_tree != &null_node && p_tree->p_child[1]->p_child[1]->level == p_tree->level) {
        aa_node_base *p_right = p_tree->p_child[1];

        //Set the parents of each node
        p_right->p_child[0]->p_parent = p_tree;
        p_right->p_parent = p_tree->p_parent;
        p_tree->p_parent = p_right;

        if(p_tree == p_anchor->p_parent)
            p_anchor->p_parent = p_right;

        //set the nodes
        p_right->p_child[1] = p_right->p_child[0];
        p_right->p_child[0] = p_tree;
        p_tree = p_right;
        ++(p_right->level);
    }
}