avl_tree.h

AVL Tree的实现

// 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())