avltree.cpp

AVL树的实现代码（包括插入

#include "head.h"
#include <stack>
#include <iostream>
using namespace std;

extern Node* null;

int AVLTree::Create(int a[], int head, int tail, Node* &Father) {
	if (head > tail) {
		Father = NULL;
		return 0;
	}
	int mid = (head + tail) / 2;
	Father = new Node;
	Father->value = a[mid];
	int leftheight = Create(a, head, mid - 1, Father->left);
	int rightheight = Create(a, mid + 1, tail, Father->right);
	Father->bal_fac = leftheight - rightheight;
	if (leftheight > rightheight) return leftheight + 1;
	else return rightheight + 1;
}

void AVLTree::Destruct(Node* Father) {
	if (Father == NULL) return;
	Node* tleft = Father->left;
	Node* tright = Father->right;
	delete Father;
	Destruct(tleft);
	Destruct(tright);
}

AVLTree::AVLTree(int a[], int size) {
	Create(a, 0, size - 1, root);
}

AVLTree::~AVLTree() {
	Destruct(root);
	root = NULL;
}

void AVLTree::LeftRotate(Node* &Father, Node* Son) {
	Father->right = Son->left;
	Son->left = Father;
	Father = Son;
}

void AVLTree::RightRotate(Node* &Father, Node* Son) {
	Father->left = Son->right;
	Son->right = Father;
	Father = Son;
}

void AVLTree::Traverse() {
	if (root == NULL) { cout << "It's Empty!" << endl; return; }
	deque<Node*> nodes;
	nodes.push_back(root);
	while (! nodes.empty()) {
		Node* temp = nodes.front();
		cout << temp->value << "(" << temp->bal_fac << ")  " << endl;
		nodes.pop_front();
		if (temp->left != NULL) nodes.push_back(temp->left);
		if (temp->right != NULL) nodes.push_back(temp->right);
	}
}

Node*& AVLTree::Insert(int val,int &type) {
	if (root == NULL) {
		root = new Node;
		root->value = val;
		root->left = root->right = NULL;
		root->bal_fac = 0;
		type = -1;
		return root;
	}
	Node* point = root;
	Node* pfather = root;
	stack<Node*> nodes;
	int LorR[2] = {0, 0};
	while (point != NULL) {
		pfather = point;
		if (point->value > val) 
			point = point->left;
		else if (point->value < val) 
			point = point->right;
		else return null;
		nodes.push(pfather);
	}
	if (pfather->value > val) {
		pfather->left = new Node;
		pfather->left->value = val;
		pfather->left->left = NULL;
		pfather->left->right = NULL;
		pfather->left->bal_fac = 0;
		nodes.top()->bal_fac += 1;
		if (nodes.top()->bal_fac == 0) return null;
		LorR[0] = -1;
	}
	else {
		pfather->right = new Node;
		pfather->right->value = val;
		pfather->right->left = NULL;
		pfather->right->right = NULL;
		pfather->right->bal_fac = 0;
		nodes.top()->bal_fac += -1;
		if (nodes.top()->bal_fac == 0) return null;
		LorR[0] = 1;
	}
	int mark = 1;
	Node* temp = nodes.top();
	nodes.pop();
	while(! nodes.empty() && mark) {
		if (nodes.top()->left == temp) {
			nodes.top()->bal_fac += 1;
			LorR[1] = LorR[0];
			LorR[0] = -1;
		}
		else {
			nodes.top()->bal_fac += -1;
			LorR[1] = LorR[0];
			LorR[0] = 1;
		}
		if (nodes.top()->bal_fac == 0) mark = 0;
		if (nodes.top()->bal_fac == -2 || nodes.top()->bal_fac == 2) {
			if (LorR[0] == -1 && LorR[1] == -1) type = 0;
			if (LorR[0] == -1 && LorR[1] == 1) type = 1;
			if (LorR[0] == 1 && LorR[1] == -1) type = 2;
			if (LorR[0] == 1 && LorR[1] == 1) type = 3;
			temp = nodes.top();
			nodes.pop();
			if (! nodes.empty()) 
				if (nodes.top()->left == temp) return nodes.top()->left;
				else return nodes.top()->right;
			else return root;
		}
		temp = nodes.top();
		nodes.pop();
	}
	return null;	
}

