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

列印頁面