// Include once.
#ifndef ABSTRACT_CONTAINER_AVL_TREE_H_
#define ABSTRACT_CONTAINER_AVL_TREE_H_
// Abstract AVL Tree Template.
//
// This code is in the public domain. See avl_tree.html for interface
// documentation.
//
// Version: 1.2 Author: Walt Karas
//
// NOTE: Within the implementation, it's generally more convenient to
// define the depth of the root node to be 0 (0-based depth) rather than
// 1 (1-based depth).
#include "bitset"
namespace abstract_container
{
#ifndef ABSTRACT_CONTAINER_SEARCH_TYPE_
#define ABSTRACT_CONTAINER_SEARCH_TYPE_
enum search_type
{
EQUAL = 1,
LESS = 2,
GREATER = 4,
LESS_EQUAL = EQUAL | LESS,
GREATER_EQUAL = EQUAL | GREATER
};
#endif
// The base_avl_tree template is the same as the avl_tree template,
// except for one additional template parameter: bset. Here is the
// reference class for bset.
//
// class bset
// {
// public:
//
// class ANY_bitref
// {
// public:
// operator bool (void);
// void operator = (bool b);
// };
//
// // Does not have to initialize bits.
// bset(void);
//
// // Must return a valid value for index when 0 <= index < max_depth
// ANY_bitref operator [] (unsigned index);
//
// // Set all bits to 1.
// void set(void);
//
// // Set all bits to 0.
// void reset(void);
// };
//
template <class abstractor, unsigned max_depth, class bset>
class base_avl_tree
{
public:
typedef typename abstractor::key key;
typedef typename abstractor::handle handle;
typedef typename abstractor::size size;
inline handle insert(handle h);
inline handle search(key k, search_type st = EQUAL);
inline handle search_least(void);
inline handle search_greatest(void);
inline handle remove(key k);
void purge(void) { root = null(); }
bool is_empty(void) { return(root == null()); }
bool read_error(void) { return(abs.read_error()); }
base_avl_tree(void) : root(null()) { }
class iter
{
public:
// NOTE: GCC allows these member functions to be defined as
// explicitly inline outside the class, but Visual C++ .NET does
// not.
// Initialize depth to invalid value, to indicate iterator is
// invalid. (Depth is zero-base.)
iter(void) { depth = ~0; }
void start_iter(base_avl_tree &tree, key k, search_type st = EQUAL)
{
// Mask of high bit in an int.
const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);
// Save the tree that we're going to iterate through in a
// member variable.
tree_ = &tree;
int cmp, target_cmp;
handle h = tree_->root;
unsigned d = 0;
depth = ~0;
if (h == null())
// Tree is empty.
return;
if (st & LESS)
// Key can be greater than key of starting node.
target_cmp = 1;
else if (st & GREATER)
// Key can be less than key of starting node.
target_cmp = -1;
else
// Key must be same as key of starting node.
target_cmp = 0;
for ( ; ; )
{
cmp = cmp_k_n(k, h);
if (cmp == 0)
{
if (st & EQUAL)
{
// Equal node was sought and found as starting node.
depth = d;
break;
}
cmp = -target_cmp;
}
else if (target_cmp != 0)
if (!((cmp ^ target_cmp) & MASK_HIGH_BIT))
// cmp and target_cmp are both negative or both positive.
depth = d;
h = cmp < 0 ? get_lt(h) : get_gt(h);
if (read_error())
{
depth = ~0;
break;
}
if (h == null())
break;
branch[d] = cmp > 0;
path_h[d++] = h;
}
}
void start_iter_least(base_avl_tree &tree)
{
tree_ = &tree;
handle h = tree_->root;
depth = ~0;
branch.reset();
while (h != null())
{
if (depth != ~0)
path_h[depth] = h;
depth++;
h = get_lt(h);
if (read_error())
{
depth = ~0;
break;
}
}
}
void start_iter_greatest(base_avl_tree &tree)
{
tree_ = &tree;
handle h = tree_->root;
depth = ~0;
branch.set();
while (h != null())
{
if (depth != ~0)
path_h[depth] = h;
depth++;
h = get_gt(h);
if (read_error())
{
depth = ~0;
break;
}
}
}
handle operator * (void)
{
if (depth == ~0)
return(null());
return(depth == 0 ? tree_->root : path_h[depth - 1]);
}
void operator ++ (void)
{
if (depth != ~0)
{
handle h = get_gt(**this);
if (read_error())
depth = ~0;
else if (h == null())
do
{
if (depth == 0)
{
depth = ~0;
break;
}
depth--;
}
while (branch[depth]);
else
{
branch[depth] = true;
path_h[depth++] = h;
for ( ; ; )
{
h = get_lt(h);
if (read_error())
{
depth = ~0;
break;
}
if (h == null())
break;
branch[depth] = false;
path_h[depth++] = h;
}
}
}
}
void operator -- (void)
{
if (depth != ~0)
{
handle h = get_lt(**this);
if (read_error())
depth = ~0;
else if (h == null())
do
{
if (depth == 0)
{
depth = ~0;
break;
}
depth--;
}
while (!branch[depth]);
else
{
branch[depth] = false;
path_h[depth++] = h;
for ( ; ; )
{
h = get_gt(h);
if (read_error())
{
depth = ~0;
break;
}
if (h == null())
break;
branch[depth] = true;
path_h[depth++] = h;
}
}
}
}
void operator ++ (int) { ++(*this); }
void operator -- (int) { --(*this); }
bool read_error(void) { return(tree_->read_error()); }
protected:
// Tree being iterated over.
base_avl_tree *tree_;
// Records a path into the tree. If branch[n] is true, indicates
// take greater branch from the nth node in the path, otherwise
// take the less branch. branch[0] gives branch from root, and
// so on.
bset branch;
// Zero-based depth of path into tree.
unsigned depth;
// Handles of nodes in path from root to current node (returned by *).
handle path_h[max_depth - 1];
int cmp_k_n(key k, handle h)
{ return(tree_->abs.compare_key_node(k, h)); }
int cmp_n_n(handle h1, handle h2)
{ return(tree_->abs.compare_node_node(h1, h2)); }
handle get_lt(handle h)
{ return(tree_->abs.get_less(h, true)); }
handle get_gt(handle h)
{ return(tree_->abs.get_greater(h, true)); }
handle null(void) { return(tree_->abs.null()); }
};
template<typename fwd_iter>
bool build(fwd_iter p, size num_nodes)
{
// NOTE: GCC allows me to define this outside the class definition
// using the following syntax:
//
// template <class abstractor, unsigned max_depth, class bset>
// template<typename fwd_iter>
// inline void base_avl_tree<abstractor, max_depth, bset>::build(
// fwd_iter p, size num_nodes)
// {
// ...
// }
//
// but Visual C++ .NET won't accept it. Is this a GCC extension?
if (num_nodes == 0)
{
root = null();
return(true);
}
// Gives path to subtree being built. If branch[N] is false, branch
// less from the node at depth N, if true branch greater.
bset branch;
// If rem[N] is true, then for the current subtree at depth N, it's
// greater subtree has one more node than it's less subtree.
bset rem;
// Depth of root node of current subtree.
unsigned depth = 0;
// Number of nodes in current subtree.
size num_sub = num_nodes;
// The algorithm relies on a stack of nodes whose less subtree has
// been built, but whose right subtree has not yet been built. The
// stack is implemented as linked list. The nodes are linked
// together by having the "greater" handle of a node set to the
// next node in the list. "less_parent" is the handle of the first
// node in the list.
handle less_parent = null();
// h is root of current subtree, child is one of its children.
handle h, child;
for ( ; ; )
{
while (num_sub > 2)
{
// Subtract one for root of subtree.
num_sub--;
rem[depth] = !!(num_sub & 1);
branch[depth++] = false;
num_sub >>= 1;
}
if (num_sub == 2)
{
// Build a subtree with two nodes, slanting to greater.
// I arbitrarily chose to always have the extra node in the
// greater subtree when there is an odd number of nodes to
// split between the two subtrees.
h = *p;
if (read_error())
return(false);
p++;
child = *p;
if (read_error())
return(false);
p++;
set_lt(child, null());
set_gt(child, null());
set_bf(child, 0);
set_gt(h, child);
set_lt(h, null());
set_bf(h, 1);
}
else // num_sub == 1
{
// Build a subtree with one node.
h = *p;
if (read_error())
return(false);
p++;
set_lt(h, null());
set_gt(h, null());
set_bf(h, 0);
}
while (depth)
{
depth--;
if (!branch[depth])
// We've completed a less subtree.
break;
// We've completed a greater subtree, so attach it to
// its parent (that is less than it). We pop the parent
// off the stack of less parents.
child = h;
h = less_parent;
less_parent = get_gt(h);
if (read_error())
return(false);
set_gt(h, child);
// num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1
num_sub <<= 1;
num_sub += 1 - rem[depth];
if (num_sub & (num_sub - 1))
// num_sub is not a power of 2
set_bf(h, 0);
else
// num_sub is a power of 2
set_bf(h, 1);
}
if (num_sub == num_nodes)
// We've completed the full tree.
break;
// The subtree we've completed is the less subtree of the
// next node in the sequence.
child = h;
h = *p;
if (read_error())
return(false);
p++;
set_lt(h, child);
// Put h into stack of less parents.
set_gt(h, less_parent);
less_parent = h;
// Proceed to creating greater than subtree of h.
branch[depth] = true;
num_sub += rem[depth++];
} // end for ( ; ; )
root = h;
return(true);
}
protected:
friend class iter;
abstractor abs;
handle root;
handle get_lt(handle h, bool access = true)
{ return(abs.get_less(h, access)); }
void set_lt(handle h, handle lh) { abs.set_less(h, lh); }
handle get_gt(handle h, bool access = true)
{ return(abs.get_greater(h, access)); }
void set_gt(handle h, handle gh) { abs.set_greater(h, gh); }
int get_bf(handle h) { return(abs.get_balance_factor(h)); }
void set_bf(handle h, int bf) { abs.set_balance_factor(h, bf); }
int cmp_k_n(key k, handle h) { return(abs.compare_key_node(k, h)); }
int cmp_n_n(handle h1, handle h2)
{ return(abs.compare_node_node(h1, h2)); }
handle null(void) { return(abs.null()); }
private:
// Balances subtree, returns handle of root node of subtree
// after balancing.
handle balance(handle bal_h)
{
handle deep_h;
// Either the "greater than" or the "less than" subtree of
// this node has to be 2 levels deeper (or else it wouldn't
// need balancing).
if (get_bf(bal_h) > 0)
{
// "Greater than" subtree is deeper.
deep_h = get_gt(bal_h);
if (read_error())
return(null());
if (get_bf(deep_h) < 0)
{
handle old_h = bal_h;
bal_h = get_lt(deep_h);
if (read_error())
return(null());
set_gt(old_h, get_lt(bal_h, false));
set_lt(deep_h, get_gt(bal_h, false));
set_lt(bal_h, old_h);
set_gt(bal_h, deep_h);
int bf = get_bf(bal_h);
if (bf != 0)
{
if (bf > 0)
{
set_bf(old_h, -1);
set_bf(deep_h, 0);
}
else
{
set_bf(deep_h, 1);
set_bf(old_h, 0);
}
set_bf(bal_h, 0);
}
else
{
set_bf(old_h, 0);
set_bf(deep_h, 0);
}
}
else
{
set_gt(bal_h, get_lt(deep_h, false));
set_lt(deep_h, bal_h);
if (get_bf(deep_h) == 0)
{
set_bf(deep_h, -1);
set_bf(bal_h, 1);
}
else
{
set_bf(deep_h, 0);
set_bf(bal_h, 0);
}
bal_h = deep_h;
}
}
else
{
// "Less than" subtree is deeper.
deep_h = get_lt(bal_h);
if (read_error())
return(null());
if (get_bf(deep_h) > 0)
{
handle old_h = bal_h;
bal_h = get_gt(deep_h);
if (read_error())
return(null());
set_lt(old_h, get_gt(bal_h, false));
set_gt(deep_h, get_lt(bal_h, false));
set_gt(bal_h, old_h);
set_lt(bal_h, deep_h);
int bf = get_bf(bal_h);
if (bf != 0)
{
if (bf < 0)
{
set_bf(old_h, 1);
set_bf(deep_h, 0);
}
else
{
set_bf(deep_h, -1);
set_bf(old_h, 0);
}
set_bf(bal_h, 0);
}
else
{
set_bf(old_h, 0);
set_bf(deep_h, 0);
}
}
else
{
set_lt(bal_h, get_gt(deep_h, false));
set_gt(deep_h, bal_h);
if (get_bf(deep_h) == 0)
{
set_bf(deep_h, 1);
set_bf(bal_h, -1);
}
else
{
set_bf(deep_h, 0);
set_bf(bal_h, 0);
}
bal_h = deep_h;
}
}
return(bal_h);
}
};
template <class abstractor, unsigned max_depth, class bset>
inline typename base_avl_tree<abstractor, max_depth, bset>::handle
base_avl_tree<abstractor, max_depth, bset>::insert(handle h)
{
set_lt(h, null());
set_gt(h, null());
set_bf(h, 0);
if (root == null())
root = h;
else
{
// Last unbalanced node encountered in search for insertion point.
handle unbal = null();
// Parent of last unbalanced node.
handle parent_unbal = null();
// Balance factor of last unbalanced node.
int unbal_bf;
// Zero-based depth in tree.
unsigned depth = 0, unbal_depth = 0;
// Records a path into the tree. If branch[n] is true, indicates
// take greater branch from the nth node in the path, otherwise
// take the less branch. branch[0] gives branch from root, and
// so on.
bset branch;
handle hh = root;
handle parent = null();
int cmp;
while (hh != null())
{
if (get_bf(hh) != 0)
{
unbal = hh;
parent_unbal = parent;
unbal_depth = depth;
}
cmp = cmp_n_n(h, hh);
if (cmp == 0)
// Duplicate key.
return(hh);
parent = hh;
hh = cmp < 0 ? get_lt(hh) : get_gt(hh);
if (read_error())
return(null());
branch[depth++] = cmp > 0;
}
// Add node to insert as leaf of tree.
if (cmp < 0)
set_lt(parent, h);
else
set_gt(parent, h);
depth = unbal_depth;
if (unbal == null())
hh = root;
else
{
cmp = branch[depth++] ? 1 : -1;
unbal_bf = get_bf(unbal);
if (cmp < 0)
unbal_bf--;
else // cmp > 0
unbal_bf++;
hh = cmp < 0 ? get_lt(unbal) : get_gt(unbal);
if (read_error())
return(null());
if ((unbal_bf != -2) && (unbal_bf != 2))
{
// No rebalancing of tree is necessary.
set_bf(unbal, unbal_bf);
unbal = null();
}
}
if (hh != null())
while (h != hh)
{
cmp = branch[depth++] ? 1 : -1;
if (cmp < 0)
{
set_bf(hh, -1);
hh = get_lt(hh);
}
else // cmp > 0
{
set_bf(hh, 1);
hh = get_gt(hh);
}
if (read_error())
return(null());
}
if (unbal != null())
{
unbal = balance(unbal);
if (read_error())
return(null());
if (parent_unbal == null())
root = unbal;
else
{
depth = unbal_depth - 1;
cmp = branch[depth] ? 1 : -1;
if (cmp < 0)
set_lt(parent_unbal, unbal);
else // cmp > 0
set_gt(parent_unbal, unbal);
}
}
}
return(h);
}
template <class abstractor, unsigned max_depth, class bset>
inline typename base_avl_tree<abstractor, max_depth, bset>::handle
base_avl_tree<abstractor, max_depth, bset>::search(key k, search_type st)
{
const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);
int cmp, target_cmp;
handle match_h = null();
handle h = root;
if (st & LESS)
target_cmp = 1;
else if (st & GREATER)
target_cmp = -1;
else
target_cmp = 0;
while (h != null())
{
cmp = cmp_k_n(k, h);
if (cmp == 0)
{
if (st & EQUAL)
{
match_h = h;
break;
}
cmp = -target_cmp;
}
else if (target_cmp != 0)
if (!((cmp ^ target_cmp) & MASK_HIGH_BIT))
// cmp and target_cmp are both positive or both negative.
match_h = h;
handle h1 = cmp < 0 ? get_lt(h) : get_gt(h);
h = h1;
if (read_error())
{
match_h = null();
break;
}
}
return(match_h);
}
template <class abstractor, unsigned max_depth, class bset>
inline typename base_avl_tree<abstractor, max_depth, bset>::handle
base_avl_tree<abstractor, max_depth, bset>::search_least(void)
{
handle h = root, parent = null();
while (h != null())
{
parent = h;
h = get_lt(h);
if (read_error())
{
parent = null();
break;
}
}
return(parent);
}
template <class abstractor, unsigned max_depth, class bset>
inline typename base_avl_tree<abstractor, max_depth, bset>::handle
base_avl_tree<abstractor, max_depth, bset>::search_greatest(void)
{
handle h = root, parent = null();
while (h != null())
{
parent = h;
h = get_gt(h);
if (read_error())
{
parent = null();
break;
}
}
return(parent);
}
template <class abstractor, unsigned max_depth, class bset>
inline typename base_avl_tree<abstractor, max_depth, bset>::handle
base_avl_tree<abstractor, max_depth, bset>::remove(key k)
{
// Zero-based depth in tree.
unsigned depth = 0, rm_depth;
// Records a path into the tree. If branch[n] is true, indicates
// take greater branch from the nth node in the path, otherwise
// take the less branch. branch[0] gives branch from root, and
// so on.
bset branch;
handle h = root;
handle parent = null(), child;
int cmp, cmp_shortened_sub_with_path;
for ( ; ; )
{
if (h == null())
// No node in tree with given key.
return(null());
cmp = cmp_k_n(k, h);
if (cmp == 0)
// Found node to remove.
break;
parent = h;
h = cmp < 0 ? get_lt(h) : get_gt(h);
if (read_error())
return(null());
branch[depth++] = cmp > 0;
cmp_shortened_sub_with_path = cmp;
}
handle rm = h;
handle parent_rm = parent;
rm_depth = depth;
// If the node to remove is not a leaf node, we need to get a
// leaf node, or a node with a single leaf as its child, to put
// in the place of the node to remove. We will get the greatest
// node in the less subtree (of the node to remove), or the least
// node in the greater subtree. We take the leaf node from the
// deeper subtree, if there is one.
if (get_bf(h) < 0)
{
child = get_lt(h);
branch[depth] = false;
cmp = -1;
}
else
{
child = get_gt(h);
branch[depth] = true;
cmp = 1;
}
if (read_error())
return(null());
depth++;
if (child != null())
{
cmp = -cmp;
do
{
parent = h;
h = child;
if (cmp < 0)
{
child = get_lt(h);
branch[depth] = false;
}
else
{
child = get_gt(h);
branch[depth] = true;
}
if (read_error())
return(null());
depth++;
}
while (child != null());
if (parent == rm)
// Only went through do loop once. Deleted node will be replaced
// in the tree structure by one of its immediate children.
cmp_shortened_sub_with_path = -cmp;
else
cmp_shortened_sub_with_path = cmp;
// Get the handle of the opposite child, which may not be null.
child = cmp > 0 ? get_lt(h, false) : get_gt(h, false);
}
if (parent == null())
// There were only 1 or 2 nodes in this tree.
root = child;
else if (cmp_shortened_sub_with_path < 0)
set_lt(parent, child);
else
set_gt(parent, child);
// "path" is the parent of the subtree being eliminated or reduced
// from a depth of 2 to 1. If "path" is the node to be removed, we
// set path to the node we're about to poke into the position of the
// node to be removed.
handle path = parent == rm ? h : parent;
if (h != rm)
{
// Poke in the replacement for the node to be removed.
set_lt(h, get_lt(rm, false));
set_gt(h, get_gt(rm, false));
set_bf(h, get_bf(rm));
if (parent_rm == null())
root = h;
else
{
depth = rm_depth - 1;
if (branch[depth])
set_gt(parent_rm, h);
else
set_lt(parent_rm, h);
}
}
if (path != null())
{
// Create a temporary linked list from the parent of the path node
// to the root node.
h = root;
parent = null();
depth = 0;
while (h != path)
{
if (branch[depth++])
{
child = get_gt(h);
set_gt(h, parent);
}
else
{
child = get_lt(h);
set_lt(h, parent);
}
if (read_error())
return(null());
parent = h;
h = child;
}
// Climb from the path node to the root node using the linked
// list, restoring the tree structure and rebalancing as necessary.
bool reduced_depth = true;
int bf;
cmp = cmp_shortened_sub_with_path;
for ( ; ; )
{
if (reduced_depth)
{
bf = get_bf(h);
if (cmp < 0)
bf++;
else // cmp > 0
bf--;
if ((bf == -2) || (bf == 2))
{
h = balance(h);
if (read_error())
return(null());
bf = get_bf(h);
}
else
set_bf(h, bf);
reduced_depth = (bf == 0);
}
if (parent == null())
break;
child = h;
h = parent;
cmp = branch[--depth] ? 1 : -1;
if (cmp < 0)
{
parent = get_lt(h);
set_lt(h, child);
}
else
{
parent = get_gt(h);
set_gt(h, child);
}
if (read_error())
return(null());
}
root = h;
}
return(rm);
}
// I tried to avoid having a separate base_avl_tree template by having
// bitset<max_depth> be the default for the bset template, but Visual
// C++ would not permit this. It may possibly be desirable to use
// base_avl_tree directly with an optimized version of bset.
//
template <class abstractor, unsigned max_depth = 32>
class avl_tree
: public base_avl_tree<abstractor, max_depth, std::bitset<max_depth> >
{ };
} // end namespace abstract_container
#endif
Submit an article or tip