AVL树

Table of content

AVL树的基本操作
插入操作
删除操作

AVL树是第一个发明的自平衡二叉搜索树。AVL树的名字来源于其发明者的名字——Adelson-Velsky和Landis。

在AVL树中，左右子树高度之差，称为**平衡因子**，必须最多为1。一旦差值超过1，树就会自动执行平衡算法，直到差值再次变为1。

BALANCE FACTOR = 
HEIGHT(LEFT SUBTREE) − HEIGHT(RIGHT SUBTREE)

AVL树的平衡算法中通常有四种旋转情况：LL、RR、LR、RL。

LL旋转

当节点插入到右子树导致树不平衡时，执行LL旋转。这是一种单左旋转，使树再次平衡：

图：LL旋转

发生不平衡的节点成为左子节点，新添加的节点成为右子节点，中间节点作为父节点。

RR旋转

当节点插入到左子树导致树不平衡时，执行RR旋转。这是一种单右旋转，使树再次平衡：

图：RR旋转

发生不平衡的节点成为右子节点，新添加的节点成为左子节点，中间节点作为父节点。

LR旋转

LR旋转是前面单旋转的扩展版本，也称为双旋转。当节点插入到左子树的右子树时执行。LR旋转是左旋转后接右旋转的组合。执行此操作需要遵循多个步骤。

以“A”作为根节点，“B”作为“A”的左子节点，“C”作为“B”的右子节点为例。
由于不平衡发生在A处，因此对A的子节点B和C应用左旋转。
旋转后，C节点成为A的左子节点，B成为C的左子节点。
不平衡仍然存在，因此在根节点A和左子节点C处应用右旋转。
最终右旋转后，C成为根节点，A成为右子节点，B是左子节点。

图：LR旋转

RL旋转

RL旋转也是前面单旋转的扩展版本，因此称为双旋转，如果节点插入到右子树的左子树中则执行。RL旋转是右旋转后接左旋转的组合。执行此操作需要遵循多个步骤。

以“A”作为根节点，“B”作为“A”的右子节点，“C”作为“B”的左子节点为例。
由于不平衡发生在A处，因此对A的子节点B和C应用右旋转。
旋转后，C节点成为A的右子节点，B成为C的右子节点。
不平衡仍然存在，因此在根节点A和右子节点C处应用左旋转。
最终左旋转后，C成为根节点，A成为左子节点，B是右子节点。

图：RL旋转

AVL树的基本操作

在AVL树结构上执行的基本操作包括在二叉搜索树上执行的所有操作，因为AVL树的核心实际上只是一个保持其所有属性的二叉搜索树。因此，在AVL树上执行的基本操作是：**插入**和**删除**。

插入操作

通过遵循二叉搜索树的插入属性将数据插入到AVL树中，即左子树必须包含小于根值的元素，右子树必须包含所有大于的元素。

但是，在AVL树中，在插入每个元素后，会检查树的平衡因子；如果它不超过1，则树保持不变。但是，如果平衡因子超过1，则应用平衡算法重新调整树，使平衡因子再次小于或等于1。

算法

执行AVL树的插入操作涉及以下步骤：

Step 1 − Create a node
Step 2 − Check if the tree is empty
Step 3 − If the tree is empty, the new node created will become the 
         root node of the AVL Tree.
Step 4 − If the tree is not empty, we perform the Binary Search Tree 
         insertion operation and check the balancing factor of the node 
         in the tree.
Step 5 − Suppose the balancing factor exceeds ±1, we apply suitable 
         rotations on the said node and resume the insertion from Step 4.

让我们通过构建一个包含1到7个整数的示例AVL树来理解插入操作。

从第一个元素1开始，我们创建一个节点并测量平衡，即0。

由于二叉搜索属性和平衡因子都满足，因此我们将另一个元素插入到树中。

计算两个节点的平衡因子，发现为-1（左子树的高度为0，右子树的高度为1）。由于它不超过1，因此我们将另一个元素添加到树中。

