👉AVL树👈
AVL树的概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家
G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年
发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
AVL 树也称为高度平衡二叉搜索树，其满足以下性质：
它的左右子树都是 AVL 树（注：空树也是 AVL 树）
左右子树的高度差（简称平衡因子）的绝对值不超过 1（-1 / 0 / 1）（注：无法保证左右子树的高度差永远为 0）
平衡因子等于右子树高度减去左子树高度，平衡因子是非必须的，我们用的话方便实现 AVL 树。
如果一颗二叉搜索树是高度平衡的，它就是 AVL 树。如果它有 N 个节点，其高度可保持在O ( l o g 2 N ) ，查找和插入的时间复杂度为O(l o g 2 N ）
AVL树节点的定义
template <class K, class V> struct AVLTreeNode { AVLTreeNode<K, V>* _parent; // 父节点 AVLTreeNode<K, V>* _left; // 左孩子 AVLTreeNode<K, V>* _right; // 右孩子 pair<K, V> _kv; // 键值对 int _bf; // balance factor(平衡因子) AVLTreeNode(const pair<K, V>& kv) : _parent(nullptr) , _left(nullptr) , _right(nullptr) , _kv(kv) , _bf(0) {} };
AVL 树的节点是三叉链结构的，因为插入节点可能会影响父节点的平衡因子，有了指向父节点的指针会方便我们进行平衡因子的更新和旋转操作。新插入的节点的平衡因子都是 0。
AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子，因此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 // 树中已经存在Key { 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 (abs(parent->_bf) == 1) // 继续往上更新 { parent = parent->_parent; cur = cur->_parent; } else if (abs(parent->_bf) == 2) { // 说明parent所在的子树已经不平衡了,需要旋转处理 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) RotateLR(parent); else if (parent->_bf == 2 && cur->_bf == -1) RotateRL(parent); else // 理论上不会走到这里 assert(false); break; } else // 理论上不会走到这里 { assert(false); } } return true; }
AVL树的旋转
如果在一棵原本是平衡的 AVL 树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL 树的旋转分为四种：左单旋、右单旋、左右双旋和右左双旋。注：旋转操作可能对整棵树做，也可能对子树做。旋转的原则是：旋转成平衡数并且符合二叉搜索树的规则。一次插入，最多一次旋转。
节点插入在较高右子树的右侧时，需要左单旋
注：当parent->_bf == 2 && cur->_bf == 1时，此时需要对parent所在的子树进行左单旋。parent和subR不可能为空，subRL可能为空。更新subR的父指针是需要需要parent是否是根节点。
void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) // subRL不为空,其父指针且才能指向parent subRL->_parent = parent; // 记录parent的父亲 Node* ppNode = parent->_parent; subR->_left = parent; parent->_parent = subR; // parent就是根节点时,则需要将subR更新为根节点,subR的父指针指向nullptr if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { // 判断原父节点在左边还是右边 if (ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; subR->_parent = ppN ode; } // 更新平衡因子 parent->_bf = subR->_bf = 0; }
节点插入在较高左子树的左侧时，需要右单旋。右单旋和左单旋是一致的。
注：当parent->_bf == -2 && cur->_bf == -1时，此时需要对parent所在的子树进行右单旋。parent和subL不可能为空，subLR可能为空。更新subL的父指针是需要需要parent是否是根节点。
void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; // subLR不为空时,其父指针才能指向parent if (subLR) subLR->_parent = parent; Node* ppNode = parent->_parent; subL->_right = parent; parent->_parent = subL; // parent就是根节点时,则需要将subR更新为根节点,subR的父指针指向nullptr if (parent == _root) { _root = subL; subL->_parent = nullptr; } else { if (ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; subL->_parent = ppNode; } // 更新平衡因子 parent->_bf = subL->_bf = 0; }
节点插入在较高左子树的右侧时，需要左右双旋。当parent->_bf == -2 && cur->_bf == 1时，需要进行左右双旋：先对subL进行左单旋，再对parent进行右单旋。
// 左右双旋 void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; // 通过subLR的平衡因子来区分各种情况 int bf = subLR->_bf; // 先左单旋再右单旋 RotateL(subL); RotateR(parent); subLR->_bf = 0; if (bf == 1) // 在c插入新节点 { parent->_bf = 0; subL->_bf = -1; } else if (bf == 0) // 新增节点就是自己 { parent->_bf = 0; subL->_bf = 0; } else if (bf == -1) // 在b插入新节点 { parent->_bf = 1; subL->_bf = 0; } else // 理论上不会走到这里 { assert(false); } }
节点插入在较高右子树的左侧时，需要右左双旋。当parent->_bf == 2 && cur->_bf == -1时，需要进行左右双旋：先对subR进行右单旋，再对parent进行左单旋。
// 右左双旋 void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; // 通过subRL的平衡因子来区分各种情况 int bf = subRL->_bf; // 先右单旋再左单旋 RotateR(subR); RotateL(parent); subRL->_bf = 0; if (bf == 1) // 在c插入新节点 { parent->_bf = -1; subR->_bf = 0; } else if (bf == 0) // 新增节点是自己 { parent->_bf = 0; subR->_bf = 0; } else if (bf == -1) // 在b插入新节点 { parent->_bf = 0; subR->_bf = 1; } else // 理论不会走到这里 { assert(false); } }
总结： 假如以 pParent 为根的子树不平衡，即 pParent 的平衡因子为 2 或者 -2，分以下情况考虑：
pParent 的平衡因子为 2，说明 pParent 的右子树高，设 pParent 的右子树的根为 pSubR
当 pSubR 的平衡因子为 1 时，执行左单旋
当 pSubR 的平衡因子为 -1 时，执行右左双旋
pParent 的平衡因子为 -2，说明 pParent 的左子树高，设 pParent 的左子树的根为 pSubL
当 pSubL 的平衡因子为 -1 时，执行右单旋
当 pSubL 的平衡因子为 1 时，执行左右双旋
旋转完成后，原以 pParent 为根的子树个高度降低，已经平衡，不需要再向上更新。
现在已经将 AVL 树的旋转写完了，那么现在就来验证一下写得对不对。
AVL树的验证
AVL 树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证 AVL 树，可以分两步：1、验证其为二叉搜索树：如果中序遍历可得到一个有序的序列，就说明为二叉搜索树。2、验证其为平衡树：节点的平衡因子是否计算正确，每个节点子树高度差的绝对值不超过 1(注意节点中如果没有平衡因子)。
public: // 判断是否是平衡树 bool IsBalance() { return _IsBalance(_root); } // 中序遍历判断是否是二叉搜索树 void InOrder() { return _InOrder(_root); } private: // 求二叉树的高度 int Height(Node* parent) { if (parent == nullptr) return 0; return max(Height(parent->_left), Height(parent->_right)) + 1; } bool _IsBalance(Node* root) { if (root == nullptr) return true; int leftHeight = Height(root->_left); int rightHeight = Height(root->_right); int diff = rightHeight - leftHeight; return abs(diff) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right); } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); }
测试样例
void AVLTreeTest1() { size_t N = 1000; srand(time(nullptr)); AVLTree<int, int> t; for (size_t i = 0; i < N; ++i) { int x = rand(); t.Insert(make_pair(x, i)); } t.InOrder(); cout << endl; cout << "IsBalance:" << t.IsBalance() << endl; } void AVLTreeTest2() { int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; // 测试双旋平衡因子调节 //int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; AVLTree<int, int> t1; for (auto e : a) { t1.Insert(make_pair(e, e)); } t1.InOrder(); cout << "IsBalance:" << t1.IsBalance() << endl; }
AVL树的删除(了解)
因为 AVL 树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子。最差情况下，需要一直要更新到根节点的位置。
具体实现大家可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。
AVL树的性能
AVL 树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过 1，这样可以保证查找高效的时间复杂度，即 l o g 2 N log_2 Nlog
2
N。但是如果要对 AVL 树做一些结构修改的操作，性能非常低下。比如：插入时要维护其绝对平衡，旋转的次数比较多。更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑 AVL 树，但一个结构经常修改，就不太适合。
AVL树的完整代码
#pragma once template <class K, class V> struct AVLTreeNode { AVLTreeNode<K, V>* _parent; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; pair<K, V> _kv; int _bf; // balance factor AVLTreeNode(const pair<K, V>& kv) : _parent(nullptr) , _left(nullptr) , _right(nullptr) , _kv(kv) , _bf(0) {} }; template <class K, class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: 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 (abs(parent->_bf) == 1) { //cur = parent; //parent = parent->_parent; parent = parent->_parent; cur = cur->_parent; } else if (abs(parent->_bf) == 2) { // 说明parent所在的子树已经不平衡了,需要旋转处理 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) RotateLR(parent); else if (parent->_bf == 2 && cur->_bf == -1) RotateRL(parent); else assert(false); break; } else { assert(false); } } return true; } bool IsBalance() { return _IsBalance(_root); } void InOrder() { return _InOrder(_root); } private: void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; Node* ppNode = parent->_parent; subR->_left = parent; parent->_parent = subR; if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { // 判断原父节点在左边还是右边 if (ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; subR->_parent = ppNode; } parent->_bf = subR->_bf = 0; } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; Node* ppNode = parent->_parent; subL->_right = 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; } parent->_bf = subL->_bf = 0; } // 左右双旋 void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; // 通过subLR的平衡因子来区分各种情况 int bf = subLR->_bf; // 先左单旋再右单旋 RotateL(subL); RotateR(parent); subLR->_bf = 0; if (bf == 1) // 在c插入新节点 { parent->_bf = 0; subL->_bf = -1; } else if (bf == 0) // 新增节点就是自己 { parent->_bf = 0; subL->_bf = 0; } else if (bf == -1) // 在b插入新节点 { parent->_bf = 1; subL->_bf = 0; } else { assert(false); } } // 右左双旋 void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; // 通过subRL的平衡因子来区分各种情况 int bf = subRL->_bf; // 先右单旋再左单旋 RotateR(subR); RotateL(parent); subRL->_bf = 0; if (bf == 1) // 在c插入新节点 { parent->_bf = -1; subR->_bf = 0; } else if (bf == 0) // 新增节点是自己 { parent->_bf = 0; subR->_bf = 0; } else if (bf == -1) // 在b插入新节点 { parent->_bf = 0; subR->_bf = 1; } else { assert(false); } } int Height(Node* parent) { if (parent == nullptr) return 0; return max(Height(parent->_left), Height(parent->_right)) + 1; } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); } bool _IsBalance(Node* root) { if (root == nullptr) return true; int leftHeight = Height(root->_left); int rightHeight = Height(root->_right); int diff = rightHeight - leftHeight; return abs(diff) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right); } private: Node* _root = nullptr; };
👉总结👈
本篇博客主要讲解了什么是 AVL 树、AVL 树的插入、旋转、验证等等。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
