原文： https://www.programiz.com/dsa/avl-tree

在本教程中，您将学习什么是 avl 树。 此外，您还将找到在 C，C++ ，Java 和 Python 的 avl 树上执行的各种操作的工作示例。

AVL 树是一种自平衡二叉搜索树，其中每个节点都维护额外的信息，称为平衡因子，其值为 -1、0 或 +1。

AVL 树以其发明者 Georgy Adelson-Velsky 和 Landis 得名。

平衡系数

AVL 树中节点的平衡因子是该节点的左子树的高度和右子树的高度之间的差。

平衡因子=（左子树的高度-右子树的高度）或（右子树的高度-左子树的高度）

Avl 树的自平衡属性由平衡因子保持。 平衡因子的值应始终为 -1、0 或 +1。

平衡 avl 树的示例是：

AVL 树 - 图1

Avl tree

AVL 树上的操作

可以在 AVL 树上执行的各种操作是：

旋转 AVL 树中的子树

在旋转操作中，子树的节点位置互换。

轮播有两种类型：

向左旋转

在向左旋转时，右侧节点的排列将转换为左侧节点的排列。

算法

  1. 令初始树为：
    AVL 树 - 图2
    左旋转

  2. 如果y具有左子树，则将x分配为y的左子树的父树。
    AVL 树 - 图3
    将x分配为y的左子树的父级

  3. 如果x的父级是NULL，则将y作为树的根。

  4. 否则，如果x是p的左子代，则将y设为p的左子代。

  5. 否则，将y分配为p的右子元素。
    AVL 树 - 图4
    将x的父级更改为y的父级

  6. 将y设为x的父代。
    AVL 树 - 图5
    将y指定为x的父代。

向右旋转

在向左旋转时，左侧节点的排列将转换为右侧节点的排列。

  1. 令初始树为：
    AVL 树 - 图6
    初始树

  2. 如果x具有右子树，则将y分配为x的右子树的父树。
    AVL 树 - 图7
    将y分配为x
    的右子树的父级

  3. 如果y的父级为NULL，则将x作为树的根。

  4. 否则，如果y是其父级p的右子，则将x作为p的右子。

  5. 否则，将x分配为p的左子元素。
    AVL 树 - 图8
    将y的父级指定为x的父级。

  6. 使x为y的父代。
    AVL 树 - 图9
    将x分配为y的父项

左右旋转

在左右旋转时，首先将布置向左移动，然后向右移动。

  1. 在x-y上向左旋转。
    AVL 树 - 图10
    向左旋转x-y

  2. 在y-z上向右旋转。
    AVL 树 - 图11
    向右旋转z-y

在左右旋转时，这些布置首先向右移动，然后向左移动。

  1. 在x-y上向右旋转。
    AVL 树 - 图12
    右旋转x-y

  2. 在z-y上向左旋转。
    AVL 树 - 图13
    向左旋转z-y

插入新节点的算法

newNode始终作为平衡因子等于 0 的叶节点插入。

  1. 令初始树为：
    AVL 树 - 图14
    插入的初始树
    令要插入的节点为：
    AVL 树 - 图15
    新节点

  2. 使用以下递归步骤转到相应的叶节点以插入newNode。 比较newKey与当前树的rootKey。

    1. 如果newKey < rootKey，则在当前节点的左子树上调用插入算法，直到到达叶节点为止。

    2. 否则，如果newKey > rootKey，则在当前节点的右子树上调用插入算法，直到到达叶节点为止。

    3. 否则，返回leafNode。
      AVL 树 - 图16
      查找插入newNode的位置

  3. 将通过上述步骤获得的leafKey与newKey进行比较：

    1. 如果newKey < leafKey，则将newNode设为leafNode的leftChild。

    2. 否则，将newNode设为leafNode的rightChild。
      AVL 树 - 图17
      插入新节点

  4. 更新节点的balanceFactor。
    AVL 树 - 图18
    插入后更新平衡因子

  5. 如果节点不平衡，请重新平衡该节点。

    1. 如果balanceFactor > 1，则表示左侧子树的高度大于右侧子树的高度。 因此，请向右旋转或向左旋转

      1. 如果newNodeKey < leftChildKey进行右旋转。

      2. 否则，请左右旋转。
        AVL 树 - 图19
        旋转平衡树
        AVL 树 - 图20
        旋转平衡树

    2. 如果balanceFactor < -1，则意味着右子树的高度大于左子树的高度。 因此，请向右旋转或向左旋转

      1. 如果newNodeKey > rightChildKey进行左旋转。
      2. 否则，请左右旋转
  6. 最终的树是：
    AVL 树 - 图21
    最终的平衡树

