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

typedef double item;

typedef struct node_s {
    struct node_s *left, *right;
    item val;
} node;

node *new_node(item it) {
    node *ret = (node *)malloc(sizeof (node));
    ret->left = ret->right = NULL;
    ret->val = it;
    return ret;
}

node *rotateRight(node* head) {
    node *temp = head->left;
    head->left = temp->right;
    temp->right = head;
    return temp;
}

node *rotateLeft(node* head) {
    node *temp = head->right;
    head->right = temp->left;
    temp->left = head;
    return temp;
}

node * insert(node* head, item x) {
    if (head == NULL) {
        head = new_node(x);
        return head;
    }
    if (x < head->val) {
        head->left = insert(head->left, x);
        return rotateRight(head);
    } else {
        head->right = insert(head->right, x);
        return rotateLeft(head);
    }
}

void print(node const *head, int lev) {
    if (head->right != NULL)  print(head->right, lev+1);
    for (int i = 0; i < lev; i++) {
        printf("  ");
    }
    printf("%.2f\n", head->val);
    if (head->left != NULL)  print(head->left, lev+1);
}

node *join(node* a, node *b) {
   if (a == NULL) return b;
   if (b == NULL) return a;
   b = insert(b, a->val);
   b->left = join(a->left, b->left);
   b->right = join(a->right, b->right);
   // destroy a
   return b;
}

int main() {
    node *head = NULL;
    head = insert(head,5);
    head = insert(head, 1);
    head = insert(head, 3);

    node *head1 = NULL;
    head1 = insert(head1, 2);
    head1 = insert(head1, 6);
    head1 = insert(head1, 4);
    head = join(head, head1);
    print(head, 0);
}