AA Tree C implementation.

aa_tree.c

#include <stdlib.h>
#define MIN(a, b) (a > b ? b : a)

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode *create(int val)
{
    struct TreeNode *rv = calloc(1, sizeof(struct TreeNode));
    rv->val = val;
    rv->left = NULL;
    rv->right = NULL;
    return rv;
}

int nodeLevel(struct TreeNode *root)
{
    if (!root)
        return 0;
    else
    {
        int left = nodeLevel(root->left);
        int right = nodeLevel(root->right);
        return MIN(left, right) + 1;
    }
}

struct TreeNode *skew(struct TreeNode *node)
{
    if (!node || !node->left)
        return node;

    int levelLeft = nodeLevel(node->left);
    int level = nodeLevel(node);
    if (levelLeft != level)
        return node;

    struct TreeNode *left = node->left;
    node->left = left->right;
    left->right = node;
    return left;
}

struct TreeNode *split(struct TreeNode *node)
{
    if (!node || !node->right || !node->right->right)
        return node;

    int levelRightRight = nodeLevel(node->right->right);
    int level = nodeLevel(node);
    if (levelRightRight != level)
        return node;

    struct TreeNode *right = node->right;
    node->right = right->right;
    right->left = node;
    return right;
}

struct TreeNode *insert(struct TreeNode *root, int val)
{
    if (!root)
        return create(val);

    if (root->val <= val)
        root->left = insert(root->left, val);
    else
        root->right = insert(root->right, val);

    root = skew(root);
    root = split(root);
    return root;
}

int main()
{
    int nums[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    struct TreeNode *root = NULL;
    for (size_t idx = 0; idx < numsSize; idx++)
    {
        root = insert(root, nums[idx]);
    }
}