head.h

B树及其B+树的实现代码

#include <iostream>
#include <list>
#include <stack>
#include <utility>

#ifndef HEAD_H_
#define HEAD_H_

template <class Val_Type, int M>
class M_Way_Tree;
template <class Val_Type, int M>
class B_Tree;
template <class Val_Type, int M>
class B_plus_Tree;

//Definition of "Node"
template <class Val_Type, int M>
class Node {
protected:
	int                    keyTally;
	Val_Type               keys[M];
	Node*                  pointers[M + 1];
	Node*                  parent;
	bool                   is_leaf;
public:
	friend class M_Way_Tree<Val_Type, M>;
	friend class B_Tree<Val_Type, M>;
	friend class B_plus_Tree<Val_Type, M>;
	Node();
	Node(Node*, Val_Type a[], int, bool = true);
	Node(const Node& a);
	~Node();
	void Sort();
	virtual inline void Delete() {};
	virtual void Insert_Next(Node<Val_Type, M>*) {};
};

//Definition of "B_plus_Leaf"
template <class Val_Type, int M>
class B_plus_Leaf : public Node<Val_Type, M> {
private:
	B_plus_Leaf<Val_Type, M> *next, *previous;
public:
	friend class B_plus_Tree<Val_Type, M>;
	B_plus_Leaf() : next(NULL), previous(NULL) {}
	B_plus_Leaf(const Node<Val_Type, M>& );
	inline void Delete();
	void Insert_Next(B_plus_Leaf<Val_Type, M>*);
};

//Definition of "M_Way_Tree"
template <class Val_Type, int M>
class M_Way_Tree {
protected:
	Node<Val_Type, M>* root;
public:
	M_Way_Tree() : root(0) {}
	~M_Way_Tree();
	virtual void Traverse(Node<Val_Type, M>* pointer) const;
	inline Node<Val_Type, M>* Getroot() const;
	virtual int Height() const;
};

//Definition of "B_Tree"
template <class Val_Type, int M>
class B_Tree : public M_Way_Tree<Val_Type, M> {
protected:
	void Insert_with_Tobe(Val_Type, std::pair<Node<Val_Type, M>*, int>, Node<Val_Type, M>*);
	bool Delete_Adjust(Node<Val_Type, M>*);
public:
	std::pair<Node<Val_Type, M>*, int> Search(Val_Type val) const;
	void Insert(Val_Type val);
	bool Delete(Val_Type val);
	virtual void Traverse(Node<Val_Type, M>* pointer) const;
	inline int Height() const;
};

//Definition of "B_plus_Tree"
template <class Val_Type, int M>
class B_plus_Tree : public B_Tree<Val_Type, M> {
private:
	int num_of_leaf;
	B_plus_Leaf<Val_Type, M>* head;
public:
	B_plus_Tree() : num_of_leaf(0) {}
	std::pair<Node<Val_Type, M>*, int> Search(Val_Type val) const;
	void Insert(Val_Type val);
	bool Delete(Val_Type val);
	void Traverse();
	void Traverse(Node<Val_Type, M>* pointer) const;
	int Num_of_Leaf() const;
}; 	

//Functions for "Node"
template <class Val_Type, int M>
inline Node<Val_Type, M>::Node() : is_leaf(true), parent(0), keyTally(0) {
	for (int i = 0; i < M; i++) {
		pointers[i] = NULL;
		keys[i] = INT_MAX;
	}
	pointers[M] = NULL;
}

template <class Val_Type, int M>
inline Node<Val_Type, M>::Node(Node* papa, Val_Type val[], int num, bool isleaf)
: is_leaf(isleaf), parent(papa) {
	for (int i = 0; i <= M; i++)
		pointers[i] = NULL;
	for (int i = 0; i < M; i++)
		keys[i] = val[i];
	keyTally = num;
}

template <class Val_Type, int M>
inline Node<Val_Type, M>::Node(const Node& a) {
	for (int i = 0; i < M; i++) {
		keys[i] = a.keys[i];
		pointers[i] = a.pointers[i];
	}
	pointers[M] = a.pointers[M];
	is_leaf = a.is_leaf;
	parent = a.parent;
	keyTally = num;
}

template <class Val_Type, int M>
inline Node<Val_Type, M>::~Node() {
	for (int i = 0; i < M; i++) {
		pointers[i] = NULL;
		keys[i] = INT_MAX;
	}
	pointers[M] = NULL;
	parent = NULL;
}

