Build an AVL tree – Data Structures Practice Problem

Insert the given keys, in order, into an AVL tree, rebalancing with rotations after each insert. Then print the tree's keys in preorder (a node, then its left subtree, then its right subtree), and the tree's height.

What to build

An AVL tree that rebalances itself after every insert, and a report of its final shape.

Requirements

Give every node a height, and update it after each insert below the node.
When a balance factor reaches +2 or -2, repair it with the correct one or two rotations.
Print the keys in preorder on the first line, and the height on the second.

Input

A line with n (1 ≤ n ≤ 100), then n different whole numbers.

Output

Two lines: the keys in preorder separated by spaces, then the height of the tree (a single node has height 1).

Constraints

n is from 1 to 100, and all the keys are different whole numbers.

Example

Input:

6
10 20 30 40 50 25

Output:

30 20 10 25 40 50
3

Why it works

Preorder prints a node before its subtrees, so the output shows the exact shape of the tree. Only correct rotations give that shape.

Examples

Example 1 · Input

6
10 20 30 40 50 25

Expected output

30 20 10 25 40 50
3

Example 2 · Input

3
3 2 1

Expected output

2 1 3
2

Hints

Hint 1

The starter is a plain search tree. Add a height to each node: 1 for a new node, and 1 + the taller child after every insert.

Hint 2

After inserting below a node, compute balance = height(left) - height(right). At +2 or -2, rotate: compare the new key with the child's key to pick one of the four cases.

Hint 3

Return the new top of the subtree from insert and from each rotation, so the parent points at it.

Solution

Show one correct solution (try it yourself first)

#include <stdio.h>
#include <stdlib.h>

struct node {
    int key, height;
    struct node *left, *right;
};

int height(struct node *n) { return n ? n->height : 0; }
int bigger(int a, int b) { return a > b ? a : b; }
void fix(struct node *n) { n->height = 1 + bigger(height(n->left), height(n->right)); }

struct node *rotate_right(struct node *y) {
    struct node *x = y->left;
    y->left = x->right;
    x->right = y;
    fix(y);
    fix(x);
    return x;
}

struct node *rotate_left(struct node *x) {
    struct node *y = x->right;
    x->right = y->left;
    y->left = x;
    fix(x);
    fix(y);
    return y;
}

struct node *insert(struct node *n, int key) {
    if (!n) {
        n = calloc(1, sizeof(struct node));
        n->key = key;
        n->height = 1;
        return n;
    }
    if (key < n->key) n->left = insert(n->left, key);
    else n->right = insert(n->right, key);
    fix(n);
    int b = height(n->left) - height(n->right);
    if (b > 1 && key < n->left->key) return rotate_right(n);
    if (b < -1 && key > n->right->key) return rotate_left(n);
    if (b > 1) {
        n->left = rotate_left(n->left);
        return rotate_right(n);
    }
    if (b < -1) {
        n->right = rotate_right(n->right);
        return rotate_left(n);
    }
    return n;
}

int first = 1;

void preorder(struct node *n) {
    if (!n) return;
    printf(first ? "%d" : " %d", n->key);
    first = 0;
    preorder(n->left);
    preorder(n->right);
}

int main(void) {
    int n, key;
    struct node *root = NULL;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &key);
        root = insert(root, key);
    }
    preorder(root);
    printf("\n%d\n", height(root));
    return 0;
}

Lesson: AVL trees: self-balancing search trees →