AVL木にてK番目に大きい数を返すアルゴリズムが必要です

#include <iostream>

using namespace std;

#define INF 0x3f3f3f3f
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define LONG_MAX 9223372036854775807
#define LONG_MIN -9223372036854775808
#define ll long long

typedef struct AVLNode {
    int data;
    int height;
    struct AVLNode* lchild;
    struct AVLNode* rchild;
    int size;
} *AVLTree;

int Height(AVLTree T) {
    if (!T) return 0;
    return T->height;
}

int getSize(AVLTree Tree) {
    int cnt = 0;
    if (Tree->lchild)
        cnt = Tree->lchild->size + 1;
    else cnt = 1;
    if (Tree->rchild)
        cnt += Tree->rchild->size;
    return cnt;
}

void updateHeight(AVLTree& T) {
    if (!T) return;
    T->height = max(Height(T->lchild), Height(T->rchild)) + 1;
}

AVLTree LL_Rotation(AVLTree& T) {
    AVLTree temp = T->lchild;
    T->lchild = temp->rchild;
    temp->rchild = T;
    updateHeight(T);
    updateHeight(temp);
    temp->size = T->size;
    T->size = getSize(T);
    return temp;
}

AVLTree RR_Rotation(AVLTree& T) {
    AVLTree temp = T->rchild;
    T->rchild = temp->lchild;
    temp->lchild = T;
    updateHeight(T);
    updateHeight(temp);
    temp->size = T->size;
    T->size = getSize(T);
    return temp;
}

AVLTree LR_Rotation(AVLTree& T) {
    T->lchild = RR_Rotation(T->lchild);
    return LL_Rotation(T);
}

AVLTree RL_Rotation(AVLTree& T) {
    T->rchild = LL_Rotation(T->rchild);
    return RR_Rotation(T);
}

void adjust(AVLTree& T) {
    if (!T) return;
    if (Height(T->lchild) - Height(T->rchild) > 1) {
        if (Height(T->lchild->lchild) >= Height(T->lchild->rchild)) T = LL_Rotation(T);
        else T = LR_Rotation(T);
    }
    else if (Height(T->rchild) - Height(T->lchild) > 1) {
        if (Height(T->rchild->rchild) >= Height(T->rchild->lchild)) T = RR_Rotation(T);
        else T = RL_Rotation(T);
    }
}

AVLTree Insert(AVLTree& T, int x) {
    if (!T) {
        T = new AVLNode;
        T->lchild = T->rchild = NULL;
        T->data = x;
        T->height = 0;
        T->size = 1;
        return T;
    }
    if (T->data == x) return T;
    if (x < T->data) {
        T->lchild = Insert(T->lchild, x);
        T->size++;
    }
    else {
        T->rchild = Insert(T->rchild, x);
        T->size++;
    }
    updateHeight(T);
    adjust(T);
    return T;
}


int findKth(AVLTree Tree, int k) {
    return 0;
}



int main() {
    int n, x, k;
    scanf_s("%d", &n);
    scanf_s("%d", &k);
    AVLTree tree = NULL;
    for (int i = 1; i <= n; i++) {
        scanf_s("%d", &x);
        tree = Insert(tree, x);
        printf("%d ", findKth(tree, k));
    }
    return 0;
}