删除节点的算法

节点始终被删除为叶节点。 删除节点后，节点的平衡因子将更改。 为了重新平衡平衡系数，执行适当的旋转。

  1. 找到nodeToBeDeleted（递归用于在下面使用的代码中找到nodeToBeDeleted）。
    AVL 树 - 图22
    定位要删除的节点

  2. 删除节点有以下三种情况：

    1. 如果nodeToBeDeleted是叶节点（即没有任何子节点），则删除nodeToBeDeleted。

    2. 如果nodeToBeDeleted有一个子级，则用该子级的内容替换nodeToBeDeleted的内容。 移走子级。

    3. 如果nodeToBeDeleted有两个子级，则找到nodeToBeDeleted的有序继承人w（即，在右子树中具有键的最小值的节点）。
      AVL 树 - 图23
      寻找继任者

      1. 将nodeToBeDeleted的内容替换为w的内容。
        AVL 树 - 图24
        替换要删除的节点

      2. 删除叶节点w。
        AVL 树 - 图25
        移除

  3. 更新节点的balanceFactor。
    AVL 树 - 图26
    更新bf

  4. 如果任何节点的平衡因子不等于 -1、0 或 1，则重新平衡树。

    1. 如果currentNode > balanceFactor，

      1. 如果leftChild的balanceFactor >= 0，请向右旋转。
        AVL 树 - 图27
        向右旋转以平衡树

      2. 否则做左右旋转。

    2. 如果currentNode的balanceFactor < -1，

      1. 如果rightChild的balanceFactor = 0，请向左旋转。
      2. 否则做左右旋转。
  5. 最终的树是：
    AVL 树 - 图28
    Avl 最终树