现在，添加第三个元素后，平衡因子超过1变为2。因此，应用旋转。在这种情况下，应用RR旋转，因为不平衡发生在两个右节点上。

树重新排列为：

类似地，使用这些旋转插入和重新排列后续元素。重新排列后，我们得到如下树：

示例

以下是此操作在各种编程语言中的实现：

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
struct Node {
   int data;
   struct Node *leftChild;
   struct Node *rightChild;
   int height;
};
int max(int a, int b);
int height(struct Node *N){
   if (N == NULL)
      return 0;
   return N->height;
}
int max(int a, int b){
   return (a > b) ? a : b;
}
struct Node *newNode(int data){
   struct Node *node = (struct Node *) malloc(sizeof(struct Node));
   node->data = data;
   node->leftChild = NULL;
   node->rightChild = NULL;
   node->height = 1;
   return (node);
}
struct Node *rightRotate(struct Node *y){
   struct Node *x = y->leftChild;
   struct Node *T2 = x->rightChild;
   x->rightChild = y;
   y->leftChild = T2;
   y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
   x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
   return x;
}
struct Node *leftRotate(struct Node *x){
   struct Node *y = x->rightChild;
   struct Node *T2 = y->leftChild;
   y->leftChild = x;
   x->rightChild = T2;
   x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
   y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
   return y;
}
int getBalance(struct Node *N){
   if (N == NULL)
      return 0;
   return height(N->leftChild) - height(N->rightChild);
}
struct Node *insertNode(struct Node *node, int data){
   if (node == NULL)
      return (newNode(data));
   if (data < node->data)
      node->leftChild = insertNode(node->leftChild, data);
   else if (data > node->data)
      node->rightChild = insertNode(node->rightChild, data);
   else
      return node;
   node->height = 1 + max(height(node->leftChild),
                     height(node->rightChild));
   int balance = getBalance(node);
   if (balance > 1 && data < node->leftChild->data)
      return rightRotate(node);
   if (balance < -1 && data > node->rightChild->data)
      return leftRotate(node);
   if (balance > 1 && data > node->leftChild->data) {
      node->leftChild = leftRotate(node->leftChild);
      return rightRotate(node);
   }
   if (balance < -1 && data < node->rightChild->data) {
      node->rightChild = rightRotate(node->rightChild);
      return leftRotate(node);
   }
   return node;
}
struct Node *minValueNode(struct Node *node){
   struct Node *current = node;
   while (current->leftChild != NULL)
      current = current->leftChild;
   return current;
}
void printTree(struct Node *root){
   if (root == NULL)
      return;
   if (root != NULL) {
      printTree(root->leftChild);
      printf("%d ", root->data);
      printTree(root->rightChild);
   }
}
int main(){
   struct Node *root = NULL;
   root = insertNode(root, 22);
   root = insertNode(root, 14);
   root = insertNode(root, 72);
   root = insertNode(root, 44);
   root = insertNode(root, 25);
   root = insertNode(root, 63);
   root = insertNode(root, 98);
   printf("AVL Tree: ");
   printTree(root);
   return 0;
}

输出

AVL Tree: 14 22 25 44 63 72 98

