head.h

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

template <class Val_Type, int M>
bool B_Tree<Val_Type, M>::Delete_Adjust(Node<Val_Type, M>* temp) {
	bool mark = false;
	int i = 0;
	Node<Val_Type, M>* sibling = NULL;
	while (temp != NULL) {
		if (temp->parent == NULL || temp->keyTally >= M / 2) {
			if (temp->parent == NULL && temp->keyTally == 0) {delete root; root = NULL;}
			return true;
		}
		i = 0;
		for (; i <= temp->parent->keyTally && temp->parent->pointers[i] != temp; i++);
		if (i != temp->parent->keyTally) {
			sibling = temp->parent->pointers[i+1];
			if (sibling->keyTally >= M / 2 + 1) {
				temp->keyTally++;
				temp->keys[temp->keyTally-1] = temp->parent->keys[i];
				temp->pointers[temp->keyTally] = sibling->pointers[0];
				if (sibling->pointers[0] != NULL)
					sibling->pointers[0]->parent = temp;
				temp->parent->keys[i] = sibling->keys[0];
				for (int j = 0; j < sibling->keyTally - 1; j++) {
					sibling->keys[j] = sibling->keys[j+1];
					sibling->pointers[j] = sibling->pointers[j+1];
				}
				sibling->pointers[sibling->keyTally-1] = sibling->pointers[sibling->keyTally];
				sibling->pointers[sibling->keyTally] = NULL;
				sibling->keyTally--;
			} 
			else mark = true;
		}
		else {
			sibling = temp->parent->pointers[i-1];
			if (sibling->keyTally >= M / 2 + 1) {
				for (int j = temp->keyTally; j > 0; j--) {
					temp->keys[j] = temp->keys[j-1];
					temp->pointers[j+1] = temp->pointers[j];
				}
				temp->pointers[1] = temp->pointers[0];
				temp->keys[0] = temp->parent->keys[i-1];
				temp->pointers[0] = sibling->pointers[sibling->keyTally];
				if (sibling->pointers[sibling->keyTally] != NULL)
					sibling->pointers[sibling->keyTally]->parent = temp;
				temp->parent->keys[i-1] = sibling->keys[sibling->keyTally-1];
				sibling->pointers[sibling->keyTally] = NULL;
				temp->keyTally++;
				sibling->keyTally--;
			} 
			else {
				Node<Val_Type, M>* swap = sibling;
				sibling = temp;
				temp = swap;
				mark = true;
				i--;
			}
		}
		if (mark) {
			temp->keys[temp->keyTally] = temp->parent->keys[i];
			for (int j = 0; j < sibling->keyTally; j++) {
				temp->keys[temp->keyTally+j+1] = sibling->keys[j];
				temp->pointers[temp->keyTally+1+j] = sibling->pointers[j];
				if (sibling->pointers[j] != NULL)
					sibling->pointers[j]->parent = temp;
				sibling->pointers[j] = NULL;
			}
			temp->pointers[temp->keyTally+1+sibling->keyTally] = sibling->pointers[sibling->keyTally];
			if (sibling->pointers[sibling->keyTally] != NULL)
				sibling->pointers[sibling->keyTally]->parent = temp;
			sibling->pointers[sibling->keyTally] = NULL;
			temp->keyTally = temp->keyTally + 1 + sibling->keyTally;
			delete sibling;
			sibling = NULL;
			for (int j = i; j < temp->parent->keyTally - 1; j++) {
				temp->parent->keys[j] = temp->parent->keys[j+1];
				temp->parent->pointers[j+1] = temp->parent->pointers[j+2];
			}
			temp->parent->pointers[temp->parent->keyTally] = NULL;
			temp->parent->keyTally--;
			if (temp->parent->keyTally == 0) {
				for (int i = 0; i <= root->keyTally; i++)
					root->pointers[i] = NULL;
				delete root;
				root = temp;
				root->parent = NULL;
				return true;
			}
		}
		temp = temp->parent;
		mark = false;
	}
	return true;
}

