Не работает функция удаления ключа из BST-дерева

Написал программу создания BST-дерева путем рандомизированной вставки. Попытался написать функцию удаления ключа из BST-дерева, но она может удалить лишь самый первый элемент, то есть корень, остальные удалить почему-то не получается. Прошу Ваших советов и наставлений для решения данной проблемы.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

typedef struct node{
    int data;
    int k;
    struct node *left;
    struct node *right;
} Node;

void rotate_l(Node **h){
    Node *x;
    int n;
    n = (*h) -> k;
    x = (*h) -> right;
    (*h) -> right = x -> left;
    x -> left = *h;
    *h = x;
    (*h) -> k = n;
    (*h) -> left -> k = 1;
    if ((*h)->right->right){
        (*h) -> right -> k = (*h) -> right -> k + (*h) -> right -> right -> k;
    }
    if ((*h)->right->left){
        (*h) -> right -> k = (*h) -> right -> k + (*h) -> right -> left -> k;
    }
}

void rotate_r(Node **h){
    Node *x;
    int n = (*h) -> k;
    x = (*h) -> left;
    (*h) -> left = x -> right;
    x -> right = (*h);
    (*h) = x;
    (*h) -> k = n;
    (*h) -> right -> k = 1;
    if ((*h) -> right -> right){
        (*h) -> right -> k = (*h) -> right -> k + (*h) -> right -> right -> k;
    }
    if ((*h) -> right -> left){
        (*h) -> right -> k = (*h) -> right -> k + (*h) -> right -> left -> k;
    }
}

void InsertInR(Node **Root, int key){
    if (*Root == NULL){
        (*Root) = (Node*)malloc(sizeof(Node));
        (*Root) -> data = key;
        (*Root) -> left = NULL;
        (*Root) -> right = NULL;
        return;
    }
    else if(key >= (*Root) -> data){
        InsertInR(&(*Root) -> right, key);
        rotate_l(Root);
    }
    else{
        InsertInR(&(*Root) -> left, key);
        rotate_r(Root);
    }
}

void InsertR(Node **Root, int key){
    float z,a;
    if(*Root == NULL){
        (*Root) = (Node*)malloc(sizeof(Node));
        (*Root) -> data = key;
        (*Root) -> left = NULL;
        (*Root) -> right = NULL;
        (*Root) -> k = 1;
        return; 
    }
    z = rand()%2;
    a = 1/(((*Root) -> k) + 1);
    (*Root) -> k++;
    if(z < a){
        InsertInR(&(*Root), key);
        return;
    }
    if(key > (*Root) -> data){
        InsertR(&(*Root) -> left, key);
    }
    else{
        InsertR(&(*Root) -> right, key);
    }
}

/*void partition(int n, Node **Root){
    int T;
    if(*Root == 0) exit;
    //T = ((*Root) -> left == 0) ? 0 : (*Root) -> left -> k;
    if((*Root) -> left == NULL) T = 0;
    else T = (*Root) -> left -> k;
    if (T > n){
        partition(n, &(*Root) -> left);
        rotate_r(Root); 
    }
    if (T < n){
        partition(n - T - 1, &(*Root) -> right);
        rotate_l(Root); 
    }
}*/

Node *Join(Node *a, Node *b){
    if(b == NULL) return a;
    if(a == NULL) return b;
    InsertInR(&b, a -> data);
    b -> left = Join(a -> left, b -> left);
    b -> right = Join(a -> right, b -> right);
    free(a);
    return b;
}

void Delete2(int n, Node **Root){
    int z;
    z = (*Root) -> data;
    if (n == z){
        Node *t;
        t = *Root;
        *Root = Join((*Root) -> right, (*Root) -> left);
        free(t);
        return;
    }
    if (n < z) Delete2(n, &(*Root) -> left);
    else Delete2(n, &(*Root) -> right);
}

void show(Node *Root){ 
    if(Root==0) return;
    else{
        printf("%d",Root -> data);
        printf("(%d) ",Root -> k);
        show(Root -> left);
        show(Root -> right);
    } 
}

int main(int argc, char *argv[]) {
    system("chcp 1251");
    srand(time(NULL));
    int i,n,a,b;
    Node *Root = NULL;
    printf("Введите число элементов дерева\n");
    scanf("%d", &n);
    printf("Элементы, добавленные в дерево\n");
    for(i = 0; i < n; i++){
        a = rand()%100;
        printf("%d ", a);
        InsertR(&Root, a);
    }
    printf("\n");
    show(Root);
    printf("\n");
    printf("Введите ключ, который нужно удалить из BST - дерева\n");
    scanf("%d", &b);
    Delete2(b, &Root);
    show(Root);
    return 0;
}