void AVLTree::Ins_Adjust(int type, Node* &Father) {
	if (type == -1) return;
	else if (type == 0) {
		Father->bal_fac = 0;
		Father->left->bal_fac = 0;
		RightRotate(Father, Father->left);
	}
	else if (type == 1) {
		int Cbal = Father->left->right->bal_fac;
		LeftRotate(Father->left, Father->left->right);
		RightRotate(Father, Father->left);
		Father->bal_fac = 0;
		Father->left->bal_fac = 0;
		Father->right->bal_fac = 0;
		if (Cbal == 1) Father->right->bal_fac = -1;
		if (Cbal == -1) Father->left->bal_fac = 1;
	}
	else if (type == 2) {
		int Cbal = Father->right->left->bal_fac;
		RightRotate(Father->right, Father->right->left);
		LeftRotate(Father, Father->right);
		Father->bal_fac = 0;
		Father->left->bal_fac = 0;
		Father->right->bal_fac = 0;
		if (Cbal == 1) Father->right->bal_fac = -1;
		if (Cbal == -1) Father->left->bal_fac = 1;
	}
	else {
		Father->bal_fac = 0;
		Father->right->bal_fac = 0;
		LeftRotate(Father, Father->right);
	}
}

void AVLTree::AVLInsert(int val) { 
	int type;
	Node* &temp = Insert(val, type);
	if (temp != NULL) 
		Ins_Adjust(type, temp);
}

Node*& AVLTree::Delete(int val, int &type, int module) {
	Node* point = root;
	Node* pfather = root;
	stack<Node*> nodes;
	int LorR = 0;
	while (point != NULL) {
		pfather = point;
		nodes.push(pfather);
		if (point->value > val) 
			point = point->left;
		else if (point->value < val) 
			point = point->right;
		else break;
	}
	if (module == 0) {
		if (point == NULL) return null;
		if (point->left == NULL && point->right == NULL) {
			nodes.pop();
			if (nodes.empty()) { delete root; root = NULL; return null; }
			pfather = nodes.top();
			if (pfather->left == point) {
				pfather->left = NULL;
				if (pfather->bal_fac == 0) {pfather->bal_fac = -1;return null;}
				else pfather->bal_fac += -1;
				LorR = -1;
			}
			else {
				pfather->right = NULL;
				if (pfather->bal_fac == 0) {pfather->bal_fac = 1;return null;}
				else pfather->bal_fac += 1;
				LorR = 1;
			}
			delete point;
		}
		else {
			if (point->left != NULL) {
				Node* temp = point->left;
				Node* temparent = point;
				while (temp->right != NULL) {
					temp = temp->right;
					if (temparent == point) temparent = temparent->left;
					else temparent = temparent->right;
					nodes.push(temparent);
				}
				point->value = temp->value;
				if (temparent == point) {
					point->left = temp->left;
					delete temp;
					if (point->bal_fac == 0) {point->bal_fac = -1; return null;}
					else point->bal_fac += -1;
					LorR = -1;
				}
				else {
					temparent->right = temp->left;
					delete temp;
					if (temparent->bal_fac == 0) {temparent->bal_fac = 1; return null;}
					else temparent->bal_fac += 1;
					LorR = 1;
				}
			}
			else {
				Node* temp = point->right;
				Node* temparent = point;
				while (temp->left != NULL) {
					temp = temp->left;
					if (temparent == point) temparent = temparent->right;
					else temparent = temparent->left;
					nodes.push(temparent);
				}
				point->value = temp->value;
				if (temparent == point) {
					point->right = temp->right;
					delete temp;
					if (point->bal_fac == 0) {point->bal_fac = 1; return null;}
					else point->bal_fac += 1;
					LorR = 1;
				}
				else {
					temparent->left = temp->right;
					delete temp;
					if (temparent->bal_fac == 0) {temparent->bal_fac = -1; return null;}
					else temparent->bal_fac += -1;
					LorR = -1;
				}
			}
		}
	}
	else {}
	bool sym = true;
	Node* temp;
	while(! nodes.empty()) {
		if (sym && (nodes.top()->bal_fac == -2 || nodes.top()->bal_fac == 2)) {
			type = LorR;
			temp = nodes.top();
			nodes.pop();
			if (! nodes.empty()) 
				if (nodes.top()->left == temp) return nodes.top()->left;
				else return nodes.top()->right;
			else return root;
		}
		if (sym) {
			temp = nodes.top();
			nodes.pop();
			sym = false;
			continue;
		}
		if (nodes.top()->left == temp) {
			if (nodes.top()->bal_fac == 0) {nodes.top()->bal_fac = -1; return null;}
			else nodes.top()->bal_fac += -1;
			LorR = -1;
		}
		else {
			if (nodes.top()->bal_fac == 0) {nodes.top()->bal_fac = 1; return null;}
			else nodes.top()->bal_fac += 1;
			LorR = 1;
		}
		if (nodes.top()->bal_fac == -2 || nodes.top()->bal_fac == 2) {
			type = LorR;
			temp = nodes.top();
			nodes.pop();
			if (! nodes.empty()) 
				if (nodes.top()->left == temp) return nodes.top()->left;
				else return nodes.top()->right;
			else return root;
		}
		temp = nodes.top();
		nodes.pop();
	}
	return null;
}

