请问AVL树在插入新节点后，具体有哪四种调整策略？

本文共计1918个文字，预计阅读时间需要8分钟。

AVL树是一种高度平衡的二叉搜索树，具有以下特性：左右子树的高度差不超过1。此处的AVL树节点定义如下：

cpptemplate struct AVLTreeNode { K key; V value; AVLTreeNode* _left; AVLTreeNode* _right;};

AVL树是一个高度平衡的二叉搜索树

• 满足二叉搜索树的所有特性。
• 左子树和右子树的高度之差的绝对值不大于1。

此处AVL树结点的定义

template<class K, class V> struct AVLTreeNode { AVLTreeNode<K, V> _left; AVLTreeNode<K, V> _right; AVLTreeNode<K, V> _parent; pair<K, V> _kv; int _bf; //平衡因子 AVLTreeNode(const pair<K, V>& kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_kv(kv) ,_bf(0) {} };

使用平衡因子，是维持AVL树的方法之一。

此处平衡因子 = 右子树高度 - 左子树高度。