C++ AVL树

1.概念

二叉搜索树虽可以缩短查找的效率，但 如果数据有序或接近有序二叉搜索树将退化为单支树，查

找元素相当于在顺序表中搜索元素，效率低下 。因此，两位俄罗斯的数学家 G.M.Adelson-Velskii

和 E.M.Landis 在 1962 年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右 子树高度之差的绝对值不超过 1( 需要对树中的结点进行调整 ) ，即可降低树的高度，从而减少平均搜索长度。

一棵 AVL 树或者是空树，或者是具有以下性质的二叉搜索树：

1. 它的左右子树都是 AVL 树

2. 左右子树高度之差 ( 简称平衡因子 ) 的绝对值不超过 1(-1/0/1)

如果一棵二叉搜索树是高度平衡，它就是 AVL 树。如果它有 n 个结点，其高度可保持在 O( $\log_{2}n$ )，搜索时间复杂度O( $\log_{2}n$ )。

2.AVL树节点的定义

template <class K, class V>//结点struct AVLTreeNode{//构造函数AVLTreeNode(const pair<K,V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv){}//成员变量AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;int _bf;//平衡因子pair<K, V> _kv;//节点数据};

3.AVL树的构造函数

//构造函数AVLTree():_root(nullptr){}//析构函数void _Destroy(Node* root){if (root == nullptr){return;}_Destroy(root->_left);_Destroy(root->_right);delete root;}~AVLTree(){_Destroy(_root);_root = nullptr;}

4. AVL树的插入

我们规定平衡因子_bf为右子树的高度减去左子树的高度，且平衡因子_bf的取值范围为-1到1，则一颗树有如下平衡因子为0，1，-1的三种情况。

旋转要保持的要求：
1.旋转后也是搜索二叉树。
2.变成平衡树并且降低树的高度。

右单旋

我们在subL节点的左子树插入了一个节点，导致parent失衡，接着我们就要尝试调整节点，让这棵树平衡。

由于subL的右子树subLR高度为h-1，而parent的右子树高度也为h-1，此时我们可以想办法把这两个h-1的等高子树凑到一起去，于是我们把parent的左子树断开，把subL的右子树拿去给parent做左子树，此时parent就得到了等高的两棵子树。也就是第二张图片的情况。随后，以parent为根的树，总高度为h，而subL的左子树刚好高度也是h-1+1 = h，所以我们可以把parent交给subL做子树，这样subL的两边也就平衡了。而刚刚我们把subL的右子树空出来了，此时可以直接转移，就得到了第三种图片的情况。

这个情况下，我们以subL为根的树是一颗平衡的树，而且平衡因子为0，插入节点前以parent为根的子树，高度为h+1，插入节点且旋转后高度仍为h+1。插入前后高度不变，不会影响父节点，直接跳出循环。

//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* grandparent = parent->_parent;parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;}else{if (grandparent->_left == parent)grandparent->_left = subL;elsegrandparent->_right = subL;}subL->_parent = grandparent;//调整平衡因子parent->_bf = subL->_bf = 0;}

左单旋

左单旋与右单旋同理

//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* grandparent = parent->_parent;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;}else{if (grandparent->_left == parent)grandparent->_left = subR;elsegrandparent->_right = subR;}subR->_parent = grandparent;//调整平衡因子parent->_bf = subR->_bf = 0;}

左右双旋

当出现图一这种插入情况时，又要将该情况分为图二和图三两种情况，也就是对subLR进行了再细分，到底新节点插入了左子树还是右子树。

在subLR的左子树插入后旋转，调整后 parent的平衡因子：1， subL 的平衡因子：0 ， subLR的平衡因子：0
在这里插入图片描述

在subLR的右子树插入后旋转，调整后 parent的平衡因子：0， subL 的平衡因子：-1， subLR的平衡因子：0
在这里插入图片描述

//左右双旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}}

右左双旋

在subRL的左子树插入后旋转，调整后 parent的平衡因子：0， subR 的平衡因子：0 ， subRL的平衡因子：1

在subRL的右子树插入后旋转，调整后 parent的平衡因子：-1， subR 的平衡因子：0 ， subRL的平衡因子：0

//右左双旋void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = parent->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}}

