avl_tree.h

AVL Tree的实现

		  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 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 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;
	h = cmp < 0 ? get_lt(h) : get_gt(h);
	if (read_error())
	  {
	    match_h = null();
	    break;
	  }
      }

    return(match_h);
  }

template <class abstractor, unsigned max_depth, class bset>
inline 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 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 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