【软考】数据结构 - 树结构 - 平衡二叉搜索树（AVL树）

心已赠人 2024-03-24 15:07 17阅读 0赞

## 一、AVL树是什么？ ##

AVL树是一种具有自平衡特性的二叉搜索树  
AVL树的名字来源于它的发明者们：G. M. Adelson-Velsky和E. M. Landis。

AVL树虽然是一种自平衡的二叉搜索树，但它并不是唯一的自平衡二叉搜索树。  
其他常见的自平衡二叉搜索树，还包括红黑树、Splay树等。

## 二、AVL树的特点 ##

AVL树要求树中每个节点的左子树和右子树的高度差的绝对值不超过1。  
在AVL树中，任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。  
这样的树通常被称为平衡树，因为它保证了搜索操作的时间复杂度为O(log n)。  
![在这里插入图片描述][ed3c32b5e1d74a4a990378a5c2bd249d.png]

### 2.1 AVL树的优点 ###

*  AVL树能够保证树的平衡，从而保证搜索操作的时间复杂度为O(log n)。
 *  AVL树的自平衡特性使其在插入、删除等操作中具有较好的性能，时间复杂度为O(log n)。
 *  AVL树的插入和删除操作的时间复杂度均为 O(log n)，其中 n 是树中节点的数量。
 *  AVL树通过维护平衡因子和旋转操作，AVL树的平衡性是通过维护一个平衡因子来实现的。
 *  AVL树可以在插入和删除等操作中保持树的平衡性，具有较好的性能。

### 2.2 AVL树的缺点 ###

由于AVL树在插入和删除时（创建和维护），

*  需要进行平衡调整
 *  需要消耗较多的时间和空间
 *  会有一定的开销

因此，在实际应用中，可能会选择其他的平衡二叉搜索树，如红黑树。

## 三、AVL树的插入操作和删除 ##

### 3.1AVL树的插入操作 ###

AVL树的插入操作相对简单。  
AVL树的创建和插入操作与普通二叉搜索树类似。  
AVL树在插入一个新节点后，AVL树可能会失去平衡，AVL树要对树进行旋转以保持平衡。  
AVL树可以通过四种旋转操作，调整节点的位置来恢复AVL树的平衡状态。

AVL树的旋转操作包括四种情况：右左旋、左右旋、左左旋和右右旋。

此时，从根节点开始，按照以下步骤进行平衡调整（旋转操作）：  
**（1）单旋转：**  
如果当前节点的平衡因子（左子树高度减去右子树高度）为-1或1，进行单旋转操作。  
具体来说，如果当前节点的左子树比右子树高，进行右旋操作；反之，进行左旋操作。

**（2）双旋转：**  
如果当前节点的平衡因子为-2或2，进行双旋转操作。  
具体来说，如果当前节点的左子树比右子树高2，进行左右旋操作；反之，进行右左旋操作。

### 3.2 AVL树的删除操作 ###

AVL树的删除操作稍微复杂一些  
AVL树的删除操作需要分三种情况进行处理。  
AVL树在删除一个节点后，可能需要对树进行旋转以保持平衡。