template <class Val_Type, int M>
bool B_Tree<Val_Type, M>::Delete(Val_Type val) {
	std::pair<Node<Val_Type, M>*, int> Tobe = Search(val);
	if (Tobe.first == NULL || Tobe.first->keys[Tobe.second] != val) return false;
	Node<Val_Type, M>* temp = Tobe.first;
	int pos = Tobe.second;
	if (! temp->is_leaf) {
		temp = temp->pointers[pos];
		while (! temp->is_leaf) 
			temp = temp->pointers[temp->keyTally];
		pos = temp->keyTally - 1;
		Tobe.first->keys[Tobe.second] = temp->keys[pos];
	}
	for (int j = pos; j < temp->keyTally - 1; j++)
		temp->keys[j] = temp->keys[j+1];
	temp->keyTally--;
	bool rtn_val = Delete_Adjust(temp);
	return rtn_val;
}

template <class Val_Type, int M>
inline int B_Tree<Val_Type, M>::Height() const {
	Node<Val_Type, M>* temp = root;
	int h = 0;
	while (temp != NULL) {
		temp = temp->pointers[0];
		h++;
	}
	return h;
}

template <class Val_Type, int M>
void B_Tree<Val_Type, M>::Traverse(Node<Val_Type, M>* pointer) const {
	if (pointer == NULL) return;
	if (pointer->keyTally > M || (pointer->parent != NULL && pointer->keyTally < M / 2)) {
		std::cout << "KeyTally Error occurred at : " << pointer << 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]);
}

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

template <class Val_Type, int M>
void B_plus_Tree<Val_Type, M>::Insert(Val_Type val) {
	std::pair<Node<Val_Type, M>*, int> Tobe = Search(val);
	B_plus_Leaf<Val_Type, M>* tobe = (B_plus_Leaf<Val_Type, M>*) Tobe.first;
	if (tobe != NULL && Tobe.second < tobe->keyTally && tobe->keys[Tobe.second] == val) 
		return;
	B_plus_Leaf<Val_Type, M>* temp = NULL;
	B_plus_Leaf<Val_Type, M>* mark = tobe;
	if (tobe == NULL) {
		root = new B_plus_Leaf<Val_Type, M>;
		root->keyTally = 1;
		root->keys[0] = val;
		head = (B_plus_Leaf<Val_Type, M>*) root;
		num_of_leaf = 1;
		return;
	}
	if (tobe->keyTally < M) {
		for (int i = tobe->keyTally; i > Tobe.second; i--)
			tobe->keys[i] = tobe->keys[i-1];
		tobe->keys[Tobe.second] = val;
		++tobe->keyTally;
		return;
	}
	else {
		temp = new B_plus_Leaf<Val_Type, M>;
		temp->keyTally = M / 2 + 1;
		tobe->keyTally = (M + 1) / 2;
		if (Tobe.second <= (M - 1) / 2) {
			for (int i = 0; i < M / 2 + 1; i++) 
				temp->keys[i] = tobe->keys[(M-1)/2+i];
			for (int i = (M - 1) / 2; i > Tobe.second; i--) 
				tobe->keys[i] = tobe->keys[i-1];
			tobe->keys[Tobe.second] = val;
		}
		else {
			int j = M / 2, i = M - 1;
			for (; i >= Tobe.second; i--, j--) 
				temp->keys[j] = tobe->keys[i];
			temp->keys[j] = val;
			j--;
			for (; j >= 0; j--, i--)
				temp->keys[j] = tobe->keys[i];
		}
		if (tobe->parent == NULL) {
			root = new Node<Val_Type, M>;
			root->is_leaf = false;
			root->keys[0] = temp->keys[0];
			root->pointers[0] = Tobe.first;
			root->pointers[1] = temp;
			temp->parent = root;
			Tobe.first->parent = root;
			root->keyTally = 1;
		}
		else {
			int i = 1;
			for (; i <= tobe->parent->keyTally && tobe->parent->keys[i-1] < temp->keys[0]; i++);
			Tobe = std::pair<Node<Val_Type, M>*, int>(tobe->parent, i-1);
			Insert_with_Tobe(temp->keys[0], Tobe, temp);
		}
	}
	num_of_leaf++;
	tobe->Insert_Next(temp);
	return;
}

