Is there an insertion method for a binary search tree that is faster than the trivial one?

Question

Is there an insertion method for a binary search tree that is faster than the trivial one?

Navigation

#1 by (3 votes)

2

I'm trying to solve this problem in a judge online.

The problem provides N integers that must be inserted, in the given order, into an algorithm for inserting a binary search tree. Then Q queries are performed. For each query the code should say who is the parent of the element that is provided in the input.

The entry will be as follows:

N (quantity of values)
  N N N 2 ... N N (These are the values that must be entered in the tree) strong> (the amount of queries)
  Q Q (the integer representing the position of the given value in the input)

For the following sample entry following the above specification:

The algorithm should form the following tree:

And with this tree must answer who is the parent of the second element given in the entry (the parent of 1) and the 5 element of the entry (the father of 5) separated by a space (there are no spaces after the last value of the output)

Example of expected output for the example entry:

3 4

To solve this problem I used the trivial algorithm of insertion in binary trees (which leads to a worst-case complexity of O (n 2 )). During insertion, you have already saved the parent of each node on a map.

But, the code was judged as timeout exceeded . Is there any faster insertion algorithm than the trivial one (which keeps the order given in the input ... AVL trees will change the parents of each in ...)?

#include <cstdio>
#include <cstdlib>
#include <unordered_map>

struct node {
    int data;
    struct node *leftChild;
    struct node *rightChild;
};

void insertAndBuildFather(node **tree, int data, std::unordered_map<int, int> &father){
    struct node *tempNode = (struct node*) malloc(sizeof(struct node));

    tempNode->data = data;
    tempNode->leftChild = NULL;
    tempNode->rightChild = NULL;

    struct node *root = *tree;
    if(root == NULL){
        root = tempNode;
        father[root->data] = -1; //raiz nao tem pai
        *tree = root;
        return;
    }

    struct node *current = root;
    struct node *parent = NULL;

    while(1){
        parent = current;
        if(data < parent->data){
            current = current->leftChild;
            if(current == NULL){
                father[tempNode->data] = parent->data;
                parent->leftChild = tempNode;
                return;
            }
        }
        else{
            current = current->rightChild;
            if(current == NULL){
                father[tempNode->data] = parent->data;
                parent->rightChild = tempNode;
                return;
            }
        }

    }
}

int main ( void ) {
    int n;
    scanf("%d", &n);

    struct node* tree = NULL;
    std::unordered_map<int, int> father; //guarda os pais de cada valor
    int in[n + 1];
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &in[i]);
        insertAndBuildFather(&tree, in[i], father);
    }

    int q, qi;
    scanf("%d", &q);
    for (int i = 1; i < q; ++i) {
        scanf("%d", &qi);
        printf("%d ", father[in[qi]]);
    }
    scanf("%d", &qi);
    printf("%d\n", father[in[qi]]);
}

Thanks for any help =)

c++ algoritmo

asked by anonymous 12.07.2016 / 21:04

1 answer

Delete list item if directory does not exist How to add value of a conditioned cell to the value of another?

score 3 · Accepted Answer

In general, the insertion in the BST is O (N) in the worst case (which is a tree hanging completely to one side), which would actually give an O (N²) algorithm. However, this can be easily circumvented by keeping where the largest node in the tree is and the smallest node of the tree. If the value to be inserted is larger than the largest node of the tree, then just put it to the right of the largest, and set it as the new largest, and do the same in case the value to be inserted is smaller than the smaller. This way, when you enter an extreme value, you reduce the complexity of O (N) to O (1) by getting Accepted.

Below is an example of AC code:

// Gabriel Taets - Universidade Federal de Itajubá - gabrieltaets at gmail.com
#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
int tree[200100];
int n, hi = -1, lo = 0x3f3f3f3f;
int matricula[100010];
int pai[100010];

void insere(int node){
  if(tree[0] == -1){
    hi = lo = node;
    tree[0] = tree[1] = node;
    return;
  }
  int atual = 0;
  if(matricula[node] > matricula[hi]){
    int dir = hi*2+1;
    tree[dir] = node;
    pai[node] = hi;
    hi = node;
    return;
  }
  if(matricula[node] < matricula[lo]){
    int esq = lo*2;
    tree[esq] = node;
    pai[node] = lo;
    lo = node;
    return;
  }
  while(1){
    int dir = atual*2+1, esq = atual*2;
    if(matricula[node] > matricula[atual]){
      if(tree[dir] == -1){
        tree[dir] = node;
        pai[node] = atual;
        return;
      }
      atual = tree[dir];
      continue;
    }
    else {
      if(tree[esq] == -1){
        tree[esq] = node;
        pai[node] = atual;
        return;
      }
      atual = tree[esq];
      continue;
    }
  }
}

int main(){
  scanf("%d",&n);
  memset(tree,-1,sizeof tree);
  for(int i = 1; i <= n; i++){
    scanf("%d",&matricula[i]);
    insere(i);
  }
  int q;
  cin >> q;
  for(int i = 0; i < q; i++){
    int x;
    scanf("%d",&x);
    if(i) putchar(' ');
    printf("%d",matricula[pai[x]]);
  }
  putchar('\n');
  return 0;
}

A good tip too, it's often a bad idea to use dynamic allocation in these Online Judges issues (unless you're specifically training dynamic allocation). Dynamic Allocation is very error-prone and can cause crashes where you can not even imagine that it may be wrong in your code. So if your goal with Online Judge is to train for programming competitions, I recommend that you learn to represent trees as vectors, as in the above code.

I hope I have helped!