AVL树的概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年
发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
节点的平衡因子=右子树的高度-左子树的高度
例如：
下图的二叉搜索树的每个节点的平衡因子的 绝对值都小于2，并且每个节点的子树也都是AVL树
AVL树的定义
AVL树是一种特殊的二叉搜索树，它具有高度的平衡，所以为了在插入过程中的各个节点的平衡因子的更新，我们在定义AVL树的节点结构的同时要带上一个节点的双亲结点parent
template<class T> struct AVLTreeNode { AVLTreeNode(const T& data) : _left(nullptr), _right(nullptr), _parent(nullptr) , _data(data), _bf(0) {} AVLTreeNode<T>* _left; // 该节点的左孩子 AVLTreeNode<T>* _right; // 该节点的右孩子 AVLTreeNode<T>* _parent; // 该节点的双亲 T _data; int _bf; // 该节点的平衡因子 };
AVL树的插入
AVL树的插入是一个难点，它分为好几种情况，其实AVL树的插入也就是在二叉搜索树中插入新节点，但是由于他引入了平衡因子，需要更新，所以这里的插入节点就比较麻烦，她一共分为两步：
1 插入节点
2 更新节点的平衡因子
为什么要更新节点的平衡因子呢？
简单地举个例子：
如图所示，我将一个新节点插入0的左孩子节点的位置，那么以3为节点的这颗子树的高度差不就会超过1了吗，他的左子树的高度插入新节点后为3，而右子树为1，这就不符合AVL树的性质了，所以我们需要经过一些操作来更新平衡因子
这里大家需要注意一个规则：
新节点如果是插入后他的parent的左侧，那么他的平衡因子默认是+1
反之插入他的右侧就是默认-1
那么在插入节点后，各个插入节点的parent一共就有三种情况了：
平衡因子为0
如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功
平衡因子为正负1
如果parent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更新成正负1，此时以parent为根的树的高度增加，需要继续向上更新，防止部分节点的左右子树高度差超过1
平衡因子为正负2
如果parent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进行旋转处理，旋转处理之后插入成功
至于旋转的情况我们待会分析，我们先将插入节点的代码的主要框架构造出来：
这样一个简单的框架就构造出来了
template<class T> struct AVLTreeNode { AVLTreeNode<T>* _left; // 该节点的左孩子 AVLTreeNode<T>* _right; // 该节点的右孩子 AVLTreeNode<T>* _parent; // 该节点的双亲 T _data; int _bf; // 该节点的平衡因子 AVLTreeNode(const T& data) : _left(nullptr), _right(nullptr), _parent(nullptr) , _data(data), _bf(0) {} }; template<class T> class AVLTree { typedef AVLTreeNode<T> Node; public: bool insert(const T& data) { if (_root == nullptr) { _root = new Node(data); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_data < data) { parent = cur; cur = cur->_right; } else if (cur->_data > data) { parent = cur; cur = cur->_left; } else { return false; } cur = new Node(data); if (parent->_data > data) { parent->_left = cur; } else { parent->_right = cur; } while (parent) { //左边++ if (cur == parent->_left) { parent->_bf--; } //右边-- else { parent->_bf++; } //parent的平衡因子等于0，插入成功 if (parent->_bf == 0) { break; } //parent的平衡因子等于1或者-1，继续向上更新 else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { //需要进行旋转 } else { assert(false); } } } } private: Node* _root; };
下面我们就具体分析几种旋转的情况
AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：
1. 新节点插入较高左子树的左侧—左左：右单旋
下图中的h可以时0 1 2三种，分别代表了这三个子树的高度，无论他是等于0 1 还是2时他们都可以满足AVL树的要求
可以看到，这种情况就是parent的平衡因子等于-2，cur的平衡因子等于-1
左旋函数如下：
void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; //防止sublr为空 if(subLR) subLR->_parent = parent; //记录祖父位置 Node* pparent = parent->_parent; subL->_right = parent; parent->_parent = subL; //如果父亲是根节点 if (parent == _root) { _root = subL; subL->_parent = nullptr; } //parent不是根节点，那么祖父就会成为subl的parent else { if (pparent->_left == parent) { pparent->_left = subL; subL->_parent = pparent; } else { pparent->_right = subL; subL->_parent = pparent; } } //旋转后parent和subl的 平衡因子都会更新为0 parent->_bf = subL->_bf = 0; }
2. 新节点插入较高右子树的右侧—右右：左单旋
实现及情况考虑可参考右单旋。
void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; subR->_left = parent; Node* pparent = parent->_parent; if (subRL) subRL->_parent = parent; if (_root == parent) { _root = subR; subR->_parent == nullptr; } else { if (pparent->_left == parent) { pparent->_left = subR; subR->_parent = pparent; } else { pparent->_right = subR; subR->_parent = pparent; } } parent->_bf = subR->_bf = 0; }
3. 新节点插入较高左子树的右侧—左右：先左单旋再右单旋
将双旋变成单旋后再旋转，即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再考虑平衡因子的更新。
直接复用即可：
由于博主能力有限，所以放入代码大家仔细理解
void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; RotateL(parent->_left); RotateR(parent); int bf = subLR->_bf; //sublr就是新增节点 if (bf == 0) { parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } //sublr左子树新增节点 else if (bf == -1) { parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } //sublr右子树新增节点 else if (bf == 1) { parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; } else { assert(false); } }
4. 新节点插入较高右子树的左侧—右左：先右单旋再左单旋
void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent->_right); RotateL(parent); //subrl这个点为新增点 if (bf == 0) { parent->_bf = subR->_bf = subRL->_bf = 0; } //subrl的左子树新增 else if (bf == -1) { parent->_bf = 0; subRL->_bf = 0; subR->_bf = 1; } //subrl的右子树新增 else if (bf == 1) { parent->_bf = -1; subRL->_bf = 0; subR->_bf = 0; } else { assert(false); } }
根据各种情况我们做了总结：
假如以parent为根的子树不平衡，即parent的平衡因子为2或者-2，分以下情况考虑
- parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR，当subR的平衡因子为1时，执行左单旋当subR的平衡因子为-1时，执行右左双旋
- parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL，当subL的平衡因子为-1是，执行右单旋，当subL的平衡因子为1时，执行左右双旋旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新。
所以我们可以补全上面的插入节点的代码了：
bool insert(const T& data) { if (_root == nullptr) { _root = new Node(data); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_data < data) { parent = cur; cur = cur->_right; } else if (cur->_data > data) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(data); if (parent->_data > data) { parent->_left = cur; } else { parent->_right = cur; } while (parent) { //左边++ if (cur == parent->_left) { parent->_bf--; } //右边-- else { parent->_bf++; } //parent的平衡因子等于0，插入成功 if (parent->_bf == 0) { break; } //parent的平衡因子等于1或者-1，继续向上更新 else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { //需要进行旋转 if (parent->_bf == 2 && cur->_bf == 1) { RotateL(parent); } else if (parent->_bf == 2 && cur->_bf == -1) { RotateRL(parent); } else if (parent->_bf == -2 && cur->_bf == -1) { RotateR(parent); } else if (parent->_bf == -2 && cur->_bf == 1) { RotateLR(parent); } break; } else { assert(false); } } return true; }
AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：
1. 验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
2. 验证其为平衡树每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)节点的平衡因子是否计算正确
我们可以用一个函数来判断即可：
首先要有一个计算树的高度的函数
然后判断他们的子树的高度差的绝对值是否在2以内，并且他们的子树也要是AVL树
int Height(Node* root) { if (root == nullptr) { return 0; } int leftheight = Height(root->_left); int rightheight = Height(root->_right); return leftheight > rightheight ? leftheight + 1 : rightheight + 1; } bool isbalance() { return _isbalance(_root); } bool _isbalance(Node* root) { if (root == nullptr) return true; int leftheight = Height(root->_left); int rightheight = Height(root->_right); if (rightheight - leftheight != root->_bf) { cout << root->_data << "平衡因子异常" << endl; return false; } return abs(rightheight - leftheight) < 2 && _isbalance(root->_left) && _isbalance(root->_right); }
我们还可以用中序遍历打印：
void inorder() { _inorder(_root); cout << endl; } void _inorder(Node* root) { if (root == nullptr) { return; } _inorder(root->_left); cout << root->_data << " "; _inorder(root->_right); }
完整代码如下：
#include<iostream> #include<assert.h> using namespace std; template<class T> struct AVLTreeNode { AVLTreeNode<T>* _left; // 该节点的左孩子 AVLTreeNode<T>* _right; // 该节点的右孩子 AVLTreeNode<T>* _parent; // 该节点的双亲 T _data; int _bf; // 该节点的平衡因子 AVLTreeNode(const T& data) : _left(nullptr), _right(nullptr), _parent(nullptr) , _data(data), _bf(0) {} }; template<class T> class AVLTree { typedef AVLTreeNode<T> Node; public: bool insert(const T& data) { if (_root == nullptr) { _root = new Node(data); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_data < data) { parent = cur; cur = cur->_right; } else if (cur->_data > data) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(data); if (parent->_data > data) { parent->_left = cur; } else { parent->_right = cur; } while (parent) { //左边++ if (cur == parent->_left) { parent->_bf--; } //右边-- else { parent->_bf++; } //parent的平衡因子等于0，插入成功 if (parent->_bf == 0) { break; } //parent的平衡因子等于1或者-1，继续向上更新 else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { //需要进行旋转 if (parent->_bf == 2 && cur->_bf == 1) { RotateL(parent); } else if (parent->_bf == 2 && cur->_bf == -1) { RotateRL(parent); } else if (parent->_bf == -2 && cur->_bf == -1) { RotateR(parent); } else if (parent->_bf == -2 && cur->_bf == 1) { RotateLR(parent); } break; } else { assert(false); } } return true; } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; //防止sublr为空 if(subLR) subLR->_parent = parent; //记录祖父位置 Node* pparent = parent->_parent; subL->_right = parent; parent->_parent = subL; //如果父亲是根节点 if (parent == _root) { _root = subL; subL->_parent = nullptr; } //parent不是根节点，那么祖父就会成为subl的parent else { if (pparent->_left == parent) { pparent->_left = subL; subL->_parent = pparent; } else { pparent->_right = subL; subL->_parent = pparent; } } //旋转后parent和subl的 平衡因子都会更新为0 parent->_bf = subL->_bf = 0; } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; subR->_left = parent; Node* pparent = parent->_parent; if (subRL) subRL->_parent = parent; if (_root == parent) { _root = subR; subR->_parent == nullptr; } else { if (pparent->_left == parent) { pparent->_left = subR; subR->_parent = pparent; } else { pparent->_right = subR; subR->_parent = pparent; } } parent->_bf = subR->_bf = 0; } void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; RotateL(parent->_left); RotateR(parent); int bf = subLR->_bf; //sublr就是新增节点 if (bf == 0) { parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } //sublr左子树新增节点 else if (bf == -1) { parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } //sublr右子树新增节点 else if (bf == 1) { parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; } else { assert(false); } } void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent->_right); RotateL(parent); //subrl这个点为新增点 if (bf == 0) { parent->_bf = subR->_bf = subRL->_bf = 0; } //subrl的左子树新增 else if (bf == -1) { parent->_bf = 0; subRL->_bf = 0; subR->_bf = 1; } //subrl的右子树新增 else if (bf == 1) { parent->_bf = -1; subRL->_bf = 0; subR->_bf = 0; } else { assert(false); } } int Height(Node* root) { if (root == nullptr) { return 0; } int leftheight = Height(root->_left); int rightheight = Height(root->_right); return leftheight > rightheight ? leftheight + 1 : rightheight + 1; } bool isbalance() { return _isbalance(_root); } bool _isbalance(Node* root) { if (root == nullptr) return true; int leftheight = Height(root->_left); int rightheight = Height(root->_right); if (rightheight - leftheight != root->_bf) { cout << root->_data << "平衡因子异常" << endl; return false; } return abs(rightheight - leftheight) < 2 && _isbalance(root->_left) && _isbalance(root->_right); } void inorder() { _inorder(_root); cout << endl; } void _inorder(Node* root) { if (root == nullptr) { return; } _inorder(root->_left); cout << root->_data << " "; _inorder(root->_right); } private: Node* _root=nullptr; };
好了，今天的分享到这里就结束了，感谢大家的支持！