template <class Val_Type, int M>
bool B_plus_Tree<Val_Type, M>::Delete(Val_Type val) {
	std::pair<Node<Val_Type, M>*, int> Tobe = Search(val);
	if (Tobe.first == NULL || Tobe.first->keys[Tobe.second] != val) return false;
	B_plus_Leaf<Val_Type,M>* temp = (B_plus_Leaf<Val_Type, M>*) Tobe.first;
	int pos = Tobe.second;
	for (int j = pos; j < temp->keyTally - 1; j++)
		temp->keys[j] = temp->keys[j+1];
	temp->keyTally--;
	if (temp->keyTally != 0 && pos == 0 && Tobe.first->parent != NULL) {
		int i = 1;
		for (; i <= temp->parent->keyTally && temp->parent->pointers[i] != temp; i++);
		temp->parent->keys[i-1] = temp->keys[0];
	}
	bool mark = false;
	int i = 0;
	B_plus_Leaf<Val_Type, M>* sibling = NULL;
	if (temp->parent == NULL || temp->keyTally >= M / 2) {
		if (temp->parent == NULL && temp->keyTally == 0) {
			num_of_leaf= 0;
			head = NULL;
			delete root; 
			root = NULL;
		}
		return true;
	}
	for (; i <= temp->parent->keyTally && temp->parent->pointers[i] != temp; i++);
	if (i != temp->parent->keyTally) {
		sibling = (B_plus_Leaf<Val_Type,M>*) temp->parent->pointers[i+1];
		if (sibling->keyTally >= M / 2 + 1) {
			temp->keyTally++;
			temp->keys[temp->keyTally-1] = sibling->keys[0];
			for (int j = 0; j < sibling->keyTally - 1; j++)
				sibling->keys[j] = sibling->keys[j+1];
			sibling->keyTally--;
			temp->parent->keys[i] = sibling->keys[0];
			return true;
		} 
		else mark = true;
	}
	else {
		sibling = (B_plus_Leaf<Val_Type,M>*) temp->parent->pointers[i-1];
		if (sibling->keyTally >= M / 2 + 1) {
			for (int j = temp->keyTally; j > 0; j--) 
				temp->keys[j] = temp->keys[j-1];
			temp->keys[0] = sibling->keys[sibling->keyTally-1];
			temp->keyTally++;
			sibling->keyTally--;
			temp->parent->keys[i-1] = temp->keys[0];
			return true;
		} 
		else {
			B_plus_Leaf<Val_Type,M>* swap = sibling;
			sibling = temp;
			temp = swap;
			mark = true;
			i--;
		}
	}
	if (mark) {
		for (int j = 0; j < sibling->keyTally; j++)
			temp->keys[temp->keyTally+j] = sibling->keys[j];
		temp->keyTally = temp->keyTally + sibling->keyTally;
		num_of_leaf--;
		for (int j = i; j < temp->parent->keyTally - 1; j++) {
			temp->parent->keys[j] = temp->parent->keys[j+1];
			temp->parent->pointers[j+1] = temp->parent->pointers[j+2];
		}
		temp->parent->pointers[temp->parent->keyTally] = NULL;
		temp->parent->keyTally--;
		if (temp->parent->keyTally == 0) {
			delete root;
			root = temp;
			root->parent = NULL;
		}
		else Delete_Adjust(temp->parent);
		sibling->Delete();
		delete sibling;
		sibling = NULL;
	}
	return true;
}

template <class Val_Type, int M>
void B_plus_Tree<Val_Type, M>::Traverse() {
	B_plus_Leaf<Val_Type, M>* temp = head;
	if (temp == NULL) {
		std::cout << "It's Empty." << std::endl;
		return;
	}
	int count = 0;
	while (temp != NULL) {
		count += temp->keyTally;
		for (int i = 0; i < temp->keyTally; i++) 
			std::cout << temp->keys[i] << " ";
		temp = temp->next;
	}
	std::cout << std::endl << "Altogether " << count << " values stored." << std::endl;
	std::cout << std::endl;
	return;
}

template <class Val_Type, int M>
void B_plus_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 : " << pointer << std::endl; 
		return;
	}
	for (int i = 0; i < pointer->keyTally; i++) {
		if (!pointer->is_leaf && pointer->pointers[i+1]->is_leaf && pointer->keys[i] != pointer->pointers[i+1]->keys[0])
			std::cout << "Index Error occurred at : " << pointer << std::endl;
		if (!pointer->is_leaf && pointer->pointers[i]->parent != pointer)
			std::cout << "Parent Error occurred at : " << pointer << std::endl;
		//if (!pointer->is_leaf) std::cout << "Index : ";
		//std::cout << pointer->keys[i] << std::endl;
		Traverse(pointer->pointers[i]);
	}
	Traverse(pointer->pointers[pointer->keyTally]);
}

template <class Val_Type, int M>
int B_plus_Tree<Val_Type, M>::Num_of_Leaf() const {
	return num_of_leaf;
}

#endif