#include <iostream>
struct Node {
   int data;
   struct Node *leftChild;
   struct Node *rightChild;
   int height;
};
int max(int a, int b);
int height(struct Node *N){
   if (N == NULL)
      return 0;
   return N->height;
}
int max(int a, int b){
   return (a > b) ? a : b;
}
struct Node *newNode(int data){
   struct Node *node = (struct Node *) malloc(sizeof(struct Node));
   node->data = data;
   node->leftChild = NULL;
   node->rightChild = NULL;
   node->height = 1;
   return (node);
}
struct Node *rightRotate(struct Node *y){
   struct Node *x = y->leftChild;
   struct Node *T2 = x->rightChild;
   x->rightChild = y;
   y->leftChild = T2;
   y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
   x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
   return x;
}
struct Node *leftRotate(struct Node *x){
   struct Node *y = x->rightChild;
   struct Node *T2 = y->leftChild;
   y->leftChild = x;
   x->rightChild = T2;
   x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
   y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
   return y;
}
int getBalance(struct Node *N){
   if (N == NULL)
      return 0;
   return height(N->leftChild) - height(N->rightChild);
}
struct Node *insertNode(struct Node *node, int data){
   if (node == NULL)
      return (newNode(data));
   if (data < node->data)
      node->leftChild = insertNode(node->leftChild, data);
   else if (data > node->data)
      node->rightChild = insertNode(node->rightChild, data);
   else
      return node;
   node->height = 1 + max(height(node->leftChild),
                     height(node->rightChild));
   int balance = getBalance(node);
   if (balance > 1 && data < node->leftChild->data)
      return rightRotate(node);
   if (balance < -1 && data > node->rightChild->data)
      return leftRotate(node);
   if (balance > 1 && data > node->leftChild->data) {
      node->leftChild = leftRotate(node->leftChild);
      return rightRotate(node);
   }
   if (balance < -1 && data < node->rightChild->data) {
      node->rightChild = rightRotate(node->rightChild);
      return leftRotate(node);
   }
   return node;
}
struct Node *minValueNode(struct Node *node){
   struct Node *current = node;
   while (current->leftChild != NULL)
      current = current->leftChild;
   return current;
}
void printTree(struct Node *root){
   if (root == NULL)
      return;
   if (root != NULL) {
      printTree(root->leftChild);
      printf("%d ", root->data);
      printTree(root->leftChild);
   }
}
int main(){
   struct Node *root = NULL;
   root = insertNode(root, 22);
   root = insertNode(root, 14);
   root = insertNode(root, 72);
   root = insertNode(root, 44);
   root = insertNode(root, 25);
   root = insertNode(root, 63);
   root = insertNode(root, 98);
   printf("AVL Tree: ");
   printTree(root);
   return 0;
}

输出

AVL Tree: 14 22 14 44 14 22 14

import java.util.*;
import java.io.*;
class Node {
   int key, height;
   Node left, right;
   Node (int d) {
      key = d;
      height = 1;
   }
}
public class AVLTree {
   Node root;
   int height (Node N) {
      if (N == null)
         return 0;
      return N.height;
   }
   int max (int a, int b) {
      return (a > b) ? a : b;
   }
   Node rightRotate (Node y) {
      Node x = y.left;
      Node T2 = x.right;
      x.right = y;
      y.left = T2;
      y.height = max (height (y.left), height (y.right)) + 1;
      x.height = max (height (x.left), height (x.right)) + 1;
      return x;
   }
   Node leftRotate (Node x) {
      Node y = x.right;
      Node T2 = y.left;
      y.left = x;
      x.right = T2;
      x.height = max (height (x.left), height (x.right)) + 1;
      y.height = max (height (y.left), height (y.right)) + 1;
      return y;
   }
   int getBalance (Node N) {
      if (N == null)
         return 0;
      return height (N.left) - height (N.right);
   }
   Node insert (Node node, int key) {
      if (node == null)
         return (new Node (key));
      if (key < node.key)
         node.left = insert (node.left, key);
      else if (key > node.key)
         node.right = insert (node.right, key);
      else
         return node;
      node.height = 1 + max (height (node.left), height (node.right));
      int balance = getBalance (node);
      if (balance > 1 && key < node.left.key)
         return rightRotate (node);
      if (balance < -1 && key > node.right.key)
         return leftRotate (node);
      if (balance > 1 && key > node.left.key) {
         node.left = leftRotate (node.left);
         return rightRotate (node);
      }
      if (balance < -1 && key < node.right.key) {
         node.right = rightRotate (node.right);
         return leftRotate (node);
      }
      return node;
   }
   void printTree(Node root){
   if (root == null)
      return;
   if (root != null) {
      printTree(root.left);
      System.out.print(root.key + " ");
      printTree(root.left);
   }
}
   public static void main(String args[]) {
      AVLTree tree = new AVLTree();

      tree.root = tree.insert(tree.root, 10); 
      tree.root = tree.insert(tree.root, 11); 
      tree.root = tree.insert(tree.root, 12); 
      tree.root = tree.insert(tree.root, 13); 
      tree.root = tree.insert(tree.root, 14); 
      tree.root = tree.insert(tree.root, 15); 
      System.out.println("AVL Tree: ");
      tree.printTree(tree.root);

   }
}

