AVL树

AVL 树定义

AVL 树是一种自平衡二叉查找树，它能够在每次插入或删除节点时自动调整树的结构，使得整棵树始终保持平衡状态。AVL 树的平衡性是通过树中每个节点的平衡因子来维护的，平衡因子是该节点的左子树高度减去右子树高度的差值，因此平衡因子的取值范围为 -1、0、1。

AVL 树的平衡维护策略是：对于任意节点，其左右子树的高度差不超过1，如果不平衡，则通过旋转操作使之恢复平衡状态。AVL 树的旋转操作包括左旋和右旋，左旋是将某个节点的右子树提升为新的父节点，而右旋是将某个节点的左子树提升为新的父节点。

AVL 树的优点是：查询、插入、删除等操作的时间复杂度都是 O(log n)，其中 n 是树中节点的数量。缺点是，由于 AVL 树需要维护平衡状态，所以插入和删除节点时需要进行频繁的旋转操作，导致插入和删除操作的效率较低。