C 语言中的 AVL 树程序

什么是 AVL 树？

Adelson-Velskii 和 Landis 是 AVL 树的发现者，因此该名称来源于他们的名字，即 AVL。它通常被称为高度二叉树。AVL 树是其每个节点都具有以下特征之一的树。

如果一个节点的左子树中最长的路径比其右子树中最长的路径长，则该节点被称为“左重”。

如果一个节点的右子树中最长的路径比其左子树中最长的路径长一个，则该节点被称为“右重”。

如果右子树和左子树中最长的路径相等，则称节点是平衡的。

AVL 树是一种高度平衡树，其中每个节点的右子树和左子树的高度差为 -1、0 或 1。一个称为平衡因子的因素将子树的高度差分开。因此，我们可以将 AVL 定义为一种平衡二叉搜索树，其中每个节点的平衡因子为 -1、0 或 +1。在这种情况下，确定平衡因子的公式如下

平衡因子属性 -

• 如果子树的平衡因子大于零，则称其为左重，因为左子树的高度大于右子树的高度，这意味着左子树包含的节点多于右子树。
• 如果子树的平衡因子为 0，则称其为右重，因为左子树的高度小于右子树的高度，这意味着右子树包含的节点多于左子树。
• 如果平衡因子为零，则子树完全平衡，左右子树的高度相等。

AVL 树的旋转

如果树的任何节点失衡，则执行必要的旋转以纠正失衡。

C 语言中的 AVL 树操作

在 AVL 树中，执行三种类型的操作

• 插入新节点
• 删除节点
  从右子树中删除节点
  从左子树中删除节点
• 在 AVL 树中查找节点

要执行这些操作，我们必须执行四种类型的旋转。四种不同的旋转类型是可能的，并且在各种场景下使用，如下所示

LL 旋转： 当新节点作为非平衡节点的左子树的左子节点添加时。

RR 旋转：当新节点被添加到失衡节点的右子树的右子节点时，这个过程称为 RR 旋转。

LR 旋转：当新节点被添加到失衡节点右子树的左子节点时。

RL 旋转：当新节点被添加到失衡节点左子树的右子节点时。

实施

AVL 树中的插入：为了确保在每次插入后给定树保持 AVL 属性，我们必须对标准 BST 插入操作添加一些重新平衡。

可用于平衡 BST 而不违反 BST 属性的两个基本操作如下（keys(left) < key(root) < keys(right)）。

• 左旋
• 右旋

插入过程包括以下步骤

• 让新添加的节点为 w
• 插入 w 的标准 BST 插入。
• 从 w 向上遍历以找到第一个非平衡节点。设 z 为第一个非平衡节点，y 为 z 在从 w 到 z 的路径上的子节点，x 为 z 在从 w 到 z 的路径上的孙节点。
• 通过对以 z 为根的子树执行必要的旋转来重新平衡树。由于 x、y 和 z 可以以四种不同的方式排列，因此必须处理四种可能的情况。
• 四种可能的排列如下
• y 是 z 的左子节点，x 是 y 的左子节点（左左情况）
  y 是 z 的左子节点，x 是 y 的右子节点（左右情况）
  y 是 z 的右子节点，x 是 y 的右子节点（右右情况）
  y 是 z 的右子节点，x 是 y 的左子节点（右左情况）。

C 语言中的 AVL 树程序

程序 1

输出

4 2 1 3 5 6

表示

因此，插入这些元素后，我们得到了上述 AVL 树。上述 AVL 树的先序遍历是 4->2->1->3->5->6。

程序 2

输出

------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 1
Enter data: 2
Do you want to continue? y

------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 1
Enter data: 2
Do you want to continue? y

------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT

Enter Your Choice: 3
Enter data: 2

 Node found

Do you want to continue? y


------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 2
Enter data: 2
Do you want to continue? y

------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 4
2
Do you want to continue? n

输出 2

结论

AVL 树的插入操作的运行时间复杂度为 O(log n)，用于查找插入位置并返回到根。类似地，确定要删除的节点并执行后续操作以改变 AVL 树的平衡因子的运行时间复杂度为 O(log n)。与二叉搜索树相比，AVL 树具有更快、更稳定的时间复杂度。