Dear Hub,
Thanks for your kindly reply. I noticed that the implementation you suggested used push operation instead of recursive function. How do you think the efficiency of these two implementations?

Thanks,
Tang Laoya 

Dear Hub,

The problem is solved after modified the function popmax as follows:
void * popmax(avltree* &p)
{
        avltree* max=findmax(p);
        void *key=max->key;
        p=remove(p,key);
        return key;
}

Do you have any suggestion to improve the code for faster speed, especially the function popmax?

Thanks,
Tang Laoya

Dear Hub,   
Sorry to bother you again. There are still some problems. 
when the code running in the latter (after many times insert/remove/popmax operations, the code will crash. 

The code is used as follows:
node *avlroot;

avlroot=insert(avlroot,(void*)t);  /// happened at many locations
...
avl=popmax(avlroot);  /// happened at many locations
...
avlroot=remove(avlroot,(void*)t); /// happened at many locations
...

/// finally
deletetree(avlroot);

Is there any problem in using the code?

Thanks,
Tang Laoya

Dear Hub, Thank you very much for your kindly reply. I posted the whole code modified based on your original code. It seems that the problem is solved (there are some problems in compare functions before). However, the code is somewhat slow when the number of elements is huge (more than one million). Could you please help me to take a look at it and give me some suggestion to improve the code? Thanks, TangLaoya

/// reference: https://kukuruku.co/hub/cpp/avl-trees
extern int avlcompare(void *item1, void *item2);
extern void externopt(void *t);
extern void externout(void *t);
#include "avl.h"

unsigned char height(node* p)
{
    return p?p->height:0;
}

int bfactor(node* p)
{
    return height(p->right)-height(p->left);
}

void fixheight(node* p)
{
    unsigned char hl = height(p->left);
    unsigned char hr = height(p->right);
    p->height = (hl>hr?hl:hr)+1;
}

node* rotateright(node* p)
{
    node* q = p->left;
    p->left = q->right;
    q->right = p;
    fixheight(p);
    fixheight(q);
    return q;
}

node* rotateleft(node* q)
{
    node* p = q->right;
    q->right = p->left;
    p->left = q;
    fixheight(q);
    fixheight(p);
    return p;
}

node* balance(node* p) // balancing the p node
{
    fixheight(p);
    if( bfactor(p)==2 )
    {
        if( bfactor(p->right) < 0 )
            p->right = rotateright(p->right);
        return rotateleft(p);
    }
    if( bfactor(p)==-2 )
    {
        if( bfactor(p->left) > 0  )
            p->left = rotateleft(p->left);
        return rotateright(p);
    }
    return p; // balancing is not required
}

node* insert(node* p, void* k) // insert k key in a tree with p root
{
    if( !p ) return new node(k);
    //if( kkey )
                if (avlcompare(k, p->key)<0)
        p->left = insert(p->left,k);
    else
        p->right = insert(p->right,k);
    return balance(p);
}

node* findmin(node* p) // find a node with minimal key in a p tree 
{
    return p->left?findmin(p->left):p;
}

node* removemin(node* p) // deleting a node with minimal key from a p tree
{
    if( p->left==0 )
        return p->right;
    p->left = removemin(p->left);
    return balance(p);
}

node* findmax(node* p) // find a node with maximal key in a p tree 
{
    return p->right?findmax(p->right):p;
}

void * popmax(node* p)
{
        node* max=findmax(p);
        void *key=max->key;
        remove(p,key);
        return key;
}

node* remove(node* p, void* k) // deleting k key from p tree
{
    if( !p ) return 0;
                int comp=avlcompare(k, p->key);
    //if( k < p->key )
    if( comp < 0 )
        p->left = remove(p->left,k);
    //else if( k > p->key )
    else if( comp > 0 )
        p->right = remove(p->right,k);  
    else //  k == p->key 
    {
        node* q = p->left;
        node* r = p->right;
        delete p;
        if( !r ) return q;
        node* min = findmin®;
        min->right = removemin®;
        min->left = q;
        return balance(min);
    }
    return balance(p);
}

void in_order_traversal(node *p)
{
        if(p)
        {
                in_order_traversal(p->left);
                externout(p->key);
                in_order_traversal(p->right);
        }
}

void pre_order_traversal(node *p)
{
        if(p)
        {
                externout(p->key);
                pre_order_traversal(p->left);
                pre_order_traversal(p->right);
        }
}

void deletetree(node *p)
{
        if(p)
        {
                deletetree(p->left);
                deletetree(p->right);
                externopt(p->key);
                delete(p);
        }
        p=0;
}

Sorry I didn't notice the format. I post again.

Thank you very much for providing so powerful code. I have a question to use your code.
After inserted all elements, I need to pop the maximal element (return element data and then delete the node) every time (also insert some new elements). However, my test shows that every time the elements are deleted, the elements are not changed when output the whole tree (by in_order_traversal). Could you please help me to take a look at it?

Thanks,Tang Laoya

node* findmax(node* p) // find a node with maximal key in a p tree 
{
    return p->right?findmax(p->right):p;
}

void * popmax(node* p)
{
        node* max=findmax(p);
        void *key=max->key;
        remove(p,key);
        return key;
}

void in_order_traversal(node *p)
{
        if(p)
        {
                in_order_traversal(p->left);
                cout << p->key << '\n' ;
                in_order_traversal(p->right);
        }
}

Dear Hub,Thank you very much for providing so powerful code. I have a question to use your code.After inserted all elements, I need to pop the maximal element (return element data and then delete the node) every time (also insert some new elements). However, my test shows that every time the elements are deleted, the elements are not changed when output the whole tree (by in_order_traversal). Could you please help me to take a look at it?Thanks,Tang LaoyaPS:the code I added:node* findmax(node* p) // find a node with maximal key in a p tree { return p->right?findmax(p->right):p;}void * popmax(node* p){ node* max=findmax(p); void *key=max->key; remove(p,key); return key;}void in_order_traversal(node *p){ if(p) { in_order_traversal(p->left); cout << p->key << '\n'; in_order_traversal(p->right); }}

Dear Hub,Thank you very much for providing so powerful code. I have a question to use your code.After inserted all elements, I need to pop the maximal element (return element data and then delete the node) every time (also insert some new elements). However, my test shows that every time the elements are deleted, the elements are not changed when output the whole tree (by in_order_traversal). Could you please help me to take a look at it?Thanks,Tang LaoyaPS:the code I added:node* findmax(node* p) // find a node with maximal key in a p tree { return p->right?findmax(p->right):p;}void * popmax(node* p){ node* max=findmax(p); void *key=max->key; remove(p,key); return key;}void in_order_traversal(node *p){ if(p) { in_order_traversal(p->left); cout << p->key << '\n'; in_order_traversal(p->right); }}