- // <Copyright liaoqb>
- #include <iostream>
- using namespace std;
- enum factor {left_height, equal_height, right_height};
- class AVL_Tree {
- protected:
- struct avl_tree {
- int data;
- avl_tree* left;
- avl_tree* right;
- factor balance;
- void setBalance(factor b) {balance = b;}
- factor getBalance() const {return balance;}
- };
- avl_tree* root;
- void left_balance(avl_tree* &sub_root);
- void right_balance(avl_tree* &sub_root);
- void rotate_left(avl_tree* &sub_root);
- void rotate_right(avl_tree* &sub_root);
- public:
- AVL_Tree() {root = NULL;}
- void insert(avl_tree* &sub_root, const int& data, bool& taller);
- avl_tree* &getRoot() {return root;}
- void preOrder(avl_tree* sub_root);
- };
- void AVL_Tree::insert(avl_tree* &sub_root, const int& data, bool& taller) {
- if (sub_root == NULL) {
- sub_root = new avl_tree();
- sub_root -> data = data;
- sub_root -> left = NULL;
- sub_root -> right = NULL;
- sub_root -> balance = equal_height;
- taller = true;
- } else if (data < sub_root -> data) {
- insert(sub_root -> left, data, taller);
- if (taller) {
- switch (sub_root -> getBalance()) {
- case left_height:
- left_balance(sub_root);
- taller = false;
- break;
- case equal_height:
- sub_root -> setBalance(left_height);
- break;
- case right_height:
- sub_root -> setBalance(equal_height);
- taller = false;
- break;
- }
- }
- } else {
- insert(sub_root -> right, data, taller);
- if (taller) {
- switch (sub_root -> getBalance()) {
- case left_height:
- sub_root -> setBalance(equal_height);
- taller = false;
- break;
- case equal_height:
- sub_root -> setBalance(right_height);
- break;
- case right_height:
- right_balance(sub_root);
- taller = false;
- break;
- }
- }
- }
- }
- void AVL_Tree::left_balance(avl_tree* &sub_root) {
- avl_tree* &left_tree = sub_root -> left;
- switch (left_tree -> getBalance()) {
- case left_height:
- sub_root -> setBalance(equal_height);
- left_tree -> setBalance(equal_height);
- rotate_right(sub_root);
- break;
- case right_height:
- avl_tree* &sub_tree = left_tree -> right;
- switch (sub_tree -> getBalance()) {
- case equal_height:
- sub_root -> setBalance(equal_height);
- left_tree -> setBalance(equal_height);
- break;
- case right_height:
- sub_root -> setBalance(equal_height);
- left_tree -> setBalance(left_height);
- break;
- case left_height:
- sub_root -> setBalance(right_height);
- left_tree -> setBalance(equal_height);
- break;
- }
- sub_tree -> setBalance(equal_height);
- rotate_left(left_tree);
- rotate_right(sub_root);
- break;
- }
- }
- void AVL_Tree::right_balance(avl_tree* &sub_root) {
- avl_tree* &right_tree = sub_root -> right;
- switch (right_tree -> getBalance()) {
- case right_height:
- sub_root -> setBalance(equal_height);
- right_tree -> setBalance(equal_height);
- rotate_left(sub_root);
- break;
- case left_height:
- avl_tree* &sub_tree = right_tree -> left;
- switch (sub_tree -> getBalance()) {
- case equal_height:
- sub_root -> setBalance(equal_height);
- right_tree -> setBalance(equal_height);
- break;
- case left_height:
- sub_root -> setBalance(equal_height);
- right_tree -> setBalance(right_height);
- break;
- case right_height:
- sub_root -> setBalance(left_height);
- right_tree -> setBalance(equal_height);
- break;
- }
- sub_tree -> setBalance(equal_height);
- rotate_right(right_tree);
- rotate_left(sub_root);
- break;
- }
- }
- void AVL_Tree::rotate_left(avl_tree* &sub_root) {
- avl_tree* right_tree = sub_root -> right;
- sub_root -> right = right_tree -> left;
- right_tree -> left = sub_root;
- sub_root = right_tree;
- }
- void AVL_Tree::rotate_right(avl_tree* &sub_root) {
- avl_tree* left_tree = sub_root -> left;
- sub_root -> left = left_tree -> right;
- left_tree -> right = sub_root;
- sub_root = left_tree;
- }
- void AVL_Tree::preOrder(avl_tree* sub_root) {
- if (sub_root != NULL) {
- cout << sub_root -> data << ' ';
- preOrder(sub_root -> left);
- preOrder(sub_root -> right);
- }
- }
- int main(int argc, char* argv[]) {
- int t;
- cin >> t;
- while (t--) {
- int num, temp;
- AVL_Tree t;
- cin >> num;
- for (int i = 0; i < num; ++i) {
- bool taller = false;
- cin >> temp;
- t.insert(t.getRoot(), temp, taller);
- }
- t.preOrder(t.getRoot());
- cout << endl;
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/020720149870.html
来源: http://www.codesnippet.cn/detail/020720149870.html