平衡二叉树的定义

平衡二叉树，也称 AVL 树，是一种二叉树，它的左右子树的高度差不超过 1 。平衡二叉树实现了在二叉搜索树的基础上，能够提高查找、插入和删除操作的效率，并且保证树的深度始终保持在 O(log n) 级别，避免了二叉搜索树不平衡而导致时间效率下降的问题。

平衡二叉树的性质

1. 平衡二叉树的高度始终为 O(log n) 级别，n 表示该树中节点数量。

2. 平衡二叉树的任意结点的左子树和右子树高度之差的绝对值不超过 1 。

3. 平衡二叉树是一种二叉搜索树。

平衡二叉树和二叉搜索树的区别

二叉搜索树的查找操作的平均时间复杂度为 O(log n) ，最坏情况下的时间复杂度为 O(n) 。因为二叉搜索树的性质，它的左子树上所有结点的值都比它的根节点位置的值小，右子树上所有节点都比它的根节点位置的值大。但是如果二叉树不平衡，也就是存在一侧比另一侧深很多的情况，那么二叉搜索树的效率将变得非常低。

平衡二叉树是为了解决这一问题而被提出的。平衡二叉树通过限制左右子树的高度差不超过 1 ，来保证整棵树的高度始终为 O(log n) 级别。这样，平衡二叉树虽然在增加、删除、查找操作等的复杂度都比二叉搜索树略微复杂一些，但是更加稳定，可以保证操作的时间复杂度始终为 O(log n) 级别，适用于查找、排序、顺序统计、图的遍历等场景。

平衡二叉树的基本操作

1. 插入操作

比较当前节点的值和待插入节点的值，如果当前节点的值大于待插入节点的值，就去当前节点的左子树中继续递归比较；否则去右子树中比较。如果找到了叶子节点还没有找到位置，就把新节点插入到该叶子节点的位置，并且从该叶子节点开始向上遍历整棵树，更新所有祖先节点的平衡因子，如果发现某棵子树的平衡因子绝对值大于1，就需要进行平衡操作。

2. 删除操作

在平衡二叉树中删除一个节点比较复杂。首先需要把待删除的节点的位置找到，然后有以下三种情况：

① 待删除节点没有子节点：直接删除该节点，并从该节点开始向上遍历整棵树，更新所有祖先节点的平衡因子，如果发现某棵子树的平衡因子绝对值大于1，就需要进行平衡操作。

② 待删除节点只有一个子节点：让子节点替代待删除的节点，并重新从该节点开始向上遍历整棵树，更新所有祖先节点的平衡因子，如果发现某棵子树的平衡因子绝对值大于1，就需要进行平衡操作。

③ 待删除节点有两个子节点：需要找到该节点的后继节点或者前驱节点来替代该节点，由于后继节点或者前驱节点可以保证只有一个子节点或者没有子节点，所以可以按照上两种情况的做法来处理。

3. 平衡操作

当某个节点的左右子树的高度差绝对值大于1时，就需要进行平衡操作，根据平衡因子的正负分别进行右旋或左旋，使得该子树恢复平衡。如果该节点的左右子树高度差绝对值大于1且符号相同，就需要进行双旋转操作。