平衡二叉树

平衡二叉树（Balanced Binary Tree），也称为AVL树，是一种自平衡二叉搜索树（Self-Balancing Binary Search Tree）。平衡二叉树在插入或删除元素时，会通过平衡操作（Rebalance）保持树的左右子树高度差的绝对值不超过1，保证树的高度是近似于log(n)级别的，从而保证查找、插入及删除等操作的时间复杂度为log(n)级别。

特点

平衡二叉树的主要特点如下：

1. 每个节点最多有两个子树；
2. 左子树和右子树的高度差不能超过1；
3. 左子树和右子树都是一棵平衡二叉树。

实现

平衡二叉树是二叉搜索树的一种优化，因此它的节点需要存储和维护以下信息：

1. 左右子树指针；
2. 节点值；
3. 节点高度。

其中，节点高度指的是当前节点到它的最远叶子节点的距离。因此，节点高度为0的表示叶子节点，而节点高度为1的表示只有一个子节点的节点。

平衡二叉树的实现主要包括以下三个操作：

插入操作

向平衡二叉树中插入一个新节点时，需要从根节点开始搜索，找到新节点应该被插入的位置。如果新节点与已存在的节点值相同，则可以选择直接替换或者忽略该节点。

插入新节点后，从新节点父节点开始向上遍历，直到达到根节点或者找到一个节点的左右子树高度差超过1的节点。对于遇到的每个失衡节点，都需要进行平衡操作，以保证树的平衡。

删除操作

从平衡二叉树中删除一个节点时，首先需要从根节点开始搜索到要删除的节点。如果要删除的节点没有子节点，则可以直接删除；如果有一个子节点，则需要用该子节点替换要删除的节点；如果有两个子节点，则可以选择替换为左子树中最大节点或者右子树中最小节点。

删除节点后，从其父节点开始向上遍历，直到达到根节点或者找到一个节点的左右子树高度差超过1的节点。对于遇到的每个失衡节点，都需要进行平衡操作，以保证树的平衡。

平衡操作

平衡操作是平衡二叉树的核心。当插入或删除节点后，使得子树高度差超过1时，就需要对该子树进行平衡操作。

平衡操作可以通过旋转操作实现。旋转操作可以分为左旋和右旋两种，分别对应左子树失衡和右子树失衡的情况。

左旋操作

[图片上传失败...(image-b3aebb-1682412631906)]

对于如上图所示的右子树失衡情况，在节点4处进行左旋操作。左旋操作顺时针将节点4向下移到节点6的左子树上，同时节点6向上移到新的子树根节点位置。此时，节点4、6、2这个子树高度变为了2，同时根节点4的右子树高度也变为了2，树平衡。

右旋操作

[图片上传失败...(image-f81d9a-1682412631906)]

对于如上图所示的左子树失衡情况，在节点6处进行右旋操作。右旋操作逆时针将节点6向下移到节点4的右子树上，同时节点4向上移到新的子树根节点位置。此时，节点4、6、8这个子树高度变为了2，同时根节点6的左子树高度也变为了2，树平衡。

总结

平衡二叉树是一种自平衡二叉搜索树，可以保证查找、插入及删除等操作的时间复杂度为log(n)级别。平衡二叉树通过平衡操作保持树的左右子树高度差的绝对值不超过1，从而保证树的高度近似于log(n)。平衡二叉树的主要操作包括插入、删除和平衡操作，通过旋转操作实现平衡操作。