概念
AVL树是一种自平衡的二叉查找树，其中任何结点的两个子树的高度最大差别为1，因此也被称为高度平衡树。AVL树的特点是在进行插入和删除操作后，会通过旋转的方式来重新平衡树的结构。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树；
- 左右子树高度差的绝对值不超过1（0、1、-1)
一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O ( l o g 2 n ) O(log_2 n)O(log2n)，搜索时间复杂度O(l o g 2 n log_2 nlog2n).
AVL树的结点定义
template<class K,class V> struct AVLTreeNode { AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; int _bf; pair<K, V> _kv; AVLTreeNode(const pair<K, V>& kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) ,_kv(kv) {} };
AVL树的插入
对于AVL树来说，操作和搜索二叉树差不多；
先判断插入结点的大小，找到合适的位置进行插入；
再对平衡因子进行调整。
bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; while (parent) { if (cur == parent->_left) { parent->_bf--; } else { parent->_bf++; } if (parent->_bf == 0) { break; } else if (parent->_bf == 1 || parent->_bf == -1) { cur = cur->_parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { //旋转处理 if (parent->_bf == 2 && cur->_bf == 1) { RoteteL(parent); } else if (parent->_bf == -2 && cur->_bf == -1) { RorareR(parent); } else if (parent->_bf == -2 && cur->_bf == 1) { RotateLR(parent); } else { RotateRL(parent); } break; } else { assert(false); } } }
AVL树的旋转
当插入一个结点时，可能会使原本的父节点的平衡因子失去平衡，这时，就需要通过调整，来进行重新平衡；主要有4种情况：
左单旋
void RoteteL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; subR->_left = parent; Node* ppnode = parent->_parent; parent->_parent = subR; if (ppnode) { if (ppnode->_left == parent) { ppnode->_left = subR; } else { ppnode->_right = subR; } subR->_parent = ppnode; } else { _root = subR; subR->_parent = __nullptr; } parent->_bf = 0; subR->_bf = 0; }
右单旋
void RorareR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; Node* ppnode = parent->_parent; parent->_parent = subL; if (parent == _root) { _root = subL; subL->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subL; } else { ppnode->_right = subL; } subL->_parent = ppnode; } subL->_bf = 0; parent->_bf = 0; }
左右旋
void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RoteteL(parent->_left); RorareR(parent); if (bf == -1) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 1; } else if (bf == 1) { subLR->_bf = 0; subL->_bf = -1; parent->_bf = 0; } else if (bf == 0) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 0; } else { assert(false); } }
右左旋
void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RorareR(subR); RoteteL(parent); if (bf == 1) { subRL->_bf = 0; subR->_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; } else { assert(false); } }
旋转验证
AVL树的验证
bool _IsBanlance(Node* root,int& height) { if (root == nullptr) { return true; } //计算左右子树高度差 int leftHeight = 0, rightHeight = 0; if (!_IsBanlance(root->_left, leftHeight) || !_IsBanlance(root->_right, rightHeight)) { return false; } if (abs(rightHeight - leftHeight) >= 2) { cout << "不平衡" << endl; return false; } if (rightHeight - leftHeight != root->_bf) { cout << "平衡因子异常" << endl; return false; } height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; return true; } bool IsBanlance() { int height = 0; return _IsBanlance(_root,height); }
观察验证：
AVL树的查找
AVL树的性能
AVL树的性能主要体现下面几个方面：
- 平衡性：AVL树保持了高度的平衡，即任何结点的两个子树的高度差不超过1.这就保证了树的深度相对较小，使得查找、插入、删除操作的平均时间复杂度为O（logN）；
- 查找操作：由于AVL树是搜索二叉树的变种，它具有搜索二叉树的性质，可以在O（logN）的时间复杂度内进行查找操作。
- 插入和删除操作：当进行插入或删除时，AVL树会根据需要进行平衡调整，以保持树的平衡性。则可能需要通过旋转来重新平衡树的结构。但这个旋转次数影响不大，插入和删除操作的时间复杂度为O（logN）；
- 内存消耗：AVL树相比于其他平衡二叉树（如红黑树）可能会消耗更多的内存空间，因为每个结点需要存储额外的平衡因子信息。平衡因子通常由一个整数表示；但在大多数应用场景中，AVL树的性能仍然是非常好的。
