AVL树

提示

AVL树定义：AVL树是一种自平衡二叉搜索树，每个节点都有一个平衡因子（左子树高度减去右子树高度），其值为 -1、0 或 +1。
节点旋转：为保持平衡，AVL树通过左旋、右旋、左-右旋和右-左旋四种旋转操作调整树的结构。
操作复杂度：在AVL树上执行插入、删除和搜索操作的时间复杂度均为O(log n)，使其适用于大型数据库和索引记录。

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

AVL 树以其发明者 Georgy Adelson-Velsky 和 Landis 的名字命名。

平衡因子

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

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

AVL 树的自平衡特性由平衡因子维护。平衡因子的值应始终为 -1、0 或 +1。

一个平衡的 AVL 树的示例是：

avl 树

对 AVL 树的操作

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

AVL 树中子树的旋转

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

旋转分为两种类型：

左旋

在左旋中，右侧节点的排列转换为左侧节点的排列。

算法

初始树为：
如果 y 有左子树，则将 x 设为 y 的左子树的父节点。
如果 x 的父节点为 NULL，则使 y 成为树的根。
否则如果 x 是其父节点 p 的左孩子，将 y 设为 p 的左孩子。
否则将 y 设为 p 的右孩子。
将 y 设为 x 的父节点。

右旋

在右旋中，左侧节点的排列转换为右侧节点的排列。

初始树为：
如果 x 有右子树，则将 y 设为 x 的右子树的父节点。
如果 y 的父节点为 NULL，则使 x 成为树的根。
否则如果 y 是其父节点 p 的右孩子，将 x 设为 p 的右孩子。
否则将 x 设为 p 的左孩子。
将 x 设为 y 的父节点。

左-右旋和右-左旋

在左-右旋转中，排列首先向左移动，然后向右移动。

对 x-y 执行左旋。
对 y-z 执行右旋。

在右-左旋转中，排列首先向右移动，然后向左移动。

对 x-y 执行右旋。
对 z-y 执行左旋。

插入新节点的算法

新节点总是作为叶节点插入，其平衡因子等于 0。

初始树为：

待插入的节点为：新节点

使用以下递归步骤前往适当的叶节点以插入 newNode。将 newKey 与当前树的 rootKey 进行比较。
如果 newKey < rootKey，则对当前节点的左子树调用插入算法，直到达到叶节点。
否则如果 newKey > rootKey，则对当前节点的右子树调用插入算法，直到达到叶节点。
否则，返回 leafNode。

比较上述步骤获得的 leafKey 与 newKey：

如果 newKey < leafKey，则将 newNode 设为 leafNode 的 leftChild。
否则，将 newNode 设为 leafNode 的右孩子。

更新节点的 balanceFactor。 avl 树插入如果节点不平衡，则重新平衡该节点。

如果 balanceFactor > 1，意味着左子树的高度大于右子树的高度。因此，进行右旋转或左-右旋转。
如果 newNodeKey < leftChildKey，则进行右旋转。
否则，进行左-右旋转。

AVL 树中的插入

如果 balanceFactor < -1，意味着右子树的高度大于左子树的高度。因此，进行右旋转或右-左旋转。

如果 newNodeKey > rightChildKey，则进行左旋转。
否则，进行右-左旋转。

最终的树是：左-右插入

删除节点的算法

节点总是作为叶节点被删除。删除节点后，节点的平衡因子会发生变化。为了重新平衡平衡因子，执行适当的旋转。

定位 nodeToBeDeleted（在下面使用的代码中使用递归来查找 nodeToBeDeleted）。
删除节点有三种情况：
如果 nodeToBeDeleted 是叶节点（即没有任何子节点），则移除 nodeToBeDeleted。
如果 nodeToBeDeleted 有一个子节点，那么用子节点的内容替换 nodeToBeDeleted 的内容。移除该子节点。
如果 nodeToBeDeleted 有两个子节点，找到 nodeToBeDeleted 的中序后继 w（即右子树中键值最小的节点）。
用 w 的内容替换 nodeToBeDeleted 的内容。
移除叶节点 w。

更新节点的 balanceFactor。更新平衡因子

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

如果 currentNode 的 balanceFactor > 1，
如果 leftChild 的 balanceFactor ≥ 0，进行右旋转。
否则进行左-右旋转。

如果 currentNode 的 balanceFactor < -1，

如果 rightChild 的 balanceFactor ≤ 0，进行左旋转。
否则进行右-左旋转。

最终的树是： AVL 树

Python、Java 和 C/C++ 示例