完整的插入代码

		//插入pair<Node*, bool> Insert(const pair<K, V>& kv){//在第一个位置插入if (_root == nullptr){_root = new Node(kv);return pair<Node*, bool>(_root, true);}Node* cur = _root, * parent = _root;while (cur){if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{//已经存在不插入return pair<Node*, bool>(cur, false);}}//创建新结点连接cur = new Node(kv);cur->_parent = parent;if (kv.first < parent->_kv.first)parent->_left = cur;elseparent->_right = cur;Node* ret = cur;//更新平衡因子while (cur != _root){if (cur == parent->_right)parent->_bf++;elseparent->_bf--;if (parent->_bf == 0){break;}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){//左单旋if (cur->_bf == 1)RotateL(parent);//右左双旋else if (cur->_bf == -1)RotateRL(parent);}else if (parent->_bf == -2){//右单旋if (cur->_bf == -1)RotateR(parent);//左右双旋else if (cur->_bf == 1)RotateLR(parent);}break;}}return pair<Node*, bool>(ret, true);}

5. 重载AVL树的[ ]

		//重载[]V& operator[](const K& key){pair<Node*, bool> ret = Insert(make_pair(key,V()));return ret.first->_kv.second;}

6. AVL树的判定

		//判断是否为AVLTree//要求左右子树的高度差小于等于1，且等于其平衡因子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 _IsAVLTree(Node* root){if (root == nullptr){return true;}int LeftHeight = Height(root->_left);int RightHeight = Height(root->_right);if (RightHeight - LeftHeight!=root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return abs(LeftHeight - RightHeight) < 2 &&_IsAVLTree(root->_left) && _IsAVLTree(root->_right);}bool IsAVLTree(){return _IsAVLTree(_root);}

7. AVL树的完整代码

#include <iostream>
#include <vector>
using namespace std;
namespace lbk
{template <class K, class V>//结点struct AVLTreeNode{//构造函数AVLTreeNode(const pair<K,V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv){}//成员变量AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;int _bf;//平衡因子pair<K, V> _kv;//节点数据};template <class K, class V>class AVLTree{typedef AVLTreeNode<K, V> Node;//成员变量Node* _root;public://构造函数AVLTree():_root(nullptr){}//析构函数void _Destroy(Node* root){if (root == nullptr){return;}_Destroy(root->_left);_Destroy(root->_right);delete root;}~AVLTree(){_Destroy(_root);_root = nullptr;}Node* Find(const K& key){Node* cur = _root;while (cur){if (key < cur->_kv.first)cur = cur->_left;else if (key > cur->_kv.first)cur = cur->_right;elsereturn cur;}return nullptr;}//重载[]V& operator[](const K& key){pair<Node*, bool> ret = Insert(make_pair(key,V()));return ret.first->_kv.second;}//判断是否为AVLTree//要求左右子树的高度差小于等于1，且等于其平衡因子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 _IsAVLTree(Node* root){if (root == nullptr){return true;}int LeftHeight = Height(root->_left);int RightHeight = Height(root->_right);if (RightHeight - LeftHeight!=root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return abs(LeftHeight - RightHeight) < 2 &&_IsAVLTree(root->_left) && _IsAVLTree(root->_right);}bool IsAVLTree(){return _IsAVLTree(_root);}//中序遍历void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}void InOrder(){_InOrder(_root);cout << endl;}//插入pair<Node*, bool> Insert(const pair<K, V>& kv){//在第一个位置插入if (_root == nullptr){_root = new Node(kv);return pair<Node*, bool>(_root, true);}Node* cur = _root, * parent = _root;while (cur){if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{//已经存在不插入return pair<Node*, bool>(cur, false);}}//创建新结点连接cur = new Node(kv);cur->_parent = parent;if (kv.first < parent->_kv.first)parent->_left = cur;elseparent->_right = cur;Node* ret = cur;//更新平衡因子while (cur != _root){if (cur == parent->_right)parent->_bf++;elseparent->_bf--;if (parent->_bf == 0){break;}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){//左单旋if (cur->_bf == 1)RotateL(parent);//右左双旋else if (cur->_bf == -1)RotateRL(parent);}else if (parent->_bf == -2){//右单旋if (cur->_bf == -1)RotateR(parent);//左右双旋else if (cur->_bf == 1)RotateLR(parent);}break;}}return pair<Node*, bool>(ret, true);}private://左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* grandparent = parent->_parent;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;}else{if (grandparent->_left == parent)grandparent->_left = subR;elsegrandparent->_right = subR;}subR->_parent = grandparent;//调整平衡因子parent->_bf = subR->_bf = 0;}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* grandparent = parent->_parent;parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;}else{if (grandparent->_left == parent)grandparent->_left = subL;elsegrandparent->_right = subL;}subL->_parent = grandparent;//调整平衡因子parent->_bf = subL->_bf = 0;}//左右双旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}}//右左双旋void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = parent->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}}};
}