Python，Java 和 C/C++ 示例

  1. # AVL tree implementation in Python
  3. import sys
  5. # Create a tree node
  6. class TreeNode(object):
  7.     def __init__(self, key):
  8.         self.key = key
  9.         self.left = None
  10.         self.right = None
  11.         self.height = 1
  13. class AVLTree(object):
  15.     # Function to insert a node
  16.     def insert_node(self, root, key):
  18.         # Find the correct location and insert the node
  19.         if not root:
  20.             return TreeNode(key)
  21.         elif key < root.key:
  22.             root.left = self.insert_node(root.left, key)
  23.         else:
  24.             root.right = self.insert_node(root.right, key)
  26.         root.height = 1 + max(self.getHeight(root.left),
  27.                               self.getHeight(root.right))
  29.         # Update the balance factor and balance the tree
  30.         balanceFactor = self.getBalance(root)
  31.         if balanceFactor > 1:
  32.             if key < root.left.key:
  33.                 return self.rightRotate(root)
  34.             else:
  35.                 root.left = self.leftRotate(root.left)
  36.                 return self.rightRotate(root)
  38.         if balanceFactor < -1:
  39.             if key > root.right.key:
  40.                 return self.leftRotate(root)
  41.             else:
  42.                 root.right = self.rightRotate(root.right)
  43.                 return self.leftRotate(root)
  45.         return root
  47.     # Function to delete a node
  48.     def delete_node(self, root, key):
  50.         # Find the node to be deleted and remove it
  51.         if not root:
  52.             return root
  53.         elif key < root.key:
  54.             root.left = self.delete_node(root.left, key)
  55.         elif key > root.key:
  56.             root.right = self.delete_node(root.right, key)
  57.         else:
  58.             if root.left is None:
  59.                 temp = root.right
  60.                 root = None
  61.                 return temp
  62.             elif root.right is None:
  63.                 temp = root.left
  64.                 root = None
  65.                 return temp
  66.             temp = self.getMinValueNode(root.right)
  67.             root.key = temp.key
  68.             root.right = self.delete_node(root.right,
  69.                                           temp.key)
  70.         if root is None:
  71.             return root
  73.         # Update the balance factor of nodes
  74.         root.height = 1 + max(self.getHeight(root.left),
  75.                               self.getHeight(root.right))
  77.         balanceFactor = self.getBalance(root)
  79.         # Balance the tree
  80.         if balanceFactor > 1:
  81.             if self.getBalance(root.left) >= 0:
  82.                 return self.rightRotate(root)
  83.             else:
  84.                 root.left = self.leftRotate(root.left)
  85.                 return self.rightRotate(root)
  86.         if balanceFactor < -1:
  87.             if self.getBalance(root.right) <= 0:
  88.                 return self.leftRotate(root)
  89.             else:
  90.                 root.right = self.rightRotate(root.right)
  91.                 return self.leftRotate(root)
  92.         return root
  94.     # Function to perform left rotation
  95.     def leftRotate(self, z):
  96.         y = z.right
  97.         T2 = y.left
  98.         y.left = z
  99.         z.right = T2
  100.         z.height = 1 + max(self.getHeight(z.left),
  101.                            self.getHeight(z.right))
  102.         y.height = 1 + max(self.getHeight(y.left),
  103.                            self.getHeight(y.right))
  104.         return y
  106.     # Function to perform right rotation
  107.     def rightRotate(self, z):
  108.         y = z.left
  109.         T3 = y.right
  110.         y.right = z
  111.         z.left = T3
  112.         z.height = 1 + max(self.getHeight(z.left),
  113.                            self.getHeight(z.right))
  114.         y.height = 1 + max(self.getHeight(y.left),
  115.                            self.getHeight(y.right))
  116.         return y
  118.     # Get the height of the node
  119.     def getHeight(self, root):
  120.         if not root:
  121.             return 0
  122.         return root.height
  124.     # Get balance factore of the node
  125.     def getBalance(self, root):
  126.         if not root:
  127.             return 0
  128.         return self.getHeight(root.left) - self.getHeight(root.right)
  130.     def getMinValueNode(self, root):
  131.         if root is None or root.left is None:
  132.             return root
  133.         return self.getMinValueNode(root.left)
  135.     def preOrder(self, root):
  136.         if not root:
  137.             return
  138.         print("{0} ".format(root.key), end="")
  139.         self.preOrder(root.left)
  140.         self.preOrder(root.right)
  142.     # Print the tree
  143.     def printHelper(self, currPtr, indent, last):
  144.         if currPtr != None:
  145.             sys.stdout.write(indent)
  146.             if last:
  147.                 sys.stdout.write("R----")
  148.                 indent += "     "
  149.             else:
  150.                 sys.stdout.write("L----")
  151.                 indent += "|    "
  152.             print(currPtr.key)
  153.             self.printHelper(currPtr.left, indent, False)
  154.             self.printHelper(currPtr.right, indent, True)
  156. myTree = AVLTree()
  157. root = None
  158. nums = [33, 13, 52, 9, 21, 61, 8, 11]
  159. for num in nums:
  160.     root = myTree.insert_node(root, num)
  161. myTree.printHelper(root, "", True)
  162. key = 13
  163. root = myTree.delete_node(root, key)
  164. print("After Deletion: ")
  165. myTree.printHelper(root, "", True)
  1. // AVL tree implementation in Java
  3. // Create node
  4. class Node {
  5.   int item, height;
  6.   Node left, right;
  8.   Node(int d) {
  9.     item = d;
  10.     height = 1;
  11.   }
  12. }
  14. // Tree class
  15. class AVLTree {
  16.   Node root;
  18.   int height(Node N) {
  19.     if (N == null)
  20.       return 0;
  21.     return N.height;
  22.   }
  24.   int max(int a, int b) {
  25.     return (a > b) ? a : b;
  26.   }
  28.   Node rightRotate(Node y) {
  29.     Node x = y.left;
  30.     Node T2 = x.right;
  31.     x.right = y;
  32.     y.left = T2;
  33.     y.height = max(height(y.left), height(y.right)) + 1;
  34.     x.height = max(height(x.left), height(x.right)) + 1;
  35.     return x;
  36.   }
  38.   Node leftRotate(Node x) {
  39.     Node y = x.right;
  40.     Node T2 = y.left;
  41.     y.left = x;
  42.     x.right = T2;
  43.     x.height = max(height(x.left), height(x.right)) + 1;
  44.     y.height = max(height(y.left), height(y.right)) + 1;
  45.     return y;
  46.   }
  48.   // Get balance factor of a node
  49.   int getBalanceFactor(Node N) {
  50.     if (N == null)
  51.       return 0;
  52.     return height(N.left) - height(N.right);
  53.   }
  55.   // Insert a node
  56.   Node insertNode(Node node, int item) {
  58.     // Find the position and insert the node
  59.     if (node == null)
  60.       return (new Node(item));
  61.     if (item < node.item)
  62.       node.left = insertNode(node.left, item);
  63.     else if (item > node.item)
  64.       node.right = insertNode(node.right, item);
  65.     else
  66.       return node;
  68.     // Update the balance factor of each node
  69.     // And, balance the tree
  70.     node.height = 1 + max(height(node.left), height(node.right));
  71.     int balanceFactor = getBalanceFactor(node);
  72.     if (balanceFactor > 1) {
  73.       if (item < node.left.item) {
  74.         return rightRotate(node);
  75.       } else if (item > node.left.item) {
  76.         node.left = leftRotate(node.left);
  77.         return rightRotate(node);
  78.       }
  79.     }
  80.     if (balanceFactor < -1) {
  81.       if (item > node.right.item) {
  82.         return leftRotate(node);
  83.       } else if (item < node.right.item) {
  84.         node.left = rightRotate(node.left);
  85.         return leftRotate(node);
  86.       }
  87.     }
  88.     return node;
  89.   }
  91.   Node nodeWithMimumValue(Node node) {
  92.     Node current = node;
  93.     while (current.left != null)
  94.       current = current.left;
  95.     return current;
  96.   }
  98.   // Delete a node
  99.   Node deleteNode(Node root, int item) {
  101.     // Find the node to be deleted and remove it
  102.     if (root == null)
  103.       return root;
  104.     if (item < root.item)
  105.       root.left = deleteNode(root.left, item);
  106.     else if (item > root.item)
  107.       root.right = deleteNode(root.right, item);
  108.     else {
  109.       if ((root.left == null) || (root.right == null)) {
  110.         Node temp = null;
  111.         if (temp == root.left)
  112.           temp = root.right;
  113.         else
  114.           temp = root.left;
  115.         if (temp == null) {
  116.           temp = root;
  117.           root = null;
  118.         } else
  119.           root = temp;
  120.       } else {
  121.         Node temp = nodeWithMimumValue(root.right);
  122.         root.item = temp.item;
  123.         root.right = deleteNode(root.right, temp.item);
  124.       }
  125.     }
  126.     if (root == null)
  127.       return root;
  129.     // Update the balance factor of each node and balance the tree
  130.     root.height = max(height(root.left), height(root.right)) + 1;
  131.     int balanceFactor = getBalanceFactor(root);
  132.     if (balanceFactor > 1) {
  133.       if (getBalanceFactor(root.left) >= 0) {
  134.         return rightRotate(root);
  135.       } else {
  136.         root.left = leftRotate(root.left);
  137.         return rightRotate(root);
  138.       }
  139.     }
  140.     if (balanceFactor < -1) {
  141.       if (getBalanceFactor(root.right) <= 0) {
  142.         return leftRotate(root);
  143.       } else {
  144.         root.right = rightRotate(root.right);
  145.         return leftRotate(root);
  146.       }
  147.     }
  148.     return root;
  149.   }
  151.   void preOrder(Node node) {
  152.     if (node != null) {
  153.       System.out.print(node.item + " ");
  154.       preOrder(node.left);
  155.       preOrder(node.right);
  156.     }
  157.   }
  159.   // Print the tree
  160.   private void printTree(Node currPtr, String indent, boolean last) {
  161.     if (currPtr != null) {
  162.       System.out.print(indent);
  163.       if (last) {
  164.         System.out.print("R----");
  165.         indent += "   ";
  166.       } else {
  167.         System.out.print("L----");
  168.         indent += "|  ";
  169.       }
  170.       System.out.println(currPtr.item);
  171.       printTree(currPtr.left, indent, false);
  172.       printTree(currPtr.right, indent, true);
  173.     }
  174.   }
  176.   // Driver code
  177.   public static void main(String[] args) {
  178.     AVLTree tree = new AVLTree();
  179.     tree.root = tree.insertNode(tree.root, 33);
  180.     tree.root = tree.insertNode(tree.root, 13);
  181.     tree.root = tree.insertNode(tree.root, 53);
  182.     tree.root = tree.insertNode(tree.root, 9);
  183.     tree.root = tree.insertNode(tree.root, 21);
  184.     tree.root = tree.insertNode(tree.root, 61);
  185.     tree.root = tree.insertNode(tree.root, 8);
  186.     tree.root = tree.insertNode(tree.root, 11);
  187.     tree.printTree(tree.root, "", true);
  188.     tree.root = tree.deleteNode(tree.root, 13);
  189.     System.out.println("After Deletion: ");
  190.     tree.printTree(tree.root, "", true);
  191.   }
  192. }
