(模板)AVL树的实现

ゞ浴缸里的玫瑰 2022-04-22 12:20 236阅读 0赞

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    class ANode {
    public:
    	int v, height;   //v表示权值,height表示树的高度
    	ANode *lchild, *rchild;    //左右孩子的结点信息
    };
    
    //建立一个新的结点
    ANode* createNode(int v) {
    	ANode* node = new ANode;
    	node->v = v;
    	node->height = 1;
    	node->lchild = nullptr;
    	node->rchild = nullptr;
    	return node;       //返回当前结点
    }
    
    //获取结点的高度
    int getHegiht(ANode* root) {
    	if (root == nullptr) {
    		return 0;
    	}
    	else {
    		return root->height;
    	}
    }
    
    //计算平衡引子
    int calBanlanceEle(ANode* root) {
    	return getHegiht(root->lchild) - getHegiht(root->rchild);
    }
    
    //更新结点root的height
    void updateHeight(ANode* root) {
    	root->height = max(getHegiht(root->lchild), getHegiht(root->rchild)) + 1;
    }
    
    //相关操作:
    /*查找操作*/
    ANode* search(ANode* root, int value) {
    	if (root == nullptr) {
    		return nullptr;
    	}
    	if (value == root->v) {
    		return root;
    	}
    	else if (value > root->v) {
    		return search(root->rchild, value);
    	}
    	else {
    		return search(root->lchild, value);
    	}
    }
    
    /*左旋操作*/
    void Aleft_rotate(ANode* &root) {
    	ANode* temp = root->rchild;
    	root->rchild = temp->lchild;
    	temp->lchild = root;
    
    	updateHeight(root);
    	updateHeight(temp);
    	root = temp;  //temp称为root
    }
    
    /*右旋操作*/
    void Aright_rotate(ANode* &root) {
    	ANode* temp = root->lchild;
    	root->lchild = temp->rchild;
    	temp->rchild = root;
    
    	updateHeight(root);
    	updateHeight(temp);
    	root = temp;
    }
    
    
    void Ainsert(ANode* &root, int value) {
    	if (root == nullptr) {
    		root = createNode(value);
    		return;
    	}
    
    	if (value == root->v) {
    		return;
    	}
    	else if (value > root->v) {
    		Ainsert(root->rchild, value);   //右树调整
    		updateHeight(root);
    		if (calBanlanceEle(root) == -2) {
    			if (calBanlanceEle(root->rchild) == 1) {  //RL型
    				Aright_rotate(root->rchild);
    				Aleft_rotate(root);
    			}
    			else if (calBanlanceEle(root->rchild) == -1) { //RR型
    				Aleft_rotate(root);
    			}
    		}
    	}
    	else {
    		Ainsert(root->lchild, value);     //左树调整
    		updateHeight(root);
    		if (calBanlanceEle(root) == 2) {
    			if (calBanlanceEle(root->lchild) == 1) {
    				Aright_rotate(root);
    			}
    			else if (calBanlanceEle(root->lchild) == -1) {
    				Aleft_rotate(root->lchild);
    				Aright_rotate(root);
    			}
    		}
    	}
    }
    
    ANode* buildTree(int data[], int n) {
    	ANode* root = nullptr;
    	for (int i = 0; i < n; ++i) {
    		Ainsert(root, data[i]);
    	}
    	return root;
    }
    
    int main() {
    
    	int a[1001];
    	int n;
    	cin >> n;
    	for (int i = 0; i < n; ++i) {
    		cin >> a[i];
    	}
    	
    	ANode* res = buildTree(a, n);
    	cout << res->v << endl;
    
    	system("PAUSE");
    	return 0;
    }