AVL 树原理与 C++ 实现 | 极客日志

C++算法

AVL 树原理与 C++ 实现

AVL 树是一种高度平衡的二叉搜索树，其左右子树高度差的绝对值不超过 1，从而保证增删查改的时间复杂度为 O(logN)。核心维护机制是平衡因子，即右子树高度减去左子树高度。当插入节点导致平衡因子超出 [-1, 1] 范围时，需通过左旋、右旋或双旋操作恢复平衡。内容涵盖 AVL 树的结构设计、插入逻辑及四种旋转场景的处理方法，并提供完整的 C++ 代码示例。

菩提发布于 2026/2/6更新于 2026/4/181 浏览

AVL 树原理与 C++ 实现

AVL 树

1. AVL 树

1.1 AVL 的概念

AVL 树可以是一个空树。它的左右子树都是 AVL 树，且左右子树的高度差的绝对值不超过 1。AVL 树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。

AVL 树整体结点数量和分布和完全二叉树类似，高度可以控制在 logN，那么增删查改的效率也可以控制在 O(logN)，相比普通二叉搜索树有了本质的提升。

1.2 平衡因子

结点的平衡因子 = 右子树的高度减去左子树的高度。也就是说任何结点的平衡因子等于 0、1 或 -1。AVL 树并不是必须要存储平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像一个风向标一样。

为什么 AVL 树是高度平衡搜索二叉树，要求高度差不超过 1，而不是高度差是 0 呢？因为例如两个和四个结点无法达到高度差为 0 的完全平衡状态。

2. AVL 树的实现

2.1 AVL 树的结构

template<class K, class V>
struct AVLTreeNode {
    std::pair<K, V> _kv;
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;
    int _bf; // balance factor

    AVLTreeNode(const std::pair<K, V>& kv)
        : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {}
};

template<class K, class V>
class AVLTree {
    typedef AVLTreeNode<K, V> Node;
public:
    bool Insert(const std::pair<K, V>& kv);
private:
    Node* _root = nullptr;
    void RotateLeft(Node* parent);
     ;
    ;
};

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

bool AVLTree::Insert(const std::pair<K, V>& kv) {
    if (_root == nullptr) {
        _root = new Node(kv);
        return true;
    }

    Node* parent = nullptr;
    Node* cur = _root;

    while (cur) {
        if (cur->_kv.first < kv.first) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_kv.first > kv.first) {
            parent = cur;
            cur = cur->_left;
        } else {
            return false; // Key exists
        }
    }

    cur = new Node(kv);
    if (parent->_kv.first < kv.first) {
        parent->_right = cur;
    } else {
        parent->_left = cur;
    }
    cur->_parent = parent;

    // 更新平衡因子并处理旋转
    while (parent) {
        if (cur == parent->_left) {
            parent->_bf--;
        } else {
            parent->_bf++;
        }

        if (parent->_bf == 0) {
            break; // 高度未变，无需继续向上更新
        } else if (parent->_bf == 1 || parent->_bf == -1) {
            // 高度增加，继续向上更新
            cur = parent;
            parent = parent->_parent;
        } else if (parent->_bf == 2 || parent->_bf == -2) {
            // 不平衡了，需要旋转
            if (parent->_bf == 2 && cur->_bf == 1) {
                RotateLeft(parent);
            } else if (parent->_bf == -2 && cur->_bf == -1) {
                RotateRight(parent);
            } else if (parent->_bf == 2 && cur->_bf == -1) {
                RotateLR(parent);
            } else if (parent->_bf == -2 && cur->_bf == 1) {
                RotateRL(parent);
            }
            break;
        } else {
            assert(false);
        }
    }
    return true;
}

void AVLTree::RotateLeft(Node* parent) {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    Node* ppNode = parent->_parent;
    parent->_right = subRL;
    if (subRL) subRL->_parent = parent;

    subR->_left = parent;
    parent->_parent = subR;

    if (ppNode == nullptr) {
        _root = subR;
        subR->_parent = nullptr;
    } else {
        if (ppNode->_left == parent) ppNode->_left = subR;
        else ppNode->_right = subR;
        subR->_parent = ppNode;
    }

    // 更新平衡因子
    parent->_bf = 0;
    subR->_bf = 0;
}

void AVLTree::RotateRight(Node* parent) {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;

    Node* ppNode = parent->_parent;
    parent->_left = subLR;
    if (subLR) subLR->_parent = parent;

    subL->_right = parent;
    parent->_parent = subL;

    if (ppNode == nullptr) {
        _root = subL;
        subL->_parent = nullptr;
    } else {
        if (ppNode->_left == parent) ppNode->_left = subL;
        else ppNode->_right = subL;
        subL->_parent = ppNode;
    }

    parent->_bf = 0;
    subL->_bf = 0;
}

void AVLTree::RotateLR(Node* parent) {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;

    RotateLeft(subL);
    RotateRight(parent);

    if (bf == 1) {
        subL->_bf = 0;
        parent->_bf = -1;
    } else if (bf == -1) {
        subL->_bf = 1;
        parent->_bf = 0;
    } else {
        subL->_bf = 0;
        parent->_bf = 0;
    }
    subLR->_bf = 0;
}

void AVLTree::RotateRL(Node* parent) {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;

    RotateRight(subR);
    RotateLeft(parent);

    if (bf == 1) {
        subR->_bf = 0;
        parent->_bf = 1;
    } else if (bf == -1) {
        subR->_bf = -1;
        parent->_bf = 0;
    } else {
        subR->_bf = 0;
        parent->_bf = 0;
    }
    subRL->_bf = 0;
}