AVL-tree.zip_AVL高效实现_avl 旋转_二叉树旋转_树 旋转

#include"AVL_tree.h" template<class Record> Error_code AVL_tree<Record>::insert(const Record &new_data) { bool taller=true; return avl_insert(root, new_data, taller); } template<class Record> Error_code AVL_tree<Record>::remove(Record &old_data) { bool shorter=true; return avl_remove(root, old_data, shorter); } template<class Record> Error_code AVL_tree<Record>::avl_insert(Binary_node<Record> * &sub_root, const Record &new_data, bool &taller) { Error_code result=success; if(sub_root==NULL) { sub_root=new AVL_node<Record>(new_data); taller=true; } else if(sub_root->data==new_data) { result=duplicate_error; taller=false; } else if(sub_root->data > new_data) { result=avl_insert(sub_root->left, new_data, taller); if(taller==true) { switch ( sub_root->get_balance() ) { case equal_height: sub_root->set_balance(left_higher); break; case left_higher: left_balance(sub_root); taller=false;//进行旋转后，左右子树高度差又为1，即高度未改变 break; case right_higher: sub_root->set_balance(equal_height); taller=false; break; } } } else { result=avl_insert(sub_root->right, new_data, taller); if(taller==true) { switch( sub_root->get_balance() ) { case equal_height: sub_root->set_balance(right_higher); break; case left_higher: sub_root->set_balance(equal_height); taller=false; break; case right_higher: right_balance(sub_root); taller=false; break; } } } return result; } template<class Record> void AVL_tree<Record>::rotate_left(Binary_node<Record> * &sub_root) { if(sub_root==NULL || sub_root->right==NULL) cout<<"WARNING: program error detected in rotate left."<<endl; else { Binary_node<Record> *right_tree=sub_root->right; sub_root->right=right_tree->left; right_tree->left=sub_root; sub_root=right_tree; } } template<class Record> void AVL_tree<Record>::rotate_right(Binary_node<Record> * &sub_root) { if(sub_root==NULL || sub_root->left==NULL) cout<<"WARNING: program error detected in rotate right."<<endl; else { Binary_node<Record> * left_tree=sub_root->left; sub_root->left=left_tree->right; left_tree->right=sub_root; sub_root=left_tree; } } template<class Record> void AVL_tree<Record>::left_balance(Binary_node<Record> * &sub_root) { Binary_node<Record> *left_tree=sub_root->left; switch( left_tree->get_balance() ) { case equal_height: //impossible cout<<"WARNING: program error in left balance."<<endl; break; case left_higher: sub_root->set_balance(equal_height); left_tree->set_balance(equal_height); rotate_right(sub_root); break; case right_higher: Binary_node<Record> *sub_tree=left_tree->right; switch( sub_tree->get_balance() ) { case equal_height: sub_root->set_balance(equal_height); left_tree->set_balance(equal_height); break; case left_higher: sub_root->set_balance(right_higher); left_tree->set_balance(equal_height); break; case right_higher: sub_root->set_balance(equal_height); left_tree->set_balance(left_higher); break; } sub_tree->set_balance(equal_height); rotate_left(left_tree); rotate_right(sub_root); break; } } template<class Record> void AVL_tree<Record>::right_balance(Binary_node<Record> * &sub_root) { Binary_node<Record> *right_tree=sub_root->right; switch( right_tree->get_balance() ) { case equal_height: cout<<"WARNING: program error in right balance."<<endl; break; case right_higher: right_tree->set_balance(equal_height); sub_root->set_balance(equal_height); rotate_left(sub_root); break; case left_higher: Binary_node<Record> *sub_tree=right_tree->left; switch( sub_tree->get_balance() ) { case equal_height: sub_root->set_balance(equal_height); right_tree->set_balance(equal_height); break; case left_higher: sub_root->set_balance(equal_height); right_tree->set_balance(right_higher); break; case right_higher: sub_root->set_balance(left_higher); right_tree->set_balance(equal_height); break; } sub_tree->set_balance(equal_height); rotate_right(right_tree); rotate_left(sub_root); break; } } template<class Record> Error_code AVL_tree<Record>::avl_remove(Binary_node<Record> * &sub_root, const Record &new_data, bool &shorter) { Error_code result=success; Record sub_record; if(sub_root==NULL) { shorter=false; result=not_present; } else if(sub_root->data==new_data) { Binary_node<Record> * to_delete=sub_root; if(to_delete->left==NULL) { sub_root=sub_root->right; shorter=true; delete to_delete; } else if(to_delete->right==NULL) { sub_root=sub_root->left; shorter=true; delete to_delete; } else { Binary_node<Record> *parent=sub_root; to_delete=to_delete->left; while(to_delete->right!=NULL) { parent=to_delete; to_delete=to_delete->right; } //sub_record=new_data; sub_root->data=to_delete->data; if(parent==sub_root) parent->left=to_delete->left; else parent->right=to_delete->left; delete to_delete; } switch( sub_root->get_balance() ) { case equal_height: sub_root->set_balance(right_higher); break; case left_higher: sub_root->set_balance(equal_height); break; case right_higher: shorter=right_balance2(sub_root); break; } } else if(sub_root->data > new_data) { avl_remove(sub_root->left, new_data, shorter); //if(sub_record.the_key()!=0) sub_root->data = sub_record; if(shorter==true) switch( sub_root->get_balance() ) { case equal_height: sub_root->set_balance(right_higher); shorter=false; break; case left_higher: sub_root->set_balance(equal_height); break; case right_higher: shorter=right_balance2(sub_root); break; } } else { avl_remove(sub_root->right, new_data, shorter); //if(sub_record.the_key()!=0) sub_root->data = sub_record; if (shorter == true) switch ( sub_root->get_balance() ) { case equal_height: sub_root->set_balance(left_higher); shorter=false; break; case left_higher: shorter=left_balance2(sub_root); break; case right_higher: sub_root->set_balance(equal_height); break; } } return result; } template<class Record> bool AVL_tree<Record>::left_balance2(Binary_node<Record> * &sub_root) { bool shorter; Binary_node<Record> * &left_tree=sub_root->left; switch( left_tree->get_balance() ) { case equal_height: left_tree->set_balance(left_higher); rotate_right(sub_root); shorter=false; break; case left_higher: sub_root->set_balance(equal_height); left_tree->set_balance(equal_height); rotate_right(sub_root); shorter=true; break; case right_higher: Binary_node<Record> *sub_tree=left_tree->right; switch( sub_tree->get_balance() ) { case equal_height: left_tree->set_balance(equal_height); sub_root->set_balance(equal_height); break; case left_higher: left_tree->set_balance(equal_height); sub_root->set_balance(right_higher); break; case right_higher: left_tree->set_balance(left_higher); sub_root->set_balance(equal_height); break; } sub_tree->set_balance(equal_height); rotate_left(left_tree); rotate_right(sub_root); shorter=true; break; } return shorter; } template<class Record> bool AVL_tree<Record>::right_balance2(Binary_node<Record> * &sub_root) { bool shorter; Binary_node<Record> * &right_tree = sub_root->right; switch (right_tree->get_balance()) { case right_higher: sub_root->set_balance(equal_height); right_tree->set_balance(equal_height); rotate_left(sub_root); shorter = true; break; case equal_height: right_tree->set_balance(left_higher); rotate_left(sub_root); shorter = false; break; case left_higher: