AVL 树深度解析：从原理到实战，打造平衡二叉搜索树的终极指南

果酱带你啃java

发布于 2026-04-14 13:45:40

310

AVL树深度解析：从原理到实战，打造平衡二叉搜索树的终极指南

引言：为什么需要AVL树？

二叉搜索树（BST）是一种高效的有序数据结构，支持O(logn)时间复杂度的查找、插入和删除操作——但这有个前提：树必须是“平衡”的。如果插入一组有序数据（比如1,2,3,4,5），BST会退化成一条链表，此时所有操作的时间复杂度骤降至O(n)，性能大打折扣。

为解决这个问题，计算机科学家们设计了自平衡二叉搜索树，而AVL树是其中最早、最经典的实现（由Adelson-Velsky和Landis在1962年提出）。它通过严格的高度平衡规则和旋转操作，确保树始终保持“矮胖”形态，彻底避免了链表退化问题。

一、AVL树的核心定义与特性

AVL树本质上是一棵二叉搜索树，但额外满足：每个节点的左右子树高度差（平衡因子）的绝对值不超过1。

1.1 平衡因子

平衡因子（Balance Factor, BF）的计算公式为： 平衡因子 = 左子树高度 - 右子树高度

根据AVL树的定义，所有节点的平衡因子只能是**-1、0、1**。若某个节点的平衡因子绝对值大于1（即2或-2），则树失衡，需要通过旋转调整。

1.2 节点高度的定义

空节点（null）的高度为0；
叶子节点的高度为1；
非叶子节点的高度 = max(左子树高度, 右子树高度) + 1。

因此，AVL树的节点必须维护“高度”属性，这是实现平衡的基础。

二、AVL树的核心操作：旋转

旋转是AVL树保持平衡的关键，本质是通过调整节点的父子关系，将失衡的子树恢复平衡。根据失衡位置的不同，旋转分为四种类型：LL（右旋转）、RR（左旋转）、LR（先左后右）、RL（先右后左）。

2.1 基础旋转：LL（右旋转）

适用场景

节点的左子树的左子树插入新节点，导致该节点平衡因子=2（比如节点A的BF=2，左孩子B的BF=1）。

旋转原理

将失衡节点的左孩子提升为新根，失衡节点作为新根的右孩子，新根原右子树转为失衡节点的左子树。

流程图（LL旋转）

代码实现（右旋转）

/**
 * 右旋转操作（处理LL型失衡）
 * @param node 失衡节点
 * @return 旋转后的新根节点
 * @author ken
 */
private AVLNode<K, V> rightRotate(AVLNode<K, V> node) {
    if (ObjectUtils.isEmpty(node) || ObjectUtils.isEmpty(node.left)) {
        return node;
    }
    AVLNode<K, V> leftChild = node.left; // 失衡节点的左孩子（新根）
    AVLNode<K, V> leftChildRight = leftChild.right; // 新根的右子树

    // 执行旋转：新根的右子树指向原失衡节点，原失衡节点的左子树指向新根的原右子树
    leftChild.right = node;
    node.left = leftChildRight;

    // 更新节点高度（先更新原失衡节点，再更新新根）
    updateHeight(node);
    updateHeight(leftChild);

    return leftChild; // 返回新根
}

2.2 基础旋转：RR（左旋转）

适用场景

节点的右子树的右子树插入新节点，导致该节点平衡因子=-2（比如节点A的BF=-2，右孩子C的BF=-1）。

旋转原理

将失衡节点的右孩子提升为新根，失衡节点作为新根的左孩子，新根原左子树转为失衡节点的右子树。

流程图（RR旋转）

代码实现（左旋转）

/**
 * 左旋转操作（处理RR型失衡）
 * @param node 失衡节点
 * @return 旋转后的新根节点
 * @author ken
 */
private AVLNode<K, V> leftRotate(AVLNode<K, V> node) {
    if (ObjectUtils.isEmpty(node) || ObjectUtils.isEmpty(node.right)) {
        return node;
    }
    AVLNode<K, V> rightChild = node.right; // 失衡节点的右孩子（新根）
    AVLNode<K, V> rightChildLeft = rightChild.left; // 新根的左子树

    // 执行旋转：新根的左子树指向原失衡节点，原失衡节点的右子树指向新根的原左子树
    rightChild.left = node;
    node.right = rightChildLeft;

    // 更新节点高度
    updateHeight(node);
    updateHeight(rightChild);

    return rightChild; // 返回新根
}

