什么是AVL树？AVL树的插入，旋转及验证（代码实现）

前文说到了二叉搜索树一般情况下有很高的查找效率，平均时间复杂度为O(logN)，N为树中的全部节点数。但是二叉搜索树也有缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，这就很不稳定了。那么有没有更好的二叉搜索树呢？

一、什么是AVL树

两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发表了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次旋转节点来重新平衡这个树。 一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树： （1）它的左右子树都是AVL树 （2）左右子树高度之差(简称平衡因子)的绝对值不大于1(-1/0/1)

二、AVL树的实现（插入，旋转，验证）

代码如下：

#include<iostream> #include<assert.h> using namespace std; template <class T> struct AVLNode { AVLNode<T>* left; AVLNode<T>* right; AVLNode<T>* parent; T _val; int bf; //平衡因子 AVLNode(const T& val) :left(nullptr) , right(nullptr) , parent(nullptr) , _val(val) , bf(0) {} }; template <class T> class AVLTree { public: typedef AVLNode<T> Node; typedef Node* pNode; void RotateL(pNode parent) { pNode subR = parent->right; pNode subRL = subR->left; subR->left = parent; parent->right = subRL; if (subRL) subRL->parent = parent; //如果parent不是根节点,那么它肯定还有父亲 if (parent != root) { pNode grandpa = parent->parent; if (grandpa->left == parent) grandpa->left = subR; else grandpa->right = subR; subR->parent = grandpa; } else { root = subR; subR->parent = nullptr; } parent->parent = subR; //更新平衡因子 parent->bf = subR->bf = 0; } void RotateR(pNode parent) { pNode subL = parent->left; pNode subLR = subL->right; subL->right = parent; parent->left = subLR; if (subLR) subLR->parent = parent; if (parent != root) { pNode grandpa = parent->parent; if (grandpa->left == parent) grandpa->left = subL; else grandpa->right = subL; subL->parent = grandpa; } else { root = subL; subL->parent = nullptr; } parent->parent = subL; //更新平衡因子 parent->bf = subL->bf = 0; } bool insert(const T& val) { //空树 if (root == nullptr) { root = new Node(val); return true; } //搜索 pNode cur = root; pNode parent = nullptr; while (cur) { parent = cur; //更新父节点位置 if (cur->_val == val) return false; else if (cur->_val > val) cur = cur->left; else cur = cur->right; } cur = new Node(val); if (parent->_val > val) parent->left = cur; else parent->right = cur; cur->parent = parent; //插入完毕 //更新平衡因子 while (parent) { //如果插入节点在parent的左边,parent平衡因子-1;否则+1 if (parent->left == cur) --parent->bf; else ++parent->bf; //根据平衡因子情况决定执行什么操作 if (parent->bf == 0) //更新平衡因子后为0说明之前有一边被补齐,不会对上面造成影响,因此不用继续调整 break; else if (abs(parent->bf) == 1) { //继续向上更新 cur = parent; parent = parent->parent; } else if (abs(parent->bf) == 2) //此时需要进行旋转调整 { //单旋情况 if (parent->bf == 2 && cur->bf == 1) RotateL(parent); else if (parent->bf == -2 && cur->bf == -1) RotateR(parent); //双旋情况 else if (parent->bf == -2 && cur->bf == 1) { pNode subL = parent->left; pNode subLR = subL->right; int bf = subLR->bf; RotateL(cur); RotateR(parent); //更新parent,subL平衡因子 if (bf == 1) { parent->bf = 0; subL->bf = -1; } else if (bf == -1) { subL->bf = 0; parent->bf = 1; } } else if (parent->bf == 2 && cur->bf == -1) { pNode subR = parent->right; pNode subRL = subR->left; int bf = subRL->bf; RotateR(cur); RotateL(parent); if (bf == 1) { subR->bf = 0; parent->bf = -1; } else if (bf == -1) { subR->bf = 1; parent->bf = 0; } } break; } else { assert(false); } } return true; } void _inOrder(pNode root) { if (root) { _inOrder(root->left); cout << root->_val << " "; _inOrder(root->right); } } void inOrder() { _inOrder(root); cout << endl; } int height(pNode root) { if (root == nullptr) return 0; int leftHeight = height(root->left); int rightHeight = height(root->right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } bool _isAVLTree(pNode root) { if (root == nullptr) return true; //1.平衡因子绝对值不大于1 //2.平衡因子和左右子树的高度差要一致 int left = height(root->left); int right = height(root->right); if (right - left != root->bf) { cout << "节点" << root->_val << "平衡因子异常" << endl; return false; } return abs(root->bf) < 2 && _isAVLTree(root->left) && _isAVLTree(root->right); } bool isAVLTree() { return _isAVLTree(root); } private: pNode root = nullptr; };