AVL TREE - Most efficient way to print a value, by location. C++

Question

Hey I have to find the most eficient way to print a number by giving the postion. The input is like this:

8 (N-> N Numbers)
INS 100 (Add 100 to the tree)
INS 200 (Add 200 to the tree)
INS 300 (Add 300 to the tree)
REM 200 (Remove the number 200 from the tree)
PER 1 (Have to output the biggest number in the tree-> Shoud print 300)
INS 1000 (Add 1000 to the tree)
PER 1 ((Have to output the biggest number in the tree-> Shoud print 1000))
PER 2 (I have to output the second biggest number so:  300)

I have a way to print like this, but is very slow and I have to maintain a O(N * log(N)).

Here is my full code

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

// An AVL tree node
struct node
{
    int key;
    struct node *left;
    struct node *right;
    int height;
};
// A utility function to get maximum of two integers
int max(int a, int b);
// A utility function to get height of the tree
int height(struct node *N)
{
    if (N == NULL)
            return 0;
    return N->height;
}
// A utility function to get maximum of two integers
int max(int a, int b)
{
    return (a > b)? a : b;
}
/* Helper function that allocates a new node with the given key and
    NULL left and right pointers. */
struct node* newNode(int key)
{
    struct node* node = (struct node*)
                                            malloc(sizeof(struct node));
    node->key   = key;
    node->left   = NULL;
    node->right  = NULL;
    node->height = 1;  // new node is initially added at leaf
    return(node);
}
// A utility function to right rotate subtree rooted with y
// See the diagram given above.
struct node *rightRotate(struct node *y)
{
    struct node *x = y->left;
    struct node *T2 = x->right;
    // Perform rotation
    x->right = y;
    y->left = T2;
    // Update heights
    y->height = max(height(y->left), height(y->right))+1;
    x->height = max(height(x->left), height(x->right))+1;
    // Return new root
    return x;
}
// A utility function to left rotate subtree rooted with x
// See the diagram given above.
struct node *leftRotate(struct node *x)
{
    struct node *y = x->right;
    struct node *T2 = y->left;
    // Perform rotation
    y->left = x;
    x->right = T2;
    //  Update heights
    x->height = max(height(x->left), height(x->right))+1;
    y->height = max(height(y->left), height(y->right))+1;
    // Return new root
    return y;
}
// Get Balance factor of node N
int getBalance(struct node *N)
{
    if (N == NULL)
            return 0;
    return height(N->left) - height(N->right);
}
struct node* insert(struct node* node, int key)
{
    /* 1.  Perform the normal BST rotation */
    if (node == NULL)
            return(newNode(key));
    if (key < node->key)
            node->left  = insert(node->left, key);
    else
            node->right = insert(node->right, key);
    /* 2. Update height of this ancestor node */
    node->height = max(height(node->left), height(node->right)) + 1;
    /* 3. Get the balance factor of this ancestor node to check whether
           this node became unbalanced */
    int balance = getBalance(node);
    // If this node becomes unbalanced, then there are 4 cases
    // Left Left Case
    if (balance > 1 && key < node->left->key)
            return rightRotate(node);
    // Right Right Case
    if (balance < -1 && key > node->right->key)
            return leftRotate(node);
    // Left Right Case
    if (balance > 1 && key > node->left->key)
    {
            node->left =  leftRotate(node->left);
            return rightRotate(node);
    }
    // Right Left Case
    if (balance < -1 && key < node->right->key)
    {
            node->right = rightRotate(node->right);
            return leftRotate(node);
    }
    /* return the (unchanged) node pointer */
    return node;
}
/* Given a non-empty binary search tree, return the node with minimum
   key value found in that tree. Note that the entire tree does not
   need to be searched. */