2.3 复合旋转：LR（先左后右）

适用场景

节点的左子树的右子树插入新节点，导致该节点平衡因子=2（比如节点A的BF=2，左孩子B的BF=-1）。

旋转原理

先对失衡节点的左孩子执行左旋转（RR），将结构转为LL型，再对失衡节点执行右旋转（LL）。

流程图（LR旋转）

代码实现（LR旋转）

/**
 * 处理LR型失衡（先左旋转左孩子，再右旋转当前节点）
 * @param node 失衡节点
 * @return 调整后的新根节点
 * @author ken
 */
private AVLNode<K, V> handleLR(AVLNode<K, V> node) {
    node.left = leftRotate(node.left); // 先对左孩子左旋转
    return rightRotate(node); // 再对当前节点右旋转
}

2.4 复合旋转：RL（先右后左）

适用场景

节点的右子树的左子树插入新节点，导致该节点平衡因子=-2（比如节点A的BF=-2，右孩子C的BF=1）。

旋转原理

先对失衡节点的右孩子执行右旋转（LL），将结构转为RR型，再对失衡节点执行左旋转（RR）。

代码实现（RL旋转）

/**
 * 处理RL型失衡（先右旋转右孩子，再左旋转当前节点）
 * @param node 失衡节点
 * @return 调整后的新根节点
 * @author ken
 */
private AVLNode<K, V> handleRL(AVLNode<K, V> node) {
    node.right = rightRotate(node.right); // 先对右孩子右旋转
    return leftRotate(node); // 再对当前节点左旋转
}

三、AVL树的完整实现

3.1 节点定义

/**
 * AVL树节点类
 * @param <K> 键类型（需实现Comparable接口）
 * @param <V> 值类型
 * @author ken
 */
private static class AVLNode<K extends Comparable<K>, V> {
    K key; // 键（用于排序）
    V value; // 值
    AVLNode<K, V> left; // 左子节点
    AVLNode<K, V> right; // 右子节点
    int height; // 节点高度（叶子节点初始为1）

    public AVLNode(K key, V value) {
        this.key = key;
        this.value = value;
        this.height = 1; // 新节点默认高度为1
    }
}

3.2 核心工具方法

/**
 * 获取节点高度（空节点高度为0）
 * @param node 目标节点
 * @return 节点高度
 * @author ken
 */
private int getHeight(AVLNode<K, V> node) {
    return node == null ? 0 : node.height;
}

/**
 * 更新节点高度
 * @param node 目标节点
 * @author ken
 */
private void updateHeight(AVLNode<K, V> node) {
    if (ObjectUtils.isEmpty(node)) {
        return;
    }
    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}

/**
 * 计算节点平衡因子（左子树高度-右子树高度）
 * @param node 目标节点
 * @return 平衡因子
 * @author ken
 */
private int getBalanceFactor(AVLNode<K, V> node) {
    return node == null ? 0 : getHeight(node.left) - getHeight(node.right);
}

3.3 插入操作

AVL树的插入逻辑基于BST，但插入后需回溯检查平衡因子，若失衡则执行旋转：

/**
 * 插入键值对
 * @param key 键
 * @param value 值
 * @author ken
 */
public void put(K key, V value) {
    if (ObjectUtils.isEmpty(key)) {
        throw new IllegalArgumentException("Key cannot be null");
    }
    root = insert(root, key, value);
}

/**
 * 递归插入节点（BST逻辑+平衡调整）
 * @param node 当前子树根节点
 * @param key 键
 * @param value 值
 * @return 调整后的子树根节点
 * @author ken
 */