输出

AVL Tree: 
10 11 10 13 10 11 10

class Node(object):
   def __init__(self, data):
      self.data = data
      self.left = None
      self.right = None
      self.height = 1
class AVLTree(object):
   def insert(self, root, key):
      if not root:
         return Node(key)
      elif key < root.data:
         root.left = self.insert(root.left, key)
      else:
         root.right = self.insert(root.right, key)
      root.h = 1 + max(self.getHeight(root.left),
         self.getHeight(root.right))
      b = self.getBalance(root)
      if b > 1 and key < root.left.data:
         return self.rightRotate(root)
      if b < -1 and key > root.right.data:
         return self.leftRotate(root)
      if b > 1 and key > root.left.data:
         root.left = self.lefttRotate(root.left)
         return self.rightRotate(root)
      if b < -1 and key < root.right.data:
         root.right = self.rightRotate(root.right)
         return self.leftRotate(root)
      return root
   def leftRotate(self, z):
      y = z.right
      T2 = y.left
      y.left = z
      z.right = T2
      z.height = 1 + max(self.getHeight(z.left),
         self.getHeight(z.right))
      y.height = 1 + max(self.getHeight(y.left),
         self.getHeight(y.right))
      return y
   def rightRotate(self, z):
      y = z.left
      T3 = y.right
      y.right = z
      z.left = T3
      z.height = 1 + max(self.getHeight(z.left),
         self.getHeight(z.right))
      y.height = 1 + max(self.getHeight(y.left),
         self.getHeight(y.right))
      return y
   def getHeight(self, root):
      if not root:
         return 0
      return root.height
   def getBalance(self, root):
      if not root:
         return 0
      return self.getHeight(root.left) - self.getHeight(root.right)
   def Inorder(self, root):
      if root.left:
         self.Inorder(root.left)
      print(root.data)
      if root.right:
         self.Inorder(root.right)
Tree = AVLTree()
root = None

root = Tree.insert(root, 10)
root = Tree.insert(root, 13)
root = Tree.insert(root, 11)
root = Tree.insert(root, 14)
root = Tree.insert(root, 12)
root = Tree.insert(root, 15)

# Inorder Traversal
print("Inorder traversal of the AVL tree is")
Tree.Inorder(root)

输出

Inorder traversal of the AVL tree is
10
11
12
13
14
15

删除操作

AVL树中的删除发生在三种不同的场景中：

**场景1（删除叶子节点）** - 如果要删除的节点是叶子节点，则无需替换即可删除，因为它不会干扰二叉搜索树属性。但是，平衡因子可能会受到干扰，因此应用旋转来恢复它。
**场景2（删除只有一个子节点的节点）** - 如果要删除的节点只有一个子节点，则用其子节点中的值替换该节点中的值。然后删除子节点。如果平衡因子受到干扰，则应用旋转。
**场景3（删除有两个子节点的节点）** - 如果要删除的节点有两个子节点，则找到该节点的中序后继并将其值替换为中序后继值。然后尝试删除中序后继节点。如果删除后平衡因子超过1，则应用平衡算法。

使用上面给出的相同树，让我们在三种场景中执行删除：

从上面的树中删除元素7：

由于元素7是叶子节点，因此我们通常删除该元素而不干扰树中的任何其他节点

从获得的输出树中删除元素6：

但是，元素6不是叶子节点，并且有一个子节点附加到它。在这种情况下，我们用其子节点：节点5替换节点6。

树的平衡因子变为 1，并且由于它不超过 1，因此树保持不变。如果我们进一步删除元素 5，则需要应用左旋转；由于不平衡发生在 1-2-4 和 3-2-4 处，因此可能是 LL 或 LR 旋转。