struct node * minValueNode(struct node* node)
{
    struct node* current = node;
    /* loop down to find the leftmost leaf */
    while (current->left != NULL)
            current = current->left;
    return current;
}
struct node* apagaNode(struct node* root, int key)
{
    // STEP 1: PERFORM STANDARD BST DELETE
    if (root == NULL)
            return root;
    // If the key to be deleted is smaller than the root's key,
    // then it lies in left subtree
    if ( key < root->key )
            root->left = apagaNode(root->left, key);
    // If the key to be deleted is greater than the root's key,
    // then it lies in right subtree
    else if( key > root->key )
            root->right = apagaNode(root->right, key);
    // if key is same as root's key, then This is the node
    // to be deleted
    else
    {
            // node with only one child or no child
            if( (root->left == NULL) || (root->right == NULL) )
            {
                    struct node *temp = root->left ? root->left : root->right;
                    // No child case
                    if(temp == NULL)
                    {
                            temp = root;
                            root = NULL;
                    }
                    else // One child case
                         *root = *temp; // Copy the contents of the non-empty child
                    free(temp);
            }
            else
            {
                    // node with two children: Get the inorder successor (smallest
                    // in the right subtree)
                    struct node* temp = minValueNode(root->right);
                    // Copy the inorder successor's data to this node
                    root->key = temp->key;
                    // Delete the inorder successor
                    root->right = apagaNode(root->right, temp->key);
            }
    }
    // If the tree had only one node then return
    if (root == NULL)
          return root;
    // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
    root->height = max(height(root->left), height(root->right)) + 1;
    // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether
    //  this node became unbalanced)
    int balance = getBalance(root);
    // If this node becomes unbalanced, then there are 4 cases
    // Left Left Case
    if (balance > 1 && getBalance(root->left) >= 0)
            return rightRotate(root);
    // Left Right Case
    if (balance > 1 && getBalance(root->left) < 0)
    {
            root->left =  leftRotate(root->left);
            return rightRotate(root);
    }
    // Right Right Case
    if (balance < -1 && getBalance(root->right) <= 0)
            return leftRotate(root);
    // Right Left Case
    if (balance < -1 && getBalance(root->right) > 0)
    {
            root->right = rightRotate(root->right);
            return leftRotate(root);
    }
    return root;
}

int imprime(struct node *root,int targetPos,int curPos)
{
    if(root != NULL)
    {
            int newPos = imprime(root->left, targetPos, curPos);
            newPos++;
            if (newPos == targetPos)
            {
                    printf("%d\n", root->key);
            }
            return imprime(root->right, targetPos, newPos);
    }
    else
    {
            return curPos;
    }
}

int main()
{
  struct node *root = NULL;
  int total=0;
  int n,b;
  string a;
  cin >> n;
  for (int i=0; i<n; i++)
  {
          cin >> a >> b;
          if(a=="INS")
                  {root = insert(root, b);total=total+1;}
          else
          if(a=="REM")
                   {root = apagaNode(root, b);total=total-1;}
          else
                  imprime(root, total-b+1, 0);
  }
    return 0;
}

The way I found to print the values:

int imprime(struct node *root,int targetPos,int curPos)
{
    if(root != NULL)
    {
            int newPos = imprime(root->left, targetPos, curPos);
            newPos++;
            if (newPos == targetPos)
            {
                    printf("%d\n", root->key);
            }
            return imprime(root->right, targetPos, newPos);
    }
    else
    {
            return curPos;
    }
}

Problem is that this function is very slow, and I can't use it. How is the best way to print by a given postion like this? (A heard about, counting n_nodes, and during the rotations I have to incremennt, decrement, i realy did not understand. Help me please! Give some tips, and advices) (PS: I'm not an expert with this kind of algorithms)

Answer 1

The advice you heard is correct: you should add a node counter to your node structure:

struct node
{
    int key;
    struct node *left;
    struct node *right;
    int height;
    int n_nodes;
};

It should hold the number of nodes in the tree. Assuming it's correct, you can improve the algorithm for finding a node with a target position: it will know exactly in which branch of the tree to look (left or right), which will make the search faster (current imprime implementation is O(n)).

So, how to make it so the n_nodes field holds the right value? Fortunately, you already have an example: height. Look where your existing code changes it; these are roughly the places where you have to update n_nodes, too. Most of them are trivial (just add 1 to it); the more interesting ones are the rotation functions:

struct node *rightRotate(struct node *y)
{
    struct node *x = y->left;
    struct node *T2 = x->right;
    // Perform rotation
    x->right = y;
    y->left = T2;
    // Update heights
    y->height = max(height(y->left), height(y->right))+1;
    x->height = max(height(x->left), height(x->right))+1;
    // Update numbers of nodes
    x->n_nodes = ...;
    y->n_nodes = ...;
    T2->n_nodes = ...;
    // Return new root
    return x;
}

So it transforms the tree like this:

    y                   x
   / \                 / \
  x   D               A   y
 / \         ==>         / \
A   T2                  T2  D
   / \                 / \
  B   C               B   C

Here A, B, C and D are trees whose sizes your program knows; let's denote their sizes as a, b, c and d. So the transformation changes these sizes like this:

size of x:      from a+b+c+2       to     a+b+c+d+3
size of y:      from a+b+c+d+3     to     b+c+d+2
size of T2:     unchanged

So just transform this to code.