I am writing a non-recursive AA-Tree that is similar to std::multiset. I was wondering if anybody could notice any problems in my code to rebalance the tree for a deletion. The while loop in erase_rebalance() is going into an infinite loop when erase(iterator first, iterator last) is called. This is leading me to believe that the code to disconnect the node to be deleted from the tree has a problem somewhere and the rebalancing code itself is not at fault.
It is also only happening on about the 16th node to be deleted.
The whole implementation is here:
#ifndef POWERSTL_AA_TREE__
#define POWERSTL_AA_TREE__
/*
anchor holds 3 values:
anchor.p_parent points to the parent node
anchor.p_child[1] holds the rightmost node - (end() - 1)
anchor.p_child[0] holds the leftmost node - begin()
&anchor == end() of the tree
*/
namespace powerstd_aa_tree //hide implementation details
{
class aa_node_base
{
public:
aa_node_base *p_parent;
aa_node_base *p_child[2];
int32_t level;
};
template <typename T>
class aa_node : public aa_node_base
{
public:
T value;
};
static aa_node_base null_node = { &null_node, &null_node, &null_node, 0 }; //Is there a way to make this local to each object instance?
inline
aa_node_base* tree_min_child(aa_node_base *p_node)
{
while(p_node->p_child[0] != &null_node)
p_node = p_node->p_child[0];
return p_node;
}
inline
aa_node_base* tree_max_child(aa_node_base *p_node)
{
while(p_node->p_child[1] != &null_node)
p_node = p_node->p_child[1];
return p_node;
}
void skew(aa_node_base *&p_tree, aa_node_base *&p_root, aa_node_base *p_null_node);
void split(aa_node_base *&p_tree, aa_node_base *&p_root, aa_node_base *p_null_node);
void erase_rebalance(aa_node_base *p_node, aa_node_base *p_anchor, aa_node_base *p_null_node);
iterator erase(iterator pos); //returns position after pos
void erase(iterator first, iterator last)
{
if(first.p_node != static_cast<node_type *>(anchor.p_child[0]) && last.p_node != static_cast<node_type *>(&anchor)) {
while(first != last)
first = erase(first);
} else {
clear();
}
}
};
template <typename Key, typename Value, typename Compare, class Allocator>
typename aa_tree_set<Key, Value, Compare, Allocator>::iterator
aa_tree_set<Key, Value, Compare, Allocator>::erase(iterator pos)
{
iterator itr(pos);
++itr;
erase_rebalance(static_cast<base_type *>(pos.p_node), &anchor, &null_node);
--tree_size;
destroy_node(pos.p_node);
return itr;
}
#endif
#include "aa_tree.hpp"
//right rotation
void powerstd_aa_tree::skew(aa_node_base *&p_tree, aa_node_base *&p_root, aa_node_base *p_null_node) //modifies p_root
{
if(p_tree->p_child[0]->level != 0 && p_tree->p_child[0]->level == p_tree->level) {
aa_node_base *p_left = p_tree->p_child[0];
p_tree->p_child[0] = p_left->p_child[1];
if(p_left->p_child[1] != p_null_node)
p_left->p_child[1]->p_parent = p_tree;
p_left->p_parent = p_tree->p_parent;
if(p_root != p_tree) {
p_tree->p_parent->p_child[p_tree->p_parent->p_child[1] == p_tree] = p_left;
} else { //root == p_tree
p_root = p_left;
}
p_left->p_child[1] = p_tree;
p_tree->p_parent = p_left;
}
}
//left rotation
void powerstd_aa_tree::split(aa_node_base *&p_tree, aa_node_base *&p_root, aa_node_base *p_null_node) //modifies p_root
{
if(p_tree->level != 0 && p_tree->level == p_tree->p_child[1]->p_child[1]->level) {
aa_node_base *p_right = p_tree->p_child[1];
p_tree->p_child[1] = p_right->p_child[0];
if(p_right->p_child[0] != p_null_node)
p_right->p_child[0]->p_parent = p_tree;
p_right->p_parent = p_tree->p_parent;
if(p_root != p_tree) {
p_tree->p_parent->p_child[p_tree->p_parent->p_child[0] != p_tree] = p_right;
} else { //root == p_tree
p_root = p_right;
}
p_right->p_child[0] = p_tree;
p_tree->p_parent = p_right;
++(p_right->level);
}
}
void powerstd_aa_tree::erase_rebalance(aa_node_base *p_node, aa_node_base *p_anchor, aa_node_base *p_null_node)
{
aa_node_base *&p_root_ref = p_anchor->p_parent;
aa_node_base *&p_leftmost_ref = p_anchor->p_child[0];
aa_node_base *&p_rightmost_ref = p_anchor->p_child[1];
aa_node_base *p_successor = p_node;
aa_node_base *p_node_child = p_null_node;
aa_node_base *p_node_child_parent = p_null_node;
if(p_successor->p_child[0] == p_null_node) {
p_node_child = p_successor->p_child[1];
} else if(p_successor->p_child[1] == p_null_node) {
p_node_child = p_successor->p_child[0];
} else {
p_successor = p_successor->p_child[1];
while(p_successor->p_child[0] != p_null_node)
p_successor = p_successor->p_child[0];
p_node_child = p_successor->p_child[1];
}
if(p_successor != p_node) {
p_node->p_child[0]->p_parent = p_successor;
p_successor->p_child[0] = p_node->p_child[0];
if(p_successor == p_node->p_child[1]) {
p_node_child_parent = p_successor;
} else {
p_node_child_parent = p_successor->p_parent;
if(p_node_child != p_null_node)
p_node_child->p_parent = p_node_child_parent;
p_node_child_parent->p_child[0] = p_node_child;
p_successor->p_child[1] = p_node->p_child[1];
p_node->p_child[1]->p_parent = p_successor;
}
if(p_node == p_root_ref) {
p_root_ref = p_successor;
} else if(p_node == p_node->p_parent->p_child[0]) {
p_node->p_parent->p_child[0] = p_successor;
} else {
p_node->p_parent->p_child[1] = p_successor;
}
p_successor->p_parent = p_node->p_parent;
p_successor->level = p_node->level;
} else {
p_node_child_parent = p_successor->p_parent;
if(p_node_child != p_null_node)
p_node_child->p_parent = p_successor->p_parent;
if(p_node == p_root_ref) {
p_root_ref = p_node;
} else {
if(p_node == p_node->p_parent->p_child[0]) {
p_node->p_parent->p_child[0] = p_node_child;
} else {
p_node->p_parent->p_child[1] = p_node_child;
}
}
if(p_node == p_leftmost_ref) {
if(p_node->p_child[1] != p_null_node) {
p_leftmost_ref = tree_min_child(p_node_child);
} else {
p_leftmost_ref = p_node->p_parent;
}
}
if(p_node == p_rightmost_ref) {
if(p_node->p_child[0] != p_null_node) {
p_rightmost_ref = tree_max_child(p_node_child);
} else {
p_rightmost_ref = p_node->p_parent;
}
}
}
while(p_node_child != p_root_ref) {
if(p_node_child->p_child[0]->level < p_node_child->level - 1 ||
p_node_child->p_child[1]->level < p_node_child->level - 1) {
--(p_node_child->level);
if(p_node_child->p_child[1]->level > p_node_child->level)
p_node_child->p_child[1]->level = p_node_child->level;
skew(p_node_child, p_root_ref, p_null_node);
skew(p_node_child->p_child[1], p_root_ref, p_null_node);
skew(p_node_child->p_child[1]->p_child[1], p_root_ref, p_null_node);
split(p_node_child, p_root_ref, p_null_node);
split(p_node_child->p_child[1], p_root_ref, p_null_node);
}
p_node_child = p_node_child->p_parent;
}
}
Sorry for being a little vague but I am having some trouble tracking this bug.
Edit:I've edited this down for terseness.
Edit: The behavior I'm seeing: The code above the while loop in erase_rebalance() is intended to disconnect the node to be deleted from the tree. I took it from EASTL. p_node_child however, is coming up pointing to the null_node on the every other node to be deleted. Further, when calling erase(iterator first, iterator last), at the 15th node to be deleted (we're deleting all but the first node and last nodes in the tree) the while loop in erase_rebalance goes into an infinite loop. I'm not sure what else to put, but this is the behavior I'm seeing. p_node_child should be where the rebalancing starts after the in-order successor to the deleted node replaces the deleted node.
So, that's what I've got for now, and I apologize for the original post being too large and vague.