Python 示例 Java 示例 C 示例 C++ 示例

# Python 中的 AVL 树实现


import sys

# 创建树节点
class TreeNode(object):
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1


class AVLTree(object):

    # 插入节点的函数
    def insert_node(self, root, key):

        # 找到正确的位置并插入节点
        if not root:
            return TreeNode(key)
        elif key < root.key:
            root.left = self.insert_node(root.left, key)
        else:
            root.right = self.insert_node(root.right, key)

        root.height = 1 + max(self.getHeight(root.left),
                              self.getHeight(root.right))

        # 更新平衡因子并平衡树
        balanceFactor = self.getBalance(root)
        if balanceFactor > 1:
            if key < root.left.key:
                return self.right

Rotate(root)
            else:
                root.left = self.leftRotate(root.left)
                return self.rightRotate(root)

        if balanceFactor < -1:
            if key > root.right.key:
                return self.leftRotate(root)
            else:
                root.right = self.rightRotate(root.right)
                return self.leftRotate(root)

        return root

    # 删除节点的函数
    def delete_node(self, root, key):

        # 找到要删除的节点并移除它
        if not root:
            return root
        elif key < root.key:
            root.left = self.delete_node(root.left, key)
        elif key > root.key:
            root.right = self.delete_node(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.getMinValueNode(root.right)
            root.key = temp.key
            root.right = self.delete_node(root.right,
                                          temp.key)
        if root is None:
            return root

        # 更新节点的平衡因子
        root.height = 1 + max(self.getHeight(root.left),
                              self.getHeight(root.right))

        balanceFactor = self.getBalance(root)

        # 平衡树
        if balanceFactor > 1:
            if self.getBalance(root.left) >= 0:
                return self.rightRotate(root)
            else:
                root.left = self.leftRotate(root.left)
                return self.rightRotate(root)
        if balanceFactor < -1:
            if self.getBalance(root.right) <= 0:
                return self.leftRotate(root)
            else:
                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 getMinValueNode(self, root):
        if root is None or root.left is None:
            return root
        return self.getMinValueNode(root.left)

    def preOrder(self, root):
        if not root:
            return
        print("{0} ".format(root.key), end="")
        self.preOrder(root.left)
        self.preOrder(root.right)

    # 打印树
    def printHelper(self, currPtr, indent, last):
        if currPtr != None:
            sys.stdout.write(indent)
            if last:
                sys.stdout.write("R----")
                indent += "     "
            else:
                sys.stdout.write("L----")
                indent += "|    "
            print(currPtr.key)
            self.printHelper(currPtr.left, indent, False)
            self.printHelper(currPtr.right, indent, True)


myTree = AVLTree()
root = None
nums = [33, 13, 52, 9, 21, 61, 8, 11]
for num in nums:
    root = myTree.insert_node(root, num)
myTree.printHelper(root, "", True)
key = 13
root = myTree.delete_node(root, key)
print("After Deletion: ")
myTree.printHelper(root, "", True)

// Java 中 AVL 树的实现

// 创建节点
class Node {
  int item, height;
  Node left, right;

  Node(int d) {
    item = d;
    height = 1;
  }
}

// 树类
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 getBalanceFactor(Node N) {
    if (N == null)
      return 0;
    return height(N.left) - height(N.right);
  }

  // 插入节点
  Node insertNode(Node node, int item) {

    // 查找位置并插入节点
    if (node == null)
      return (new Node(item));
    if (item < node.item)
      node.left = insertNode(node.left, item);
    else if (item > node.item)
      node.right = insertNode(node.right, item);
    else
      return node;

    // 更新每个节点的平衡因子
    // 并平衡树
    node.height = 1 + max(height(node.left), height(node.right));
    int balanceFactor = getBalanceFactor(node);
    if (balanceFactor > 1) {
      if (item < node.left.item) {
        return rightRotate(node);
      } else if (item > node.left.item) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
      }
    }
    if (balanceFactor < -1) {
      if (item > node.right.item) {
        return leftRotate(node);
      } else if (item < node.right.item) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
      }
    }
    return node;
  }

  Node nodeWithMimumValue(Node node) {
    Node current = node;
    while (current.left != null)
      current = current.left;
    return current;
  }

  // 删除节点
  Node deleteNode(Node root, int item) {

    // 查找要删除的节点并移除
    if (root == null)
      return root;
    if (item < root.item)
      root.left = deleteNode(root.left, item);
    else if (item > root.item)
      root.right = deleteNode(root.right, item);
    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 = nodeWithMimumValue(root.right);
        root.item = temp.item;
        root.right = deleteNode(root.right, temp.item);
      }
    }
    if (root == null)
      return root;

    // 更新每个节点的平衡因子并平衡树
    root.height = max(height(root.left), height(root.right)) + 1;
    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;
  }

  void preOrder(Node node) {
    if (node != null) {
      System.out.print(node.item + " ");
      preOrder(node.left);
      preOrder(node.right);
    }
  }

  // 打印树
  private void printTree