template <class Val_Type, int M>
void Node<Val_Type, M>::Sort() {}

//Functions for "B_plus_Leaf"
template <class Val_Type, int M>
B_plus_Leaf<Val_Type, M>::B_plus_Leaf(const Node<Val_Type, M>& a) {
	for (int i = 0; i < M; i++) {
		keys[i] = a.keys[i];
		pointers[i] = a.pointers[i];
	}
	pointers[M] = a.pointers[M];
	is_leaf = true;
	parent = a.parent;
	keyTally = num;
	previous = NULL;
	next = NULL;
}

template <class Val_Type, int M>
void B_plus_Leaf<Val_Type, M>::Delete() {
	if (previous != NULL) 
		previous->next = next;
	if (next != NULL)
		next->previous = previous;
	return;
}

template <class Val_Type, int M>
void B_plus_Leaf<Val_Type, M>::Insert_Next(B_plus_Leaf<Val_Type, M>* temp) {
	temp->next = next;
	if (next != NULL)
		next->previous = temp;
	next = temp;
	temp->previous = this;
	return;
}

//Functions for "M_Way_Tree"
template <class Val_Type, int M>
M_Way_Tree<Val_Type, M>::~M_Way_Tree() {
	if (root == 0) return;
	using namespace std;
	stack<Node<Val_Type, M>*> nodes;
	nodes.push(root);
	Node<Val_Type, M>* temp = NULL;
	while (! nodes.empty()) {
		temp = nodes.top();
		nodes.pop();
		for (int i = 0; i <= M; i++)
			if (temp->pointers[i] != 0) nodes.push(temp->pointers[i]);
		delete temp;
	}
}

template <class Val_Type, int M>
void M_Way_Tree<Val_Type, M>::Traverse(Node<Val_Type, M>* pointer) const {
	if (pointer == NULL) return;
	if (pointer->keyTally > M) {
		std::cout << "KeyTally Error occurred at : " << std::endl; 
		return;
	}
	for (int i = 0; i < pointer->keyTally; i++) {
		if (!pointer->is_leaf && pointer->pointers[i]->parent != pointer)
			std::cout << "Parent Error occurred at : " << pointer << std::endl;
		//std::cout << pointer->keys[i] << std::endl;
		Traverse(pointer->pointers[i]);
	}
	Traverse(pointer->pointers[pointer->keyTally]);
}

template <class Val_Type, int M>
inline Node<Val_Type, M>* M_Way_Tree<Val_Type, M>::Getroot() const {
	return root;
}

template <class Val_Type, int M>
int M_Way_Tree<Val_Type, M>::Height() const {
	if (root == NULL) return 0;
	std::deque<Node<Val_Type, M>*> nodes;
	nodes.push_back(root);
	int count = 1, h = 0, tcount = 0;
	while (! nodes.empty()) {
		Node<Val_Type, M>* temp = nodes.front();
		nodes.pop_front();
		count--;
		if (count == 0) h++;
		for (int i = 0; i < temp->keyTally + 1; i++) {
			if (temp->pointers[i] != NULL) {
				nodes.push_back(temp->pointers[i]);
				tcount++;
			}
			else break;
		}
		if (count == 0) {
			count = tcount;
			tcount = 0;
		}
	}
	return h;
}

//Functions for "B_Tree"
template <class Val_Type, int M>
std::pair<Node<Val_Type, M>*, int> B_Tree<Val_Type, M>::Search(Val_Type val) const {
	Node<Val_Type, M>* temp = root;
	Node<Val_Type, M>* leaf = NULL;
	int mark = -1;
	while (temp != NULL) {
		int i = 1;
		while (i <= temp->keyTally && temp->keys[i-1] < val) i++;
		if (temp->keys[i-1] > val || i > temp->keyTally) {
			if (temp->is_leaf) { leaf = temp; mark = i-1; }
			temp = temp->pointers[i-1];
		}
		else return std::pair<Node<Val_Type, M>*, int>(temp, i-1);
	}
	return std::pair<Node<Val_Type, M>*, int>(leaf, mark);
}

