btree.h

用Borland C写的B-Tree算法

		assert(node->count == order-1);
		/* no room, split and insert into parent */
		/* note: node is full, don't need to look at count anymore... */
		BTREE<KEY> *new_node = new BTREE<KEY>(order);
		BTREE<KEY> *ptr = NULL;		// which node added in
		BTREE<KEY> *added;
		BTREE_POS temp_pos;

		assert (new_node != NULL);

		/* assume has same parent, if it splits will fix itself */
		new_node->parent = node->parent;

		/* doesn't fit, split into two nodes, right first */
		new_node->count = order/2;

		KEY median_key;

		if (i < order/2) {
			// insert in original node
			pos=i;
			ptr=node;

			// first fill in new node
			for (j=0; j<order/2; ++j) {
				new_node->key[j]=node->key[j+order/2];
				new_node->ptr[j]=node->ptr[j+order/2];
			}
			new_node->ptr[j]=node->ptr[j+order/2];
		
			median_key = node->key[order/2-1];

			// insert...
			for (j=order/2-1; j>i; --j) {
				node->key[j] = node->key[j-1];
				node->ptr[j+1] = node->ptr[j];
			}
			node->ptr[j+1] = node->ptr[j];
			node->key[i] = key;
			assert(ptr->key[pos] == key);
			node->count = order/2;
		} else if (i == order/2) {
			// key is median, so insert in parent instead
			median_key = key;

			// just fill in new node
			for (j=0; j<order/2; ++j) {
				new_node->key[j]=node->key[j+order/2];
				new_node->ptr[j]=node->ptr[j+order/2];
			}
			new_node->ptr[j]=node->ptr[j+order/2];
			node->count = order/2;
		} else {
			assert (i > order/2);
			// insert in new_node
			pos = i-order/2-1;
			ptr=new_node;
			for (j=0; j<pos; ++j) {
				new_node->key[j] = node->key[j+order/2+1];
				new_node->ptr[j] = node->ptr[j+order/2+1];
			}
			new_node->ptr[j] = node->ptr[j+order/2+1];
			new_node->key[j] = key;
			assert(ptr->key[pos] == key);
			median_key = node->key[order/2];
			for (j=pos+1; j<order/2; ++j) {
				new_node->key[j] = node->key[j+order/2];
				new_node->ptr[j] = node->ptr[j+order/2];
			}
			new_node->ptr[j] = node->ptr[j+order/2];
			node->count = order/2;
		}

		/* RESET CHILDREN OF NEW TO POINT TO NEW PARENT */
		for (j=0; j<=order/2; ++j) {
			if (new_node->ptr[j] != NULL)
				new_node->ptr[j]->parent = new_node;
		}

		/* wipe out pointers moved to the new_node node */
		for (j=order/2+1; j<order; ++j)
			node->ptr[j] = NULL;

		/* add to parent, create parent if necessary */
		if (node->parent == NULL) {
			node->parent = new BTREE<KEY>(order);
			split_pos = -1;
		} else {
			/* NULL terminate the parent's pointer to this node */
			for (i=0; i <= node->parent->count; ++i) {
				if (node->parent->ptr[i] == node) {
					node->parent->ptr[i] = NULL;
					break;
				}
			}
			assertf(i <= node->parent->count, "%d\n", i);
			split_pos = i;
		}

		assert(node->parent != NULL);

		/* insert the median and the split nodes into the parent node */
		if (ptr == NULL) {
			added = node->parent->add_internal(node, new_node, median_key,
				temp_pos, order, split_pos);
			pos = temp_pos;
		} else
			added = node->parent->add_internal(node, new_node, median_key,
				temp_pos, order, split_pos);

		assert(added->key[temp_pos] == median_key);

		if (left != NULL) {
			if (ptr == NULL) {
				node->ptr[order/2] = left;
				assert(left->parent == node);
				new_node->ptr[0] = right;
				right->parent = new_node;
				node = added;
			} else {
				/* both left and right not NULL */
				assert(right != NULL);
				ptr->ptr[pos] = left;
				ptr->ptr[pos+1] = right;
				left->parent = ptr;
				right->parent = ptr;
				node = ptr;
			}
		}
	}

	return node;
}