删除元素 5 后，平衡因子被扰乱，因此我们应用 LL 旋转（这里也可以应用 LR 旋转）。

在路径 1-2-4 上应用 LL 旋转后，节点 3 保持不变，因为它应该成为节点 2 的右孩子（现在被节点 4 占据）。因此，该节点被添加到节点 2 的右子树中，并作为节点 4 的左孩子。

从剩余树中删除元素 2 -

如场景 3 中所述，此节点有两个子节点。因此，我们找到它的中序后继节点（例如，3），该节点是叶子节点，并用中序后继节点的值替换它的值。

树的平衡因子仍然为 1，因此我们保持树不变，不执行任何旋转。

示例

以下是此操作在各种编程语言中的实现：

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
struct Node {
   int data;
   struct Node *leftChild;
   struct Node *rightChild;
   int height;
};
int max(int a, int b);
int height(struct Node *N){
   if (N == NULL)
      return 0;
   return N->height;
}
int max(int a, int b){
   return (a > b) ? a : b;
}
struct Node *newNode(int data){
   struct Node *node = (struct Node *) malloc(sizeof(struct Node));
   node->data = data;
   node->leftChild = NULL;
   node->rightChild = NULL;
   node->height = 1;
   return (node);
}
struct Node *rightRotate(struct Node *y){
   struct Node *x = y->leftChild;
   struct Node *T2 = x->rightChild;
   x->rightChild = y;
   y->leftChild = T2;
   y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
   x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
   return x;
}
struct Node *leftRotate(struct Node *x){
   struct Node *y = x->rightChild;
   struct Node *T2 = y->leftChild;
   y->leftChild = x;
   x->rightChild = T2;
   x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
   y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
   return y;
}
int getBalance(struct Node *N){
   if (N == NULL)
      return 0;
   return height(N->leftChild) - height(N->rightChild);
}
struct Node *insertNode(struct Node *node, int data){
   if (node == NULL)
      return (newNode(data));
   if (data < node->data)
      node->leftChild = insertNode(node->leftChild, data);
   else if (data > node->data)
      node->rightChild = insertNode(node->rightChild, data);
   else
      return node;
   node->height = 1 + max(height(node->leftChild),
                     height(node->rightChild));
   int balance = getBalance(node);
   if (balance > 1 && data < node->leftChild->data)
      return rightRotate(node);
   if (balance < -1 && data > node->rightChild->data)
      return leftRotate(node);
   if (balance > 1 && data > node->leftChild->data) {
      node->leftChild = leftRotate(node->leftChild);
      return rightRotate(node);
   }
   if (balance < -1 && data < node->rightChild->data) {
      node->rightChild = rightRotate(node->rightChild);
      return leftRotate(node);
   }
   return node;
}
struct Node *minValueNode(struct Node *node){
   struct Node *current = node;
   while (current->leftChild != NULL)
      current = current->leftChild;
   return current;
}
struct Node *deleteNode(struct Node *root, int data){
   if (root == NULL)
      return root;
   if (data < root->data)
      root->leftChild = deleteNode(root->leftChild, data);
   else if (data > root->data)
      root->rightChild = deleteNode(root->rightChild, data);
   else {
      if ((root->leftChild == NULL) || (root->rightChild == NULL)) {
         struct Node *temp = root->leftChild ? root->leftChild : root->rightChild;
         if (temp == NULL) {
            temp = root;
            root = NULL;
         } else
            *root = *temp;
         free(temp);
      } else {
         struct Node *temp = minValueNode(root->rightChild);
         root->data = temp->data;
         root->rightChild = deleteNode(root->rightChild, temp->data);
      }
   }
   if (root == NULL)
      return root;
   root->height = 1 + max(height(root->leftChild),
                     height(root->rightChild));
   int balance = getBalance(root);
   if (balance > 1 && getBalance(root->leftChild) >= 0)
      return rightRotate(root);
   if (balance > 1 && getBalance(root->leftChild) < 0) {
      root->leftChild = leftRotate(root->leftChild);
      return rightRotate(root);
   }
   if (balance < -1 && getBalance(root->rightChild) <= 0)
      return leftRotate(root);
   if (balance < -1 && getBalance(root->rightChild) > 0) {
      root->rightChild = rightRotate(root->rightChild);
      return leftRotate(root);
   }
   return root;
}