private AVLNode<K, V> insert(AVLNode<K, V> node, K key, V value) {
    // 1. BST插入逻辑
    if (node == null) {
        size++; // 节点数+1
        return new AVLNode<>(key, value);
    }

    int compare = key.compareTo(node.key);
    if (compare < 0) {
        node.left = insert(node.left, key, value);
    } else if (compare > 0) {
        node.right = insert(node.right, key, value);
    } else {
        // 键已存在，更新值
        node.value = value;
        return node;
    }

    // 2. 更新当前节点高度
    updateHeight(node);

    // 3. 计算平衡因子，处理失衡
    int balanceFactor = getBalanceFactor(node);

    // LL型：BF>1且左孩子BF>=0
    if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
        return rightRotate(node);
    }
    // RR型：BF<-1且右孩子BF<=0
    if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
        return leftRotate(node);
    }
    // LR型：BF>1且左孩子BF<0
    if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
        return handleLR(node);
    }
    // RL型：BF<-1且右孩子BF>0
    if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
        return handleRL(node);
    }

    // 未失衡，返回原节点
    return node;
}

3.4 删除操作

删除操作比插入更复杂，因为删除节点后可能导致上层节点失衡，需递归回溯调整：

/**
 * 删除指定键的节点
 * @param key 键
 * @author ken
 */
public void remove(K key) {
    if (ObjectUtils.isEmpty(key)) {
        throw new IllegalArgumentException("Key cannot be null");
    }
    root = remove(root, key);
}

/**
 * 递归删除节点（BST逻辑+平衡调整）
 * @param node 当前子树根节点
 * @param key 键
 * @return 调整后的子树根节点
 * @author ken
 */
private AVLNode<K, V> remove(AVLNode<K, V> node, K key) {
    if (node == null) {
        return null;
    }

    AVLNode<K, V> retNode;
    int compare = key.compareTo(node.key);
    if (compare < 0) {
        node.left = remove(node.left, key);
        retNode = node;
    } else if (compare > 0) {
        node.right = remove(node.right, key);
        retNode = node;
    } else {
        // 找到目标节点，处理三种删除情况
        if (node.left == null) {
            size--;
            retNode = node.right; // 情况1：无左子树，返回右子树
        } else if (node.right == null) {
            size--;
            retNode = node.left; // 情况2：无右子树，返回左子树
        } else {
            // 情况3：有左右子树，找后继节点（右子树最小值）替代
            AVLNode<K, V> successor = minimum(node.right);
            successor.right = remove(node.right, successor.key); // 删除后继节点
            successor.left = node.left;
            node.left = null;
            node.right = null;
            retNode = successor;
        }
    }

    // 删除后子树为空，直接返回
    if (retNode == null) {
        return null;
    }

    // 更新高度并处理失衡
    updateHeight(retNode);
    int balanceFactor = getBalanceFactor(retNode);

    // 失衡处理逻辑与插入一致
    if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) {
        return rightRotate(retNode);
    }
    if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) {
        return leftRotate(retNode);
    }
    if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
        return handleLR(retNode);
    }
    if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
        return handleRL(retNode);
    }

    return retNode;
}

/**
 * 查找右子树的最小值节点（后继节点）
 * @param node 目标节点
 * @return 最小值节点
 * @author ken
 */
