实现（平衡）二叉排序树的各种算法代码

以下是实现平衡二叉排序树（AVL树）的各种算法的C语言代码示例。

注：平衡二叉排序树的左子树和右子树的高度差不能超过1，以保证树的平衡。

1. AVL树节点结构体定义

struct AVLNode {
    int data;
    struct AVLNode* left;
    struct AVLNode* right;
    int height;
};

我们定义了一个结构体 `AVLNode` 表示AVL树节点。其中 `data` 表示节点的数据，`left` 表示左子节点，`right` 表示右子节点，`height` 表示节点的高度。

2. 计算节点高度

int height(struct AVLNode* node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

我们定义了一个 `height` 函数，用于计算节点的高度。若节点为空，返回0，否则返回节点的 `height` 成员变量。

3. 计算节点平衡因子

int balanceFactor(struct AVLNode* node) {
    if (node == NULL) {
        return 0;
    }
    return height(node->left) - height(node->right);
}

我们定义了一个 `balanceFactor` 函数，用于计算节点的平衡因子。平衡因子等于节点的左子树高度减去右子树高度。

4. 更新节点高度

void updateHeight(struct AVLNode* node) {
    node->height = 1 + max(height(node->left), height(node->right));
}

我们定义了一个 `updateHeight` 函数，用于更新节点的高度。节点的高度等于其左右子树高度的较大值加1。

5. 左旋转

struct AVLNode* leftRotate(struct AVLNode* node) {
    struct AVLNode* rightChild = node->right;
    struct AVLNode* leftGrandChild = rightChild->left;
    rightChild->left = node;
    node->right = leftGrandChild;
    updateHeight(node);
    updateHeight(rightChild);
    return rightChild;
}

我们定义了一个 `leftRotate` 函数，用于实现左旋转。左旋转操作将当前节点的右子节点变为新的根节点，当前节点变为新根节点的左子节点，而新根节点的左子节点变为当前节点的右子节点。然后更新当前节点和新根节点的高度，并返回新根节点。

6. 右旋转

struct AVLNode* rightRotate(struct AVLNode* node) {
    struct AVLNode* leftChild = node->left;
    struct AVLNode* rightGrandChild = leftChild->right;
    leftChild->right = node;
    node->left = rightGrandChild;
    updateHeight(node);
    updateHeight(leftChild);
    return leftChild;
}

我们定义了一个 `rightRotate` 函数，用于实现右旋转。右旋转操作将当前节点的左子节点变为新的根节点，当前节点变为新根节点的右子节点，而新根节点的右子节点变为当前节点的左子节点。然后更新当前节点和新根节点的高度，并返回新根节点。

7. 插入节点

struct AVLNode* insert(struct AVLNode* root, int data) {
    if (root == NULL) {
        return newNode(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else {
        root->right = insert(root->right, data);
    }
    updateHeight(root);
    int balance = balanceFactor(root);
    if (balance > 1 && data < root->left->data) {
        return rightRotate(root);
    }
    if (balance < -1 && data > root->right->data) {
        return leftRotate(root);
    }
    if (balance > 1 && data > root->left->data) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    if (balance < -1 && data < root->right->data) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    return root;
}

我们定义了一个 `insert` 函数，用于向AVL树插入一个节点。若树为空，则直接返回一个新节点。若待插入节点的值小于当前节点的值，则递归插入当前节点的左子树，否则递归插入当前节点的右子树。然后更新当前节点的高度，并计算平衡因子。若平衡因子大于1且待插入节点的值小于当前节点的左子节点的值，则进行右旋转；若平衡因子小于-1且待插入节点的值大于当前节点的右子节点的值，则进行左旋转；若平衡因子大于1且待插入节点的值大于当前节点的左子节点的值，则先进行左旋转再进行右旋转；若平衡因子小于-1且待插入节点的值小于当前节点的右子节点的值，则先进行右旋转再进行左旋转。最后返回根节点。

8. 删除节点

struct AVLNode* delete(struct AVLNode* root, int data) {
    if (root == NULL) {
        return root;
    }
    if (data < root->data) {
        root->left = delete(root->left, data);
    } else if (data > root->data) {
        root->right = delete(root->right, data);
    } else {
        if (root->left == NULL || root->right == NULL) {
            struct AVLNode* temp = root->left ? root->left : root->right;
            if (temp == NULL) {
                temp = root;
                root = NULL;
            } else {
                *root = *temp;
            }
            free(temp);
        } else {
            struct AVLNode* temp = minValueNode(root->right);
            root->data = temp->data;
            root->right = delete(root->right, temp->data);
        }
    }
    if (root == NULL) {
        return root;
    }
    updateHeight(root);
    int balance = balanceFactor(root);
    if (balance > 1 && balanceFactor(root->left) >= 0) {
        return rightRotate(root);
    }
    if (balance > 1 && balanceFactor(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    if (balance < -1 && balanceFactor(root->right) <= 0) {
        return leftRotate(root);
    }
    if (balance < -1 && balanceFactor(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    return root;
}

我们定义了一个 `delete` 函数，用于删除AVL树中的一个节点。若树为空，则直接返回。若待删除节点的值小于当前节点的值，则递归删除当前节点的左子树中的对应节点，否则递归删除当前节点的右子树中的对应节点。若待删除节点的左右子树都不为空，则在右子树中找到最小值节点，将其值赋给当前节点，然后递归删除右子树中的最小值节点。最后，必须更新当前节点的高度，并计算平衡因子。若平衡因子大于1且当前节点的左子树的平衡因子大于等于0，则进行右旋转；若平衡因子大于1且当前节点的左子树的平衡因子小于0，则先进行左旋转再进行右旋转；若平衡因子小于-1且当前节点的右子树的平衡因子小于等于0，则进行左旋转；若平衡因子小于-1且当前节点的右子树的平衡因子大于0，则先进行右旋转再进行左旋转。最后返回根节点。

9. 查找最小值节点

struct AVLNode* minValueNode(struct AVLNode* node) {
    struct AVLNode* current = node;
    while (current->left != NULL) {
        current = current->left;
    }
    return current;
}

我们定义了一个 `minValueNode` 函数，用于查找AVL树中的最小值节点。从当前节点开始，一直往左走，直到找到左子树为空的节点。最后返回该节点。

完整代码示例：