AVL树删除操作导致遍历结果不正确
创始人
2024-11-13 02:00:17
0

在AVL树的删除操作中,需要重新平衡树以确保树的平衡性。在节点删除后,需要从被删除节点的父节点开始向上遍历,检查子树的平衡因子是否失衡,并进行旋转操作以保持平衡。同时,在进行旋转操作时需要更新节点的高度信息。

下面是一个AVL树的删除操作的示例代码(假设节点类型为Node,节点高度信息在节点结构体中的height属性中存储):

Node* deleteNode(Node* root, int key) {
    if (!root) return NULL;
    
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        if (!root->left || !root->right) {
            Node* tmp = root->left ? root->left : root->right;
            if (!tmp) {
                tmp = root;
                root = NULL;
            } else {
                *root = *tmp;
            }
            delete tmp;
        } else {
            Node* cur = root->right;
            while (cur->left) {
                cur = cur->left;
            }
            root->val = cur->val;
            root->right = deleteNode(root->right, cur->val);
        }
    }
    
    if (!root) return NULL;

    root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
    int balance = getBalanceFactor(root);
    
    if (balance > 1 && getBalanceFactor(root->left) >= 0) {
        return rightRotate(root);
    }
    
    if (balance > 1 && getBalanceFactor(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    
    if (balance < -1 && getBalanceFactor(root->right) <= 0) {
        return leftRotate(root);
    }
    
    if (balance < -1 && getBalanceFactor(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    
    return root;
}

相关内容

热门资讯

盘点一款!pokemmo内置修... 盘点一款!pokemmo内置修改器(辅助挂)总是真的有挂(发现有挂辅助插件)1、下载好正确养号方法之...
我来教大家!aa poker辅... 我来教大家!aa poker辅助包(辅助挂)竟然是真的有挂(今日头条辅助插件)1、每一步都需要思考,...
今日重大通报!agpoker辅... 今日重大通报!agpoker辅助(辅助挂)确实有挂(有挂教学辅助攻略)1、这是跨平台的轻量版有透视,...
一分钟揭秘!wpk有作弊吗(辅... 一分钟揭秘!wpk有作弊吗(辅助挂)真是真的有挂(有挂规律辅助攻略)1、实时透视辅助更新:用户可以随...
重大通报!德普之星透视辅助插件... 重大通报!德普之星透视辅助插件(辅助挂)本来有挂(有挂总结辅助软件)该软件可以轻松地帮助玩家将外卦神...
普及知识!wepoker黑侠辅... 普及知识!wepoker黑侠辅助器(辅助挂)果然是有挂(有挂功能辅助插件)1、任何透视是真的假的的玩...
重大科普!wpk俱乐部辅助器(... 重大科普!wpk俱乐部辅助器(辅助挂)竟然有挂(有挂技术辅助插件)小薇(辅助器软件下载)致您一封信;...
如何分辨真伪!如何下载wpk透... 如何分辨真伪!如何下载wpk透视版(辅助挂)原来真的是有挂(有挂攻略辅助插件)1、免费辅助多个强度级...
揭秘几款!wepoker看底牌... 揭秘几款!wepoker看底牌(辅助挂)真是是真的有挂(有挂详情辅助工具)破解侠是真的助透视。每个模...
一分钟揭秘!pokemomo辅... 一分钟揭秘!pokemomo辅助工具(辅助挂)都是是有挂(有挂存在辅助教程)能透视中分为三种模型:模...