/*****************************************************************************
 * remove_internal()	-	forcibly remove key from specified internal node
 *
 * INPUTS: 	position of key to remove
 * OUTPUTS:	modifies contents of B-Tree to remove key
 * RETURNS:	nothing
 *
 * NOTE: does not modify ptr[pos]
 *****************************************************************************/
template <class KEY>
void BTREE<KEY>::remove_internal(BTREE_POS pos, BTREE_POS order)
{
	BTREE_POS i;

	for (i=pos+1; i<count; ++i) {
		key[i-1] = key[i];
		ptr[i] = ptr[i+1];
	}
	if (--count == 0)
		underflow(order);
}

/*****************************************************************************
 * remove()	-	remove specified node
 *
 * INPUTS: 	position of key to remove
 * OUTPUTS:	modifies contents of B-Tree to remove key
 * RETURNS:	nothing
 *****************************************************************************/
template <class KEY>
void BTREE<KEY>::remove(BTREE_POS pos, BTREE_POS order)
{
	BTREE_POS i;

	assertf(order>1 && order%2 == 1, "%d", order);
	assertf(pos >= 0 && pos < order, "%d\n", pos);
	assertf(count > 0 && count < order, "%d\n", count);
	assertf2(pos == 0 || count != 1, "pos=%d, count=%d\n",
		pos, count);

	if (ptr[0] == NULL) {
		// LEAF
		for (i=pos+1; i<count; ++i)
			key[i-1] = key[i];
		if (--count == 0) {
			ptr[0] = NULL;
			underflow(order);
		}
	} else {
		/* INTERIOR: REPLACE BY ITS SUCCESSOR AND DELETE THE SUCCESSOR */
		BTREE_POS succ_pos;
		BTREE<KEY> *succ = find_next(pos, succ_pos);
		assert(succ != NULL);
		assert(succ->count > 0);
		assert(succ->ptr[0] == NULL);
		assert(succ_pos == 0);
		assert(key[pos] <= succ->key[0]);
		key[pos] = succ->key[0];
		succ->remove(0, order);
	}
}

/*****************************************************************************
 * print() - output contents of B-Tree to stdout on one line
 *****************************************************************************/
template <class KEY>
void BTREE<KEY>::print()
{
	BTREE_POS i;

	if (count == 0) {
		cout << "EMPTY" << endl;
		return;
	}

	for (i=0; i < count; ++i) {
		if (ptr[i] != NULL) {
			cout << flush;
			assert(ptr[i]->parent == this);
			ptr[i]->print();
		}
		cout << key[i] << ' ';
	}
	if (ptr[i] != NULL) {
		cout << flush;
		assert(ptr[i]->parent == this);
		ptr[i]->print();
	}
}

/*****************************************************************************
 * levels()	-	count levels of the B-Tree
 *****************************************************************************/
template <class KEY>
int BTREE<KEY>::levels()
{
	BTREE_POS i;
	int levels;
	int max=1;

	for (i=0; i <= count; ++i) {
		levels = 1;
		if (ptr[i] != NULL)
			levels += ptr[i]->levels();
		if (levels > max)
			max = levels;
	}
	return max;
}

/*****************************************************************************
 * get_count()	-	count members of the B-Tree
 *****************************************************************************/
template <class KEY>
long BTREE<KEY>::get_count() const
{
	BTREE_POS i;
	long c=0;

	for (i=0; i <= count; ++i) {
		if (i<count)
			++c;
		if (ptr[i] != NULL)
			c += ptr[i]->get_count();
	}

	return c;
}

/*****************************************************************************
 * display() - output contents of B-Tree to stdout showing hierarchy
 *						horizontally.  Recommended only for very small B-Trees
 *****************************************************************************/
template <class KEY>
void BTREE<KEY>::display(int only_level)
{
	BTREE_POS i;
	int level=1;
	char buffer[80];
	ostrstream s(buffer, sizeof(buffer));

	if (count == 0) {
		cout << "EMPTY" << endl;
		return;
	}

	for (i=0; i < count; ++i) {
		if (ptr[i] != NULL) {
			assert(ptr[i]->parent == this);
			ptr[i]->display(only_level-1);
		}
		s << key[i] << ' ';
		if (level != only_level)
			memset(buffer, ' ', strlen(buffer));
		cout << buffer;
	}
	if (ptr[i] != NULL) {
		cout << flush;
		assert(ptr[i]->parent == this);
		ptr[i]->display(only_level-1);
	}
}

