平衡树排序(谁会用这个啊)

时间复杂度：稳定O(n log n)
空间复杂度：稳定O(n)
稳定性：不稳定
code:

#include<iostream>
using namespace std;
struct treenode
{
   int val;//值
   int size;//树大小
   int depth;//树深度
   treenode* l;//左树
   treenode* r;//右树
   treenode(int key) : val(key), size(1), depth(1), l(nullptr), r(nullptr){}
};
treenode* root;
struct AVL
{
   int cnt = 0;
   //获取树深度
   inline int depth(treenode* node)
   {
       if(node == nullptr)return 0;
       else return node->depth;
   }
   //获取树大小
   inline int size(treenode* node)
   {
       if(node == nullptr)return 0;
       else return node->size;
   }
   inline void update(treenode* node)
   {
       node->size = 1 + size(node->l) + size(node->r);
       node->depth = max(depth(node->l), depth(node->r)) + 1;
   }
   //右旋
   inline treenode* right_rotate(treenode* node)
   {
       if(node == nullptr)return node;
       if(node->l == nullptr)return node;
       treenode* t0 = node->l;
       treenode* t1 = node->l->r;
       t0->r = node;
       node->l = t1;
       update(node);
       update(t0);
       return t0;
   }
   //左旋
   inline treenode* left_rotate(treenode* node)
   {
       if(node == nullptr)return node;
       if(node->r == nullptr)return node;
       treenode* t0 = node->r;
       treenode* t1 = node->r->l;
       t0->l = node;
       node->r = t1;
       update(node);
       update(t0);
       return t0;
   }
   //插入
   inline treenode* insert_x(int key, treenode* node = root)
   {
       if(node == nullptr)
           return new treenode(key);
       if(key <= node->val)
           node->l = insert_x(key, node->l);
       if(key > node->val)
           node->r = insert_x(key, node->r);
       update(node);
       if(depth(node->l) - depth(node->r) >= 2)
       {
           if(key <= node->l->val)
               return right_rotate(node);
           else
           {
               node->l = left_rotate(node->l);
               return right_rotate(node);
           }
       }
       if(depth(node->r) - depth(node->l) >= 2)
       {
           if(key > node->r->val)
               return left_rotate(node);
           else
           {
               node->r = right_rotate(node->r);
               return left_rotate(node);
           }
       }
       return node;
   }
   inline void insert(int key)
   {
       root = insert_x(key);
   }
   //获取第k大值
   inline int rank(int key, treenode* node = root)
   {
       if(node == nullptr)return -1;
       if(key > node->size)return -1;
       
       if(key <= size(node->r))
           return rank(key, node->r);
       
       if(key == size(node->r) + 1)
           return node->val;
       
       return rank(key - size(node->r) - 1, node->l);
   }
}f;
int main()
{
   int n;
   cin >> n;
   for(int i = 1; i <= n; i++)
   {
       int x;
       cin >> x;
       f.insert(x);
   }
   for(int i = n; i >= 1; i--)
       cout << f.rank(i) << ' ';
}