avl树算法实现

AVL树是一种自平衡二叉搜索树，其每个节点的左子树和右子树的高度差（平衡因子）最多为1。当插入或删除节点导致不平衡时，AVL树会通过旋转操作来重新平衡。

下面是AVL树的算法实现：

定义AVL树节点结构，包括键值、左右子树指针和平衡因子。

struct AVLNode {
    int key;
    int bf; // 平衡因子
    AVLNode* left;
    AVLNode* right;
};

定义AVL树类，包括插入、删除、查找和遍历等操作。

class AVLTree {
public:
    AVLTree();
    ~AVLTree();
    void insert(int key);
    void remove(int key);
    bool search(int key) const;
    void inorderTraversal() const;
private:
    AVLNode* root;
    AVLNode* insertNode(AVLNode* node, int key);
    AVLNode* removeNode(AVLNode* node, int key);
    AVLNode* findMinNode(AVLNode* node) const;
    AVLNode* rotateLeft(AVLNode* node);
    AVLNode* rotateRight(AVLNode* node);
    AVLNode* rotateLeftRight(AVLNode* node);
    AVLNode* rotateRightLeft(AVLNode* node);
    void updateBalanceFactor(AVLNode* node);
    void rebalance(AVLNode* node);
    void destroyTree(AVLNode* node);
};

实现插入节点操作。

AVLNode* AVLTree::insertNode(AVLNode* node, int key) {
    if (node == nullptr) {
        node = new AVLNode;
        node->key = key;
        node->bf = 0;
        node->left = nullptr;
        node->right = nullptr;
    }
    else if (key < node->key) {
        node->left = insertNode(node->left, key);
        updateBalanceFactor(node);
        rebalance(node);
    }
    else if (key > node->key) {
        node->right = insertNode(node->right, key);
        updateBalanceFactor(node);
        rebalance(node);
    }
    return node;
}

void AVLTree::insert(int key) {
    root = insertNode(root, key);
}

实现删除节点操作。

AVLNode* AVLTree::removeNode(AVLNode* node, int key) {
    if (node == nullptr) {
        return nullptr;
    }
    if (key < node->key) {
        node->left = removeNode(node->left, key);
        updateBalanceFactor(node);
        rebalance(node);
    }
    else if (key > node->key) {
        node->right = removeNode(node->right, key);
        updateBalanceFactor(node);
        rebalance(node);
    }
    else {
        if (node->left == nullptr && node->right == nullptr) {
            delete node;
            node = nullptr;
        }
        else if (node->left == nullptr) {
            AVLNode* temp = node;
            node = node->right;
            delete temp;
        }
        else if (node->right == nullptr) {
            AVLNode* temp = node;
            node = node->left;
            delete temp;
        }
        else {
            AVLNode* minNode = findMinNode(node->right);
            node->key = minNode->key;
            node->right = removeNode(node->right, minNode->key);
            updateBalanceFactor(node);
            rebalance(node);
        }
    }
    return node;
}

void AVLTree::remove(int key) {
    root = removeNode(root, key);
}

实现查找节点操作。

bool AVLTree::search(int key) const {
    AVLNode* node = root;
    while (node != nullptr) {
        if (key == node->key) {
            return true;
        }
        else if (key < node->key) {
            node = node->left;
        }
        else {
            node = node->right;
        }
    }
    return false;
}

实现中序遍历操作。

void AVLTree::inorderTraversal() const {
    stack<AVLNode*> s;
    AVLNode* node = root;
    while (node != nullptr || !s.empty()) {
        while (node != nullptr) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        s.pop();
        cout << node->key << " ";
        node = node->right;
    }
}

实现旋转操作。

AVLNode* AVLTree::rotateLeft(AVLNode* node) {
    AVLNode* right = node->right;
    node->right = right->left;
    right->left = node;
    updateBalanceFactor(node);
    updateBalanceFactor(right);
    return right;
}

AVLNode* AVLTree::rotateRight(AVLNode* node) {
    AVLNode* left = node->left;
    node->left = left->right;
    left->right = node;
    updateBalanceFactor(node);
    updateBalanceFactor(left);
    return left;
}

AVLNode* AVLTree::rotateLeftRight(AVLNode* node) {
    node->left = rotateLeft(node->left);
    return rotateRight(node);
}

AVLNode* AVLTree::rotateRightLeft(AVLNode* node) {
    node->right = rotateRight(node->right);
    return rotateLeft(node);
}

实现更新平衡因子和重新平衡操作。

void AVLTree::updateBalanceFactor(AVLNode* node) {
    int leftHeight = (node->left != nullptr) ? node->left->bf + 1 : 0;
    int rightHeight = (node->right != nullptr) ? node->right->bf + 1 : 0;
    node->bf = rightHeight - leftHeight;
}

void AVLTree::rebalance(AVLNode* node) {
    if (node->bf == -2) {
        if (node->left->bf == 1) {
            node = rotateLeftRight(node);
        }
        else {
            node = rotateRight(node);
        }
    }
    else if (node->bf == 2) {
        if (node->right->bf == -1) {
            node = rotateRightLeft(node);
        }
        else {
            node = rotateLeft(node);
        }
    }
    if (node->left != nullptr) {
        rebalance(node->left);
    }
    if (node->right != nullptr) {
        rebalance(node->right);
    }
}

实现析构函数。

void AVLTree::destroyTree(AVLNode* node) {
    if (node != nullptr) {
        destroyTree(node->left);
        destroyTree(node->right);
        delete node;
    }
}

AVLTree::~AVLTree() {
    destroyTree(root);
}

这样，AVL树的算法实现就完成了。