如何梳理介绍AVL树插入新节点后的四种调整情况？

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

AVL树是一种平衡的二叉搜索树，具备以下特性：- 左子树和右子树的高度差不超过1。- 定义节点结构：`template class K, class V`- `class AVLTreeNode`

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树的方法之一。

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