// AVL tree implementation in C

#include <stdio.h>
#include <stdlib.h>

// Create Node
struct Node {
  int key;
  struct Node *left;
  struct Node *right;
  int height;
};

int max(int a, int b);

// Calculate height
int height(struct Node *N) {
  if (N == NULL)
    return 0;
  return N->height;
}

int max(int a, int b) {
  return (a > b) ? a : b;
}

// Create a node
struct Node *newNode(int key) {
  struct Node *node = (struct Node *)
    malloc(sizeof(struct Node));
  node->key = key;
  node->left = NULL;
  node->right = NULL;
  node->height = 1;
  return (node);
}

// Right rotate
struct Node *rightRotate(struct Node *y) {
  struct Node *x = y->left;
  struct 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;
}

// Left Rotate
struct Node *leftRotate(struct Node *x) {
  struct Node *y = x->right;
  struct 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;
}

// Get the balance factor
int getBalanceFactor(struct Node *N) {
  if (N == NULL)
    return 0;
  return height(N->left) - height(N->right);
}

// Insert node
struct Node *insertNode(struct Node *node, int key) {
  // Find the correct position to insert the node and insert it
  if (node == NULL)
    return (newNode(key));
  if (key < node->key)
    node->left = insertNode(node->left, key);
  else if (key > node->key)
    node->right = insertNode(node->right, key);
  else
    return node;

