【数据结构】AVL树insert接口实现

AVL树的插入接口需要分多种情况讨论&＃xff0c;
前提是依据插入后平衡因子的值来做调整&＃xff1a;

1.平衡因子为0&＃xff0c;结束调整&＃xff1b;
2.平衡因子为正负1&＃xff0c;继续向上调整&＃xff0c;直到0&＃xff1b;
3.平衡因子为正负2&＃xff0c;此时还需要进一步讨论&＃xff1a;

出现平衡因子±2比较复杂&＃xff0c;需要针对每一种情况做出不同旋转&＃xff1a;

3.1. pParent的平衡因子为2&＃xff0c;说明pParent的右子树高&＃xff0c;设pParent的右子树的根为pSubR
当pSubR的平衡因子为1时&＃xff0c;执行左单旋
当pSubR的平衡因子为-1时&＃xff0c;执行右左双旋
3.2. pParent的平衡因子为-2&＃xff0c;说明pParent的左子树高&＃xff0c;设pParent的左子树的根为pSubL
当pSubL的平衡因子为-1是&＃xff0c;执行右单旋
当pSubL的平衡因子为1时&＃xff0c;执行左右双旋
旋转完成后&＃xff0c;原pParent为根的子树个高度降低&＃xff0c;已经平衡&＃xff0c;不需要再向上更新。

#include
using namespace std;
template<class T>
//AVLTree节点
class AVLNode{
public://AVL数有3个节点指针&＃xff0c;1个val&＃xff0c;1个平衡因子int _bf;T _val;AVLNode<T>* _partent;AVLNode<T>* _left;AVLNode<T>* _right;AVLNode(const T& val &＃61; T())//类0值:_bf(0), _val(val), _partent(nullptr), _left(nullptr), _right(nullptr) {}
};
//AVLTree树
template<class T>
class AVLTree{
public:typedef AVLNode<T> Node;bool insert(const T& val){//先判断是否为空树if (_root &＃61;&＃61; nullptr){_root &＃61; new Node(val);return true;}Node* node&＃61;_root;Node* partent&＃61;nullptr;while (node){partent &＃61; node;if (node->_val &＃61;&＃61; val){return false;}else if (node->_val > val){node &＃61; node->_left;}else{node &＃61; node->_right;}}//此时node在空上,并且没有链接父节点node &＃61; new Node(val);//此时链接父节点if (partent->_val>val){partent->_left &＃61; node;}else{partent->_right &＃61; node;}node->_partent &＃61; partent;//开始调整bf//从partent开始while (partent){//先对父节点bf进行增或减if (partent->_left &＃61;&＃61; node)--partent->_bf;else&＃43;&＃43;partent->_bf;//根据调整后的bf操作//bf&＃61;&＃61;0&＃xff0c;结束调整//bf&＃61;&＃43;-1&＃xff0c;继续向上更新//bf&＃61;&＃43;-2&＃xff0c;需要旋转if (partent->_bf &＃61;&＃61; 0){break;}else if (partent->_bf &＃61;&＃61; 1 || partent->_bf &＃61;&＃61; -1){node &＃61; partent;partent &＃61; partent->_partent;}else if(abs(partent->_bf)&＃61;&＃61;2){if (node->_bf &＃61;&＃61; -1 && partent->_bf &＃61;&＃61; -2){//需要右旋RotateR(partent);}else if (node->_bf &＃61;&＃61; 1 && partent->_bf &＃61;&＃61; 2){RotateL(partent);}else if (partent->_bf &＃61;&＃61; 2 && node->_bf &＃61;&＃61; -1){Node* subRL &＃61; node->_left;int bf &＃61; subRL->_bf;RotateR(node);RotateL(partent);if (bf &＃61;&＃61; 1){partent->_bf &＃61; -1;node->_bf &＃61; 0;}else if (bf &＃61;&＃61; -1){node->_bf &＃61; 1;partent->_bf &＃61; 0;}}else if (partent->_bf &＃61;&＃61; -2 && node->_bf &＃61;&＃61; 1){Node* subLR &＃61; node->_right;int bf &＃61; subLR->_bf;RotateL(node);RotateR(partent);if (bf &＃61;&＃61; 1){partent->_bf &＃61; 0;node->_bf &＃61; -1;}else if (bf &＃61;&＃61; -1){node->_bf &＃61; 0;partent->_bf &＃61; 1;}}break;}}return true;}// partent subL//subL -> partent// subLR subLR void RotateR(Node* partent){Node* subL &＃61; partent->_left;Node* subLR &＃61; subL->_right;subL->_right &＃61; partent;partent->_left &＃61; subLR;if (subLR){subLR->_partent &＃61; partent;}//调整上部节点if (partent &＃61;&＃61; _root){_root &＃61; subL;subL->_partent &＃61; nullptr;}else{Node* pparent &＃61; partent->_partent;if (pparent->_left &＃61;&＃61; partent){pparent->_left &＃61; subL;}else{pparent->_right &＃61; subL;}subL->_partent &＃61; pparent;}partent->_partent &＃61; subL;subL->_bf &＃61; partent->_bf &＃61; 0;}//partent subR// subR -> partent// subRL subRL void RotateL(Node* partent){Node* subR &＃61; partent->_right;Node* subRL &＃61; subR->_left;subR->_left &＃61; partent;partent->_right &＃61; subRL;if (subRL){subRL->_partent &＃61; partent;}partent->_partent &＃61; subR;//调整上部节点if (partent &＃61;&＃61; _root){_root &＃61; subR;subR->_partent &＃61; nullptr;}else{Node* pparent &＃61; partent->_partent;if (pparent->_left &＃61;&＃61; partent){pparent->_left &＃61; subR;}else{pparent->_right &＃61; subR;}subR->_partent &＃61; pparent;}subR->_bf &＃61; partent->_bf &＃61; 0;}void _inorder(Node* root){if (root){_inorder(root->_left);cout << root->_val << " ";_inorder(root->_right);}}void inorder(){return _inorder(_root);}//检查AVL是否正确//查看节点长度int Height(Node* root){if (root &＃61;&＃61; nullptr){return 0;}int left &＃61; Height(root->_left);int right &＃61; Height(root->_right);return left > right ? left &＃43; 1 : right &＃43; 1;}bool _isbalance(Node* root){if (root &＃61;&＃61; nullptr){return true;}int left &＃61; Height(root->_left);int right &＃61; Height(root->_right);if (right - left !&＃61; root->_bf){cout << root->_val <<":错误"<< endl;return false;}return abs(root->_bf) < 2 && _isbalance(root->_left) && _isbalance(root->_right);}bool isbalance(){return _isbalance(_root);}
private://记得置空AVLNode<T>* _root&＃61;nullptr;};void test(){AVLTree<int> t;t.insert(5);t.insert(3);t.insert(1);t.insert(0);t.insert(2);t.insert(-1);t.insert(5);t.insert(1);t.inorder();cout << endl;cout<<t.isbalance();
}
int main(){test();system("pause");return 0;
}


通过校验&＃xff1a;