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);
    void RotateRight(Node* parent);
    void UpdateBF(Node* node);
};

2.2 AVL 树的插入

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

2.3 旋转

2.3.1 旋转的原则

1. 保持搜索树的规则（中序遍历有序）。
2. 让旋转的树从不满足平衡条件变为平衡，其次降低旋转树的高度。

旋转总共分为四种：左单旋、右单旋、左右双旋、右左双旋。

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