private AVLNode<K, V> minimum(AVLNode<K, V> node) {
    if (ObjectUtils.isEmpty(node)) {
        return null;
    }
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

3.5 查找与遍历

/**
 * 根据键查找值
 * @param key 键
 * @return 值（不存在返回null）
 * @author ken
 */
public V get(K key) {
    if (ObjectUtils.isEmpty(key)) {
        throw new IllegalArgumentException("Key cannot be null");
    }
    return get(root, key);
}

private V get(AVLNode<K, V> node, K key) {
    if (node == null) {
        return null;
    }
    int compare = key.compareTo(node.key);
    if (compare < 0) {
        return get(node.left, key);
    } else if (compare > 0) {
        return get(node.right, key);
    } else {
        return node.value;
    }
}

/**
 * 中序遍历（升序输出键值对）
 * @return 有序键值对列表
 * @author ken
 */
public List<Entry<K, V>> inOrder() {
    List<Entry<K, V>> list = Lists.newArrayList();
    inOrder(root, list);
    return list;
}

private void inOrder(AVLNode<K, V> node, List<Entry<K, V>> list) {
    if (node == null) {
        return;
    }
    inOrder(node.left, list);
    list.add(new Entry<>(node.key, node.value));
    inOrder(node.right, list);
}

/**
 * 键值对实体类
 * @author ken
 */
public static class Entry<K, V> {
    private K key;
    private V value;

    public Entry(K key, V value) {
        this.key = key;
        this.value = value;
    }

    // getter方法
    public K getKey() { return key; }
    public V getValue() { return value; }
}

四、实战：基于AVL树的有序用户管理系统

我们将AVL树集成到Spring Boot项目中，实现用户数据的有序存储和高效查询，并通过MyBatis-Plus操作数据库，Swagger3提供接口文档。

4.1 项目依赖（pom.xml）

<dependencies>
    <!-- Spring Boot Web -->
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-web</artifactId>
        <version>3.2.5</version>
    </dependency>

    <!-- MyBatis-Plus -->
    <dependency>
        <groupId>com.baomidou</groupId>
        <artifactId>mybatis-plus-boot-starter</artifactId>
        <version>3.5.5</version>
    </dependency>

    <!-- MySQL驱动 -->
    <dependency>
        <groupId>com.mysql</groupId>
        <artifactId>mysql-connector-j</artifactId>
        <version>8.3.0</version>
        <scope>runtime</scope>
    </dependency>

    <!-- Lombok -->
    <dependency>
        <groupId>org.projectlombok</groupId>
        <artifactId>lombok</artifactId>
        <version>1.18.30</version>
        <scope>provided</scope>
    </dependency>

    <!-- Swagger3 -->
    <dependency>
        <groupId>org.springdoc</groupId>
        <artifactId>springdoc-openapi-starter-webmvc-ui</artifactId>
        <version>2.3.0</version>
    </dependency>

    <!-- Guava -->
    <dependency>
        <groupId>com.google.guava</groupId>
        <artifactId>guava</artifactId>
        <version>33.2.1-jre</version>
    </dependency>

    <!-- Fastjson2 -->
    <dependency>
        <groupId>com.alibaba.fastjson2</groupId>
        <artifactId>fastjson2</artifactId>
        <version>2.0.53</version>
    </dependency>
</dependencies>

4.2 用户实体类

import com.baomidou.mybatisplus.annotation.IdType;
import com.baomidou.mybatisplus.annotation.TableId;
import com.baomidou.mybatisplus.annotation.TableName;
import lombok.Data;

@Data
@TableName("user")
public class User {
    @TableId(type = IdType.AUTO)
    private Long id; // 用户ID（作为AVL树的键）
    private String username; // 用户名
    private Integer age; // 年龄
    private String email; // 邮箱
}

4.3 Mapper与Service层

// UserMapper.java
import com.baomidou.mybatisplus.core.mapper.BaseMapper;
import org.apache.ibatis.annotations.Mapper;

@Mapper
public interface UserMapper extends BaseMapper<User> {}

// UserService.java
import com.baomidou.mybatisplus.extension.service.IService;

public interface UserService extends IService<User> {}

// UserServiceImpl.java
import com.baomidou.mybatisplus.extension.service.impl.ServiceImpl;
import lombok.extern.slf4j.Slf4j;
import org.springframework.stereotype.Service;

@Slf4j
@Service
public class UserServiceImpl extends ServiceImpl<UserMapper, User> implements UserService {}

4.4 控制器层（提供API接口）

import io.swagger.v3.oas.annotations.Operation;
import io.swagger.v3.oas.annotations.Parameter;
import io.swagger.v3.oas.annotations.tags.Tag;
import lombok.RequiredArgsConstructor;
import lombok.extern.slf4j.Slf4j;
import org.springframework.web.bind.annotation.*;

import java.util.List;

@Slf4j
@RestController
@RequestMapping("/avl/user")
@RequiredArgsConstructor
@Tag(name = "AVL树用户管理接口", description = "基于AVL树的用户增删改查")
public class AVLUserController {
    private final UserService userService;
    private final AVLTreeMap<Long, User> avlTreeMap = new AVLTreeMap<>();

    @Operation(summary = "新增用户", description = "保存用户到数据库并插入AVL树")
    @PostMapping
    public String addUser(@RequestBody User user) {
        if (userService.save(user)) {
            avlTreeMap.put(user.getId(), user);
            return "新增成功，AVL树节点数：" + avlTreeMap.size();
        }
        return "新增失败";
    }

    @Operation(summary = "删除用户", description = "从数据库和AVL树中删除用户")
    @DeleteMapping("/{id}")
    public String deleteUser(@Parameter(description = "用户ID") @PathVariable Long id) {
        if (userService.removeById(id)) {
            avlTreeMap.remove(id);
            return "删除成功，AVL树节点数：" + avlTreeMap.size();
        }
        return "删除失败";
    }

    @Operation(summary = "查询用户", description = "从AVL树中查询用户")
    @GetMapping("/{id}")
    public User getUser(@Parameter(description = "用户ID") @PathVariable Long id) {
        return avlTreeMap.get(id);
    }

    @Operation(summary = "有序列出所有用户", description = "中序遍历AVL树返回升序用户列表")
    @GetMapping("/list")
    public List<AVLTreeMap.Entry<Long, User>> listUsers() {
        return avlTreeMap.inOrder();
    }
}

4.5 测试效果

新增用户：调用POST /avl/user插入用户ID为1、2、3的用户；
有序列表：调用GET /avl/user/list，返回结果按ID升序排列（AVL树中序遍历特性）；
删除用户：调用DELETE /avl/user/2后，AVL树自动调整平衡，查询效率保持O(logn)。

五、AVL树的性能分析与适用场景

5.1 时间复杂度

查找：O(logn)（树高度严格为log₂n + 1）；
插入/删除：O(logn)（旋转操作是O(1)，递归回溯是O(logn)）。

5.2 空间复杂度

O(n)（存储n个节点及高度信息）。

5.3 AVL树 vs 红黑树

特性	AVL树	红黑树
平衡要求	严格平衡（BF∈{-1,0,1}）	近似平衡（黑高一致）
旋转次数	插入最多2次，删除最多logn次	插入最多2次，删除最多3次
查询效率	更高（树更矮）	稍低（树略高）
插入/删除效率	稍低（旋转频繁）	更高（旋转更少）
适用场景	查询密集型场景	插入/删除密集型场景

六、总结

AVL树是平衡二叉搜索树的开山之作，通过“平衡因子+旋转”机制保证了严格的高度平衡，实现了O(logn)的高效操作。尽管在插入/删除时旋转次数略多，但它的严格平衡性使其在查询密集型场景（如数据库索引、缓存系统）中表现优异。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2025-11-25，如有侵权请联系 cloudcommunity@tencent.com 删除

key

本文分享自果酱带你啃java 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度

AVL 树深度解析：从原理到实战，打造平衡二叉搜索树的终极指南

AVL 树深度解析：从原理到实战，打造平衡二叉搜索树的终极指南

AVL树深度解析：从原理到实战，打造平衡二叉搜索树的终极指南

引言：为什么需要AVL树？

一、AVL树的核心定义与特性

1.1 平衡因子

1.2 节点高度的定义

二、AVL树的核心操作：旋转

2.1 基础旋转：LL（右旋转）

适用场景

旋转原理

流程图（LL旋转）

代码实现（右旋转）

2.2 基础旋转：RR（左旋转）

适用场景

旋转原理

流程图（RR旋转）

代码实现（左旋转）

2.3 复合旋转：LR（先左后右）

适用场景

旋转原理

流程图（LR旋转）

代码实现（LR旋转）

2.4 复合旋转：RL（先右后左）

适用场景

旋转原理

代码实现（RL旋转）

三、AVL树的完整实现

3.1 节点定义

3.2 核心工具方法

3.3 插入操作

3.4 删除操作

3.5 查找与遍历

四、实战：基于AVL树的有序用户管理系统

4.1 项目依赖（pom.xml）

4.2 用户实体类

4.3 Mapper与Service层

4.4 控制器层（提供API接口）

4.5 测试效果

五、AVL树的性能分析与适用场景

5.1 时间复杂度

5.2 空间复杂度

5.3 AVL树 vs 红黑树

六、总结

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