// Print the tree
void printTree(struct Node *root){
   if (root != NULL) {
      printTree(root->leftChild);
      printf("%d ", root->data);
      printTree(root->rightChild);
   }
}
int main(){
   struct Node *root = NULL;
   root = insertNode(root, 22);
   root = insertNode(root, 14);
   root = insertNode(root, 72);
   root = insertNode(root, 44);
   root = insertNode(root, 25);
   root = insertNode(root, 63);
   root = insertNode(root, 98);
   printf("AVL Tree: ");
   printTree(root);
   root = deleteNode(root, 25);
   printf("\nAfter deletion: ");
   printTree(root);
   return 0;
}

输出

AVL Tree: 14 22 25 44 63 72 98 
After deletion: 14 22 44 63 72 98

#include <iostream>
struct Node {
   int data;
   struct Node *leftChild;
   struct Node *rightChild;
   int height;
};
int max(int a, int b);
int height(struct Node *N){
   if (N == NULL)
      return 0;
   return N->height;
}
int max(int a, int b){
   return (a > b) ? a : b;
}
struct Node *newNode(int data){
   struct Node *node = (struct Node *) malloc(sizeof(struct Node));
   node->data = data;
   node->leftChild = NULL;
   node->rightChild = NULL;
   node->height = 1;
   return (node);
}
struct Node *rightRotate(struct Node *y){
   struct Node *x = y->leftChild;
   struct Node *T2 = x->rightChild;
   x->rightChild = y;
   y->leftChild = T2;
   y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
   x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
   return x;
}
struct Node *leftRotate(struct Node *x){
   struct Node *y = x->rightChild;
   struct Node *T2 = y->leftChild;
   y->leftChild = x;
   x->rightChild = T2;
   x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
   y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
   return y;
}
int getBalance(struct Node *N){
   if (N == NULL)
      return 0;
   return height(N->leftChild) - height(N->rightChild);
}
struct Node *insertNode(struct Node *node, int data){
   if (node == NULL)
      return (newNode(data));
   if (data < node->data)
      node->leftChild = insertNode(node->leftChild, data);
   else if (data > node->data)
      node->rightChild = insertNode(node->rightChild, data);
   else
      return node;
   node->height = 1 + max(height(node->leftChild),
                     height(node->rightChild));
   int balance = getBalance(node);
   if (balance > 1 && data < node->leftChild->data)
      return rightRotate(node);
   if (balance < -1 && data > node->rightChild->data)
      return leftRotate(node);
   if (balance > 1 && data > node->leftChild->data) {
      node->leftChild = leftRotate(node->leftChild);
      return rightRotate(node);
   }
   if (balance < -1 && data < node->rightChild->data) {
      node->rightChild = rightRotate(node->rightChild);
      return leftRotate(node);
   }
   return node;
}
struct Node *minValueNode(struct Node *node){
   struct Node *current = node;
   while (current->leftChild != NULL)
      current = current->leftChild;
   return current;
}
struct Node *deleteNode(struct Node *root, int data){
   if (root == NULL)
      return root;
   if (data < root->data)
      root->leftChild = deleteNode(root->leftChild, data);
   else if (data > root->data)
      root->rightChild = deleteNode(root->rightChild, data);
   else {
      if ((root->leftChild == NULL) || (root->rightChild == NULL)) {
         struct Node *temp = root->leftChild ? root->leftChild : root->rightChild;
         if (temp == NULL) {
            temp = root;
            root = NULL;
         } else
            *root = *temp;
         free(temp);
      } else {
         struct Node *temp = minValueNode(root->rightChild);
         root->data = temp->data;
         root->rightChild = deleteNode(root->rightChild, temp->data);
      }
   }
   if (root == NULL)
      return root;
   root->height = 1 + max(height(root->leftChild),
                     height(root->rightChild));
   int balance = getBalance(root);
   if (balance > 1 && getBalance(root->leftChild) >= 0)
      return rightRotate(root);
   if (balance > 1 && getBalance(root->leftChild) < 0) {
      root->leftChild = leftRotate(root->leftChild);
      return rightRotate(root);
   }
   if (balance < -1 && getBalance(root->rightChild) <= 0)
      return leftRotate(root);
   if (balance < -1 && getBalance(root->rightChild) > 0) {
      root->rightChild = rightRotate(root->rightChild);
      return leftRotate(root);
   }
   return root;
}