  // Update the balance factor of each node and
  // Balance the tree
  node->height = 1 + max(height(node->left),
               height(node->right));
  int balanceFactor = getBalanceFactor(node);
  if (balanceFactor > 1) {
    if (key < node->left->key) {
      return rightRotate(node);
    } else if (key > node->left->key) {
      node->left = leftRotate(node->left);
      return rightRotate(node);
    }
  }
  if (balanceFactor < -1) {
    if (key > node->right->key) {
      return leftRotate(node);
    } else if (key < node->right->key) {
      node->left = rightRotate(node->left);
      return leftRotate(node);
    }
  }
  return node;
}

struct Node *minValueNode(struct Node *node) {
  struct Node *current = node;
  while (current->left != NULL)
    current = current->left;
  return current;
}

// Delete a node
struct Node *deleteNode(struct Node *root, int key) {
  // Find the node and delete it
  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)) {
      struct Node *temp = root->left ? root->left : root->right;
      if (temp == NULL) {
        temp = root;
        root = NULL;
      } else
        *root = *temp;

      free(temp);
    } else {
      struct Node *temp = minValueNode(root->right);
      root->key = temp->key;
      root->right = deleteNode(root->right, temp->key);
    }
  }
  if (root == NULL)
    return root;

  // Update the balance factor of each node and
  // balance the tree
  root->height = 1 + max(height(root->left),
               height(root->right));
  int balanceFactor = getBalanceFactor(root);
  if (balanceFactor > 1) {
    if (getBalanceFactor(root->left) >= 0) {
      return rightRotate(root);
    } else {
      root->left = leftRotate(root->left);
      return rightRotate(root);
    }
  }
  if (balanceFactor < -1) {
    if (getBalanceFactor(root->right) <= 0) {
      return leftRotate(root);
    } else {
      root->right = rightRotate(root->right);
      return leftRotate(root);
    }
  }
  return root;
}

// Print the tree
void printPreOrder(struct Node *root) {
  if (root != NULL) {
    printf("%d ", root->key);
    printPreOrder(root->left);
    printPreOrder(root->right);
  }
}