(Node currPtr, String indent, boolean last) {
    if (currPtr != null) {
      System.out.print(indent);
      if (last) {
        System.out.print("R----");
        indent += "   ";
      } else {
        System.out.print("L----");
        indent += "|  ";
      }
      System.out.println(currPtr.item);
      printTree(currPtr.left, indent, false);
      printTree(currPtr.right, indent, true);
    }
  }

  // 驱动代码
  public static void main(String[] args) {
    AVLTree tree = new AVLTree();
    tree.root = tree.insertNode(tree.root, 33);
    tree.root = tree.insertNode(tree.root, 13);
    tree.root = tree.insertNode(tree.root, 53);
    tree.root = tree.insertNode(tree.root, 9);
    tree.root = tree.insertNode(tree.root, 21);
    tree.root = tree.insertNode(tree.root, 61);
    tree.root = tree.insertNode(tree.root, 8);
    tree.root = tree.insertNode(tree.root, 11);
    tree.printTree(tree.root, "", true);
    tree.root = tree.deleteNode(tree.root, 13);
    System.out.println("删除后: ");
    tree.printTree(tree.root, "", true);
  }
}

// C 语言中的 AVL 树实现

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

// 创建节点
struct Node {
  int key;
  struct Node *left;
  struct Node *right;
  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 key) {
  struct Node *node = (struct Node *)
    malloc(sizeof(struct Node));
  node->key = key;
  node->left = NULL;
  node->right = NULL;
  node->height = 1;
  return (node);
}

// 右旋转
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;
}

// 左旋转
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;
}

// 获取平衡因子
int getBalance(struct Node *N) {
  if (N == NULL)
    return 0;
  return height(N->left) - height(N->right);
}

// 插入节点
struct Node *insertNode(struct Node *node, int key) {
  // 找到正确的位置插入节点
  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;

  // 更新每个节点的平衡因子并平衡树
  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;
}

struct Node *minValueNode(struct Node *node) {
  struct Node *current = node;

  while (current->left != NULL)
    current = current->left;

  return current;
}

// 删除节点
struct Node *deleteNode(struct 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)) {
      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;

  // 更新每个节点的平衡因子并平衡树
  root->height = 1 + max(height(root->left),
               height(root->right));

  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;
}

// 打印树
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, 2);
  root = insertNode(root, 1);
  root = insertNode(root, 7);
  root = insertNode(root, 4);
  root = insertNode(root, 5);
  root = insertNode(root, 3);
  root = insertNode(root, 8);

  printPreOrder(root);

  root = deleteNode(root, 3);

  printf("\nAfter deletion: ");
  printPreOrder(root);

  return 0;
}

// C++ 中的 AVL 树实现

#include <iostream>
using namespace std;

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

int max(int a, int b);

// 计算高度
int height(Node *N) {
  if (N == NULL)
    return 0;
  return N->height;
}

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

// 创建新节点
Node *newNode(int key) {
  Node *node = new Node();
  node->key = key;
  node->left = NULL;
  node->right = NULL;
  node->height = 1;
  return (node);
}

// 向右旋转
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 getBalanceFactor(Node *N) {
  if (N == NULL)
    return 0;
  return height(N->left) -
       height(N->right);
}

// 插入节点
Node *insertNode(Node *node, int key) {
  // 找到正确位置并插入节点
  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;

  // 更新每个节点的平衡因子并平衡树
  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->right = rightRotate(node->right);
      return leftRotate(node);
    }
  }
  return node;
}

// 具有最小值的节点
Node *nodeWithMimumValue(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 = 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;

  // 更新每个节点的平衡因子并平衡树
  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;
}

// 打印树
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 << "删除后：" << endl;
  printTree(root, "", true);
}

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

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

AVL 树的应用

用于在数据库中索引大量记录
用于在大型数据库中进行搜索

AVL树

平衡因子​

对 AVL 树的操作​

AVL 树中子树的旋转​

左旋​

右旋​

左-右旋和右-左旋​

插入新节点的算法​

删除节点的算法​

Python、Java 和 C/C++ 示例​

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

AVL 树的应用​