// Print the tree
void printTree(struct Node *root){
   if (root != NULL) {
      printTree(root->leftChild);
      printf("%d ", root->data);
      printTree(root->rightChild);
   }
}
int main(){
   struct Node *root = NULL;
   root = insertNode(root, 22);
   root = insertNode(root, 14);
   root = insertNode(root, 72);
   root = insertNode(root, 44);
   root = insertNode(root, 25);
   root = insertNode(root, 63);
   root = insertNode(root, 98);
   printf("AVL Tree: ");
   printTree(root);
   root = deleteNode(root, 25);
   printf("\nAfter deletion: ");
   printTree(root);
   return 0;
}

输出

AVL Tree: 14 22 25 44 63 72 98 
After deletion: 14 22 44 63 72 98

import java.util.*;
import java.io.*;
class Node {
   int key, height;
   Node left, right;
   Node (int d) {
      key = d;
      height = 1;
   }
}
public class AVLTree {
   Node root;
   int height (Node N) {
      if (N == null)
         return 0;
      return N.height;
   }
   int max (int a, int b) {
      return (a > b) ? a : b;
   }
   Node rightRotate (Node y) {
      Node x = y.left;
      Node T2 = x.right;
      x.right = y;
      y.left = T2;
      y.height = max (height (y.left), height (y.right)) + 1;
      x.height = max (height (x.left), height (x.right)) + 1;
      return x;
   }
   Node leftRotate (Node x) {
      Node y = x.right;
      Node T2 = y.left;
      y.left = x;
      x.right = T2;
      x.height = max (height (x.left), height (x.right)) + 1;
      y.height = max (height (y.left), height (y.right)) + 1;
      return y;
   }
   int getBalance (Node N) {
      if (N == null)
         return 0;
      return height (N.left) - height (N.right);
   }
   Node minValueNode (Node node) {
      Node current = node;
      while (current.left != null)
         current = current.left;
      return current;
   }
   Node deleteNode (Node root, int key) {
      if (root == null)
         return root;
      if (key < root.key)
         root.left = deleteNode (root.left, key);
      else if (key > root.key)
         root.right = deleteNode (root.right, key);
      else {
         if ((root.left == null) || (root.right == null)) {
            Node temp = null;
            if (temp == root.left)
               temp = root.right;
            else
               temp = root.left;
            if (temp == null) {
               temp = root;
               root = null;
            } else
               root = temp;
         } else {
            Node temp = minValueNode (root.right);
            root.key = temp.key;
            root.right = deleteNode (root.right, temp.key);
         }
      }
      if (root == null)
         return root;
      root.height = max (height (root.left), height (root.right)) + 1;
      int balance = getBalance (root);
      if (balance > 1 && getBalance (root.left) >= 0)
         return rightRotate (root);
      if (balance > 1 && getBalance (root.left) < 0) {
         root.left = leftRotate (root.left);
         return rightRotate (root);
      }
      if (balance < -1 && getBalance (root.right) <= 0)
         return leftRotate (root);
      if (balance < -1 && getBalance (root.right) > 0) {
         root.right = rightRotate (root.right);
         return leftRotate (root);
      }
      return root;
   }
   public void printTree(Node root) {
      if (root == null) return;
      printTree(root.left);
      System.out.print(root.key + " ");
      printTree(root.right);
   }
   public static void main (String[]args) {
      AVLTree tree = new AVLTree();
      tree.root = new Node(13);
      tree.root.left = new Node(12);
      tree.root.left.left = new Node(11);
      tree.root.left.left.left = new Node(10);
      tree.root.right = new Node(14);
      tree.root.right.right = new Node(15);
      System.out.print("AVL Tree: ");
      tree.printTree(tree.root);
      tree.root = tree.deleteNode (tree.root, 10);
      System.out.print("\nAfter deletion: ");
      tree.printTree(tree.root);
      System.out.println ("");
   }
}