template <class Val_Type, int M>
void B_Tree<Val_Type, M>::Insert_with_Tobe(Val_Type val, std::pair<Node<Val_Type, M>*, int> Tobe, Node<Val_Type, M>* spltdnode) {
	if (Tobe.second >= 0 && Tobe.first != NULL && Tobe.first->keys[Tobe.second] == val) 
		return;
	Node<Val_Type, M> *newrootleft = NULL, *newrootright = NULL;
	Node<Val_Type, M>* splitednode = spltdnode;
	Val_Type splitedkey = val;
	if (Tobe.first == NULL) {
		root = new Node<Val_Type, M>;
		root->keyTally = 1;
		root->keys[0] = val;
		return;
	}
	while (Tobe.first != NULL) {
		if (Tobe.first->keyTally < M) {
			for (int i = Tobe.first->keyTally; i > Tobe.second; i--) {
				Tobe.first->keys[i] = Tobe.first->keys[i-1];
				Tobe.first->pointers[i+1] = Tobe.first->pointers[i];
			}
			Tobe.first->keys[Tobe.second] = splitedkey;
			Tobe.first->pointers[Tobe.second+1] = splitednode;
			if (splitednode != NULL)
				splitednode->parent = Tobe.first;
			++Tobe.first->keyTally;
			return;
		}
		else {
			Node<Val_Type, M>* temp = new Node<Val_Type, M>;
			temp->keyTally = (M + 1) / 2;
			Tobe.first->keyTally = M / 2;
			temp->is_leaf = Tobe.first->is_leaf;
			if (Tobe.second <= M / 2) {
				for (int i = 0; i < (M + 1) / 2; i++) {
					temp->keys[i] = Tobe.first->keys[M/2+i];
					temp->pointers[i+1] = Tobe.first->pointers[M/2+i+1];
					if (Tobe.first->pointers[M/2+i+1] != NULL)
						Tobe.first->pointers[M/2+i+1]->parent = temp;
					Tobe.first->pointers[M/2+i+1] = NULL;
				}
				for (int i = M / 2; i > Tobe.second; i--) {
					Tobe.first->keys[i] = Tobe.first->keys[i-1];
					Tobe.first->pointers[i+1] = Tobe.first->pointers[i];
				}
				Tobe.first->keys[Tobe.second] = splitedkey;
				Tobe.first->pointers[Tobe.second+1] = splitednode;
				if (splitednode != NULL)
					splitednode->parent = Tobe.first;
			}
			else {
				int j = (M + 1) / 2 - 1, i = M - 1;
				for (; i >= Tobe.second; i--, j--) {
					temp->keys[j] = Tobe.first->keys[i];
					if (Tobe.first->pointers[i+1] != NULL)
						Tobe.first->pointers[i+1]->parent = temp;
					temp->pointers[j+1] = Tobe.first->pointers[i+1];
					Tobe.first->pointers[i+1] = NULL;
				}
				temp->keys[j] = splitedkey;
				temp->pointers[j+1] = splitednode;
				if (splitednode != NULL)
						splitednode->parent = temp;
				j--;
				for (; j >= 0; j--, i--) {
					temp->keys[j] = Tobe.first->keys[i];
					if (Tobe.first->pointers[i+1] != NULL)
						Tobe.first->pointers[i+1]->parent = temp;
					temp->pointers[j+1] = Tobe.first->pointers[i+1];
					Tobe.first->pointers[i+1] = NULL;
				}
			}
			temp->pointers[0] = Tobe.first->pointers[M/2+1];
			if (Tobe.first->pointers[M/2+1] != NULL)
				Tobe.first->pointers[M/2+1]->parent = temp;
			Tobe.first->pointers[M/2+1] = NULL;
			splitedkey = Tobe.first->keys[M/2];
			splitednode = temp;
			if (Tobe.first->parent == NULL) {
				newrootleft = Tobe.first;
				newrootright = temp;
				Tobe = std::pair<Node<Val_Type, M>*, int>(NULL, 0);
			}
			else {
				int i = 1;
				for (; i <= Tobe.first->parent->keyTally && Tobe.first->parent->keys[i-1] < splitedkey; i++);
				Tobe = std::pair<Node<Val_Type, M>*, int>(Tobe.first->parent, i-1);
			}
		}
	}
	Node<Val_Type, M>* newroot = new Node<Val_Type, M>;
	newroot->is_leaf = false;
	newroot->keys[0] = splitedkey;
	newroot->pointers[0] = newrootleft;
	newroot->pointers[1] = newrootright;
	newroot->keyTally = 1;
	newrootleft->parent = newroot;
	newrootright->parent = newroot;
	root = newroot;
	return;
}

template <class Val_Type, int M>
void B_Tree<Val_Type, M>::Insert(Val_Type val) {
	std::pair<Node<Val_Type, M>*, int> Tobe = Search(val);
	Insert_with_Tobe(val, Tobe, NULL);
	return;
}