head.h

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

struct Node {
	int value;
	int bal_fac;
	Node* left;
	Node* right;
};

class AVLTree {
	Node* root;
public:
	AVLTree() : root(0) {}
	AVLTree(int a[], int size);
	~AVLTree();
	
	int Create(int a[], int head, int tail, Node* &Father);
	void Destruct(Node* Father);
	
	void LeftRotate(Node* &Father, Node* Son);
	void RightRotate(Node* &Father, Node* Son);
	
	Node* Getroot() {return root;}
	void Traverse();
	
	Node*& Insert(int val, int &type);
	void Ins_Adjust(int type, Node* &Father);
	void AVLInsert(int val);
	
	Node*& Delete(int val, int &type, int module = 0);
	void Del_Adjust(int type, Node* &Father);
	void AVLDelete(int val);
	
	bool Search_InOrNot(int val);
	void Search_NthSmallest(int N, bool &mark, int &result, Node* temp, int &count);
};

void Test_StepByStep();
void Test_WithSetOfData();