void AVLTree::Del_Adjust(int type, Node* &Father) {
	if (type == -1) {
		if (Father->right->bal_fac == 0) {
			Father->bal_fac = -1;
			Father->right->bal_fac = 1;
			LeftRotate(Father, Father->right);
			return;
		}
		else if (Father->right->bal_fac == -1) {
			Father->bal_fac = 0;
			Father->right->bal_fac = 0;
			LeftRotate(Father, Father->right);
		}
		else {
			int mark = Father->right->left->bal_fac;
			Father->right->left->bal_fac = 0;
			Father->bal_fac = (mark == -1) ? 1 : 0;
			Father->right->bal_fac = (mark == 1) ? -1 : 0;
			RightRotate(Father->right, Father->right->left);
			LeftRotate(Father, Father->right);
		}
	}
	else {
		if (Father->left->bal_fac == 0) {
			Father->bal_fac = 1;
			Father->left->bal_fac = -1;
			RightRotate(Father, Father->left);
			return;
		}
		else if (Father->left->bal_fac == 1) {
			Father->bal_fac = 0;
			Father->left->bal_fac = 0;
			RightRotate(Father, Father->left);
		}
		else {
			int mark = Father->left->right->bal_fac;
			Father->left->right->bal_fac = 0;
			Father->bal_fac = (mark == 1) ? -1 : 0;
			Father->left->bal_fac = (mark == -1) ? 1 : 0;
			LeftRotate(Father->left, Father->left->right);
			RightRotate(Father, Father->left);
		}
	}
	int t;
	Node* &temp = Delete(Father->value, t, 1);
	if (temp != NULL)
		Del_Adjust(t, temp);
}

void AVLTree::AVLDelete(int val) {
	int type;
	Node* &temp = Delete(val, type);
	if (temp != NULL) 
		Del_Adjust(type, temp);
}

bool AVLTree::Search_InOrNot(int val) {
	if (root == NULL) return false;
	Node* temp = root;
	while (temp != NULL) {
		if (temp->value == val) return true;
		else temp = (temp->value > val) ? temp->left : temp->right;
	}
	return false;
}

void AVLTree::Search_NthSmallest(int N, bool &mark, int &result, Node* temp, int &count) {
	if (root == NULL || N <= 0) {mark = false; return;}
	if (temp->left != NULL) Search_NthSmallest(N, mark, result, temp->left, count);
	if (++count == N) {mark = true; result = temp->value; return;}
	if (count < N && temp->right != NULL) Search_NthSmallest(N, mark, result, temp->right, count);
	else {mark = false; return;}
}