int main() {
  struct Node *root = NULL;
  root = insertNode(root, 33);
  root = insertNode(root, 13);
  root = insertNode(root, 53);
  root = insertNode(root, 9);
  root = insertNode(root, 21);
  root = insertNode(root, 61);
  root = insertNode(root, 8);
  root = insertNode(root, 11);
  printPreOrder(root);
  root = deleteNode(root, 13);
  printf("\nAfter deletion: ");
  printPreOrder(root);
}

// AVL tree implementation in C++

#include <iostream>
using namespace std;

class Node {
   public:
  int key;
  Node *left;
  Node *right;
  int height;
};

int max(int a, int b);

// Calculate height
int height(Node *N) {
  if (N == NULL)
    return 0;
  return N->height;
}

int max(int a, int b) {
  return (a > b) ? a : b;
}

// New node creation
Node *newNode(int key) {
  Node *node = new Node();
  node->key = key;
  node->left = NULL;
  node->right = NULL;
  node->height = 1;
  return (node);
}

// Rotate right
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;
}

// Rotate left
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;
}

// Get the balance factor of each node
int getBalanceFactor(Node *N) {
  if (N == NULL)
    return 0;
  return height(N->left) -
       height(N->right);
}

// Insert a node
Node *insertNode(Node *node, int key) {
  // Find the correct postion and insert the node
  if (node == NULL)
    return (newNode(key));
  if (key < node->key)
    node->left = insertNode(node->left, key);
  else if (key > node->key)
    node->right = insertNode(node->right, key);
  else
    return node;

  // Update the balance factor of each node and
  // balance the tree
  node->height = 1 + max(height(node->left),
               height(node->right));
  int balanceFactor = getBalanceFactor(node);
  if (balanceFactor > 1) {
    if (key < node->left->key) {
      return rightRotate(node);
    } else if (key > node->left->key) {
      node->left = leftRotate(node->left);
      return rightRotate(node);
    }
  }
  if (balanceFactor < -1) {
    if (key > node->right->key) {
      return leftRotate(node);
    } else if (key < node->right->key) {
      node->left = rightRotate(node->left);
      return leftRotate(node);
    }
  }
  return node;
}

// Node with minimum value
Node *nodeWithMimumValue(Node *node) {
  Node *current = node;
  while (current->left != NULL)
    current = current->left;
  return current;
}

// Delete a node
Node *deleteNode(Node *root, int key) {
  // Find the node and delete it
  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 = root->left ? root->left : root->right;
      if (temp == NULL) {
        temp = root;
        root = NULL;
      } else
        *root = *temp;
      free(temp);
    } else {
      Node *temp = nodeWithMimumValue(root->right);
      root->key = temp->key;
      root->right = deleteNode(root->right,
                   temp->key);
    }
  }

  if (root == NULL)
    return root;

  // Update the balance factor of each node and
  // balance the tree
  root->height = 1 + max(height(root->left),
               height(root->right));
  int balanceFactor = getBalanceFactor(root);
  if (balanceFactor > 1) {
    if (getBalanceFactor(root->left) >= 0) {
      return rightRotate(root);
    } else {
      root->left = leftRotate(root->left);
      return rightRotate(root);
    }
  }
  if (balanceFactor < -1) {
    if (getBalanceFactor(root->right) <= 0) {
      return leftRotate(root);
    } else {
      root->right = rightRotate(root->right);
      return leftRotate(root);
    }
  }
  return root;
}

// Print the tree
void printTree(Node *root, string indent, bool last) {
  if (root != nullptr) {
    cout << indent;
    if (last) {
      cout << "R----";
      indent += "   ";
    } else {
      cout << "L----";
      indent += "|  ";
    }
    cout << root->key << endl;
    printTree(root->left, indent, false);
    printTree(root->right, indent, true);
  }
}

int main() {
  Node *root = NULL;
  root = insertNode(root, 33);
  root = insertNode(root, 13);
  root = insertNode(root, 53);
  root = insertNode(root, 9);
  root = insertNode(root, 21);
  root = insertNode(root, 61);
  root = insertNode(root, 8);
  root = insertNode(root, 11);
  printTree(root, "", true);
  root = deleteNode(root, 13);
  cout << "After deleting " << endl;
  printTree(root, "", true);
}

AVL 树上的不同操作的复杂度

插入 删除 搜索
O(log n) O(log n) O(log n)

AVL 树应用

  • 用于索引数据库中的大记录
  • 用于在大型数据库中搜索