/*****************************************************************************
 * display2() - output contents of B-Tree to stdout showing hierarchy
 *						vertically, easier to read display for large B-Trees
 *****************************************************************************/
template <class KEY>
void BTREE<KEY>::display2(int level)
{
	BTREE_POS i, j;

	if (count == 0) {
		cout << "EMPTY" << endl;
		return;
	}

	for (i=0; i < count; ++i) {
		if (ptr[i] != NULL) {
			cout << flush;
			assert(ptr[i]->parent == this);
			ptr[i]->display2(level+1);
		}
		for (j=0; j<level*6; ++j)
			cout << ' ';
		cout.width(5);
		cout << key[i] << endl;
	}
	if (ptr[i] != NULL) {
		cout << flush;
		assert(ptr[i]->parent == this);
		ptr[i]->display2(level+1);
	}
}

/*****************************************************************************
 * ~BTREE()	-	free all memory allocated for the B-Tree - destructor
 *****************************************************************************/
template <class KEY>
BTREE<KEY>::~BTREE()
{
	BTREE_POS i;

	if (count > 0) {
		for (i=0; i <= count; ++i)
			delete ptr[i];
	}

	delete [] ptr;
	delete [] key;
}

/*****************************************************************************
 * check()	-	check consistency of B-Tree while traversing it
 *						halts program if error found
 *****************************************************************************/
template <class KEY>
void BTREE<KEY>::check(BTREE_POS order)
{
	BTREE_POS i, c;

	if (count == 0)
		return;

	assertf(order>1 && order%2 == 1, "%d", order);
	assert(count > 0 && count < order);

	for (i=c=0; i <= count; ++i) {
		if (i < count)
			++c;
		if (ptr[i] != NULL) {
			assert(ptr[i]->parent == this);
			ptr[i]->check(order);
		}
	}

	assertf2(count == c, "count=%d, c=%d\n", count, c);
}

/*****************************************************************************
 * empty()	-	empty out a B-Tree node leaving allocation of key and ptr
 *****************************************************************************/
template <class KEY>
void BTREE<KEY>::empty() {
	BTREE_POS i;

	for (i=0; i<=count; ++i) {
		if (ptr[i] != NULL) {
			delete ptr[i];
			ptr[i] = NULL;
		}
		if (i<count)
			key[i] = KEY();
	}

	count=0;
}

template <class KEY>
void BTREE<KEY>::traverse(int (*operation)(const KEY& key))
{
	BTREE_POS i;
   static int bExit;

   bExit = 0;

	if (count == 0) {
		return;
	}

	for (i=0; !bExit && i < count; ++i) {
		if (ptr[i] != NULL) {
			assert(ptr[i]->parent == this);
			ptr[i]->traverse(operation);
		}
		if (!operation(key[i]))
      {
        bExit = 1;
      }
	}
	if (!bExit && ptr[i] != NULL) {
		assert(ptr[i]->parent == this);
		ptr[i]->traverse(operation);
	}
}

template <class KEY>
class BTREE_ITERATOR
{
 private:
  /*const*/ BTREE<KEY> /*const*/ *ptr;
  BTREE_POS pos;

 public:
  BTREE_ITERATOR(const BTREE_ROOT<KEY>& root)
  {
    ptr = root.find_first(pos);
  }

  // prefix
  BTREE_ITERATOR operator ++()
  {
    if (*this)
      ptr = ptr->find_next(pos, pos);
    return *this;
  }

  // postfix
  BTREE_ITERATOR operator ++(int)
  {
    BTREE_ITERATOR ret = *this;
    ++(*this);
    return ret;
  }

  // dereference
  const KEY operator *() const
  {
    return ptr->key[pos];
  }

  operator int() const
  {
    return (ptr != 0 && pos >= 0);
  }
};

template <class KEY>
int BTREE_ROOT<KEY>::add_tree(BTREE_ROOT<KEY>& source)
{
  BTREE_POS pos;
  int total = 0;
  for (BTREE_ITERATOR<KEY> p(source); p != 0; ++p)
  {
    if (add(*p, pos) != 0 && pos >= 0)
      ++total;
  }
  return total;
}

#endif // BTREE_H