自平衡二叉搜索树（AVL Trees)

AVL树

---

AVL树又称之为自平衡二叉搜索树。如果一棵二叉树，其左子树和右子树中的每个节点的高度为-1,0或者+1，则称此二叉树是平衡的。

为什么平衡是重要的

---

可以看出，二叉搜索树的最坏时间复杂度类似于线性搜索算法，这是由于树的一侧比另外一侧具有更多的元素。

在实际的数据存储中，我们无法预测树的结构，因此二叉搜索树的查找性能可能会比预期的差。为了保证二叉搜索树的性能不变，我们需要使该树保持平衡，确保树的一侧不比另外一侧有更多的子级，这样可以确保执行二叉查找时，两面都具有相同的元素数量。

平衡因子计算公式如下：

BlanceFactor=height(left-subtree)-height(right-subtree)

如果发现其不同节点的高度差大于1，需要使用四种旋转技术平衡树。这些技术通常用于插入和删除树中节点时。

AVL 旋转

---

为了保持树平衡，需要使用以下几种方式保持平衡

左旋

在这种情况下，通过向左旋转一次来恢复平衡属性

右旋

在这种情况下，通过向右旋转一次来恢复平衡属性

左-右旋转

以下这种情况，通过左旋转然后再右旋转来恢复平衡属性

右-做旋转

以下这种情况，通右旋转然后再左旋转来恢复平衡属性

更多内容，欢迎访问：