AVL树

1. 两种旋转方式

1.1 左旋

STATIC AVL_TREE_NODE *rotate_left(AVL_TREE_NODE *x)
{
    AVL_TREE_NODE *y = x->right_child;
    AVL_TREE_NODE *z = y->left_child;

    y->left_child = x;
    x->right_child = z;

    update_height(x);
    update_height(y);
    return y;
}

1.2 右旋

STATIC AVL_TREE_NODE *rotate_right(AVL_TREE_NODE *x)
{
    AVL_TREE_NODE *y = x->left_child;
    AVL_TREE_NODE *z = y->right_child;

    y->right_child = x;
    x->left_child = z;

    update_height(x);
    update_height(y);
    return x;
}

2. 调整方式

如下图所示，当插入或删除节点时，会出现四种失衡方式，具体如下：

注： V节点是为了方便演示旋转操作的虚拟节点。

2.1 LL型失衡–直接右旋

2.2 RR型失衡–直接左旋

2.3 LR型失衡–先左旋，再右旋

2.4 RL型–先右旋，再左旋

STATIC AVL_TREE_NODE *balance_node(AVL_TREE_NODE *node)
{
    update_height(node);
    INT32 bf = balance_factor(node);

    if (bf > 1) {
        if (balance_factor(node->left_child) < 0) {
            node->left_child = rotate_left(node->left_child);
        }
        return rotate_right(node);
    }
    if (bf < -1) {
        if (balance_factor(node->right_child) > 0) {
            node->right_child = rotate_right(node->right_child);
        }
        return rotate_left(node);
    }
    return node;
}

3. 插入节点

从根节点开始，比较待插入节点和当前节点的key值，来确定插入当前节点的左子树还是右子树，直到找到合适的位置插入该节点，然后对这个被插入的分支上的节点从低到高依次检查平衡性，如果发现某个节点失衡了，使用上述的平衡方法调整节点

STATIC AVL_TREE_NODE *insert_node(AVL_TREE_NODE *root, AVL_TREE_NODE *newNode, AVL_TREE_CMP_FUNC cmpFunc)
{
    if (root == NULL) {
        return newNode;
    }

    INT32 cmp = cmpFunc(AVL_TO_PAIR(newNode)->key, AVL_TO_PAIR(root)->key);
    if (cmp < 0) {
        root->left_child = insert_node(root->left_child, newNode, cmpFunc);
    } else if (cmp > 0) {
        root->right_child = insert_node(root->right_child, newNode, cmpFunc);
    } else {
        return root;
    }

    return balance_node(root);
}

4. 删除节点

从根节点开始，比较待删除节点和当前节点的key值，来确定待删除节点在当前节点的左子树还是右子树，直到找到待删除节点或者未找到。根据待删除节点的子树情况，分为如下两种情况：
注：删除节点后需要调整平衡

4.1 待删除节点存在空子树（左右子树中至少一个是空）

直接将待删除节点的非空子树取代当前节点即可（若两个子树都是空，那就是空）

4.2 待删除节点存在非空子树

STATIC AVL_TREE_NODE *remove_node(AVL_TREE_NODE *root, CONST VOID *key, AVL_TREE_CMP_FUNC cmpFunc)
{
    if (root == NULL) {
        return NULL;
    }

    INT32 cmp = cmpFunc(key, AVL_TO_PAIR(root)->key);
    if (cmp < 0) {
        root->left_child = remove_node(root->left_child, key, cmpFunc);
    } else if (cmp > 0) {
        root->right_child = remove_node(root->right_child, key, cmpFunc);
    } else {
        if (root->left_child == NULL || root->right_child == NULL) {
            AVL_TREE_NODE *temp = root->left_child ? root->left_child : root->right_child;
            AVL_PAIR_TREE_NODE *pair = AVL_TO_PAIR(root);
            free(pair->key);
            free(pair->value);
            free(pair);
            return temp;
        } else {
            AVL_TREE_NODE *temp = find_min_node(root->right_child);
            AVL_PAIR_TREE_NODE *dst = AVL_TO_PAIR(root);
            AVL_PAIR_TREE_NODE *src = AVL_TO_PAIR(temp);
            free(dst->key);
            free(dst->value);
            dst->key = src->key;
            dst->value = src->value;
            src->key = NULL;
            src->value = NULL;
            root->right_child = remove_min_node(root->right_child);
        }
    }

    return balance_node(root);
}

STATIC AVL_TREE_NODE *remove_min_node(AVL_TREE_NODE *root)
{
    if (root->left_child == NULL) {
        AVL_PAIR_TREE_NODE *pair = AVL_TO_PAIR(root);
        free(pair->key);
        free(pair->value);
        free(pair);
        return root->right_child;
    }
    root->left_child = remove_min_node(root->left_child);
    return balance_node(root);
}

菜单

分享