/* C11. AVL insertion; heights count nodes (empty=0, leaf=1). */
#include <assert.h>
#include <stdbool.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int key, height; struct Node *left, *right; } Node;
static int height(const Node *p) { return p == NULL ? 0 : p->height; }
static int maximum(int a, int b) { return a > b ? a : b; }
static void update(Node *p) { p->height = 1 + maximum(height(p->left), height(p->right)); }
static Node *rotate_right(Node *y)
{
    Node *x = y->left, *middle = x->right;
    x->right = y; y->left = middle; update(y); update(x); return x;
}
static Node *rotate_left(Node *x)
{
    Node *y = x->right, *middle = y->left;
    y->left = x; x->right = middle; update(x); update(y); return y;
}
/* ok is set false only on allocation failure. Existing nodes remain owned. */
static Node *insert(Node *root, int key, bool *ok)
{
    if (root == NULL) {
        Node *p = malloc(sizeof *p);
        if (p == NULL) { *ok = false; return NULL; }
        *p = (Node){key, 1, NULL, NULL}; return p;
    }
    if (key < root->key) root->left = insert(root->left, key, ok);
    else if (key > root->key) root->right = insert(root->right, key, ok);
    else return root; /* Ignore duplicates. */
    update(root);
    int balance = height(root->left) - height(root->right);
    if (balance > 1) {
        if (key > root->left->key) root->left = rotate_left(root->left); /* LR */
        return rotate_right(root); /* LL or second step of LR */
    }
    if (balance < -1) {
        if (key < root->right->key) root->right = rotate_right(root->right); /* RL */
        return rotate_left(root); /* RR or second step of RL */
    }
    return root;
}
static void destroy(Node *p)
{
    if (p == NULL) return;
    destroy(p->left); destroy(p->right); free(p);
}
/* Independently recompute height and check strict BST ordering after each insert. */
static int validate(const Node *p, long long lower, long long upper)
{
    if (p == NULL) return 0;
    assert(lower < p->key && p->key < upper);
    int left = validate(p->left, lower, p->key);
    int right = validate(p->right, p->key, upper);
    assert(left - right >= -1 && left - right <= 1);
    assert(p->height == 1 + maximum(left, right));
    return 1 + maximum(left, right);
}
static void inorder(const Node *p, int out[], size_t *n)
{
    if (p == NULL) return;
    inorder(p->left, out, n); out[(*n)++] = p->key; inorder(p->right, out, n);
}
static bool check_rotation(const int keys[3])
{
    Node *root = NULL; bool ok = true;
    for (size_t i = 0; i < 3; ++i) {
        root = insert(root, keys[i], &ok);
        if (!ok) { destroy(root); return false; }
        (void)validate(root, LLONG_MIN, LLONG_MAX);
    }
    assert(root->key == 20 && root->left->key == 10 && root->right->key == 30);
    destroy(root); return true;
}
int main(void)
{
    const int cases[4][3] = {{30,20,10}, {10,20,30}, {30,10,20}, {10,30,20}};
    for (size_t i = 0; i < 4; ++i) if (!check_rotation(cases[i])) return EXIT_FAILURE;
    puts("LL, RR, LR and RL rotation tests passed");
    const int keys[] = {30,100,150,20,10,45,80,75,120,130,125,200,75};
    const int expected[] = {10,20,30,45,75,80,100,120,125,130,150,200};
    Node *root = NULL; bool ok = true;
    for (size_t i = 0; i < sizeof keys / sizeof keys[0]; ++i) {
        root = insert(root, keys[i], &ok);
        if (!ok) { destroy(root); return EXIT_FAILURE; }
        (void)validate(root, LLONG_MIN, LLONG_MAX);
        int partial[13]; size_t count = 0; inorder(root, partial, &count);
        for (size_t j = 1; j < count; ++j) assert(partial[j - 1] < partial[j]);
    }
    int out[13]; size_t n = 0; inorder(root, out, &n); assert(n == 12);
    printf("AVL inorder:");
    for (size_t i = 0; i < n; ++i) { assert(out[i] == expected[i]); printf(" %d", out[i]); }
    putchar('\n'); destroy(root);
    puts("AVL tests passed");
    return EXIT_SUCCESS;
}