输出

AVL Tree: 10 11 12 13 14 15 
After deletion: 11 12 13 14 15

class Node(object):
   def __init__(self, data):
      self.data = data
      self.left = None
      self.right = None
      self.height = 1
class AVLTree(object):
   def insert(self, root, key):
      if not root:
         return Node(key)
      elif key < root.data:
         root.left = self.insert(root.left, key)
      else:
         root.right = self.insert(root.right, key)
      root.h = 1 + max(self.getHeight(root.left),
         self.getHeight(root.right))
      b = self.getBalance(root)
      if b > 1 and key < root.left.data:
         return self.rightRotate(root)
      if b < -1 and key > root.right.data:
         return self.leftRotate(root)
      if b > 1 and key > root.left.data:
         root.left = self.lefttRotate(root.left)
         return self.rightRotate(root)
      if b < -1 and key < root.right.data:
          root.right = self.rightRotate(root.right)
          return self.leftRotate(root)
      return root
   def delete(self, root, key):
      if not root:
         return root
      elif key < root.data:
         root.left = self.delete(root.left, key)
      elif key > root.data:
         root.right = self.delete(root.right, key)
      else:
         if root.left is None:
            temp = root.right
            root = None
            return temp
         elif root.right is None:
            temp = root.left
            root = None
            return temp
         temp = self.getMindataueNode(root.right)
         root.data = temp.data
         root.right = self.delete(root.right, temp.data)
      if root is None:
         return root
      root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
      balance = self.getBalance(root)
      if balance > 1 and self.getBalance(root.left) >= 0:
         return self.rightRotate(root)
      if balance < -1 and self.getBalance(root.right) <= 0:
         return self.leftRotate(root)
      if balance > 1 and self.getBalance(root.left) < 0:
         root.left = self.leftRotate(root.left)
         return self.rightRotate(root)
      if balance < -1 and self.getBalance(root.right) > 0:
         root.right = self.rightRotate(root.right)
         return self.leftRotate(root)
      return root
   def leftRotate(self, z):
      y = z.right
      T2 = y.left
      y.left = z
      z.right = T2
      z.height = 1 + max(self.getHeight(z.left),
         self.getHeight(z.right))
      y.height = 1 + max(self.getHeight(y.left),
         self.getHeight(y.right))
      return y
   def rightRotate(self, z):
      y = z.left
      T3 = y.right
      y.right = z
      z.left = T3
      z.height = 1 + max(self.getHeight(z.left),
         self.getHeight(z.right))
      y.height = 1 + max(self.getHeight(y.left),
         self.getHeight(y.right))
      return y
   def getHeight(self, root):
      if not root:
         return 0
      return root.height
   def getBalance(self, root):
      if not root:
         return 0
      return self.getHeight(root.left) - self.getHeight(root.right)
   def Inorder(self, root):
      if root.left:
         self.Inorder(root.left)
      print(root.data, end = " ")
      if root.right:
         self.Inorder(root.right)

Tree = AVLTree()
root = None
root = Tree.insert(root, 10)
root = Tree.insert(root, 13)
root = Tree.insert(root, 11)
root = Tree.insert(root, 14)
root = Tree.insert(root, 12)
root = Tree.insert(root, 15)

# Inorder Traversal
print("AVL Tree: ")
Tree.Inorder(root)
root = Tree.delete(root, 14)
print("\nAfter deletion: ")
Tree.Inorder(root)

输出

AVL Tree: 
10 11 12 13 14 15 
After deletion: 
10 11 12 13 15

打印页面