Given an AVL tree containing nodes ordered by unique integer I.D’s and data as pointers to some struct, what would be the expected minimum number of elements that will justify the creation and maintenance of the tree? I know this is a broad question so let me give some more details:

Say I have the following pseudo code:

create_avl_tree(); for(int i = 0; i < size_of(arr_a); i++) {     // insert will create the struct if it does not exist in the tree,     // and will return it if it does exists.     my_first_struct = insert_to_avl(arr_a[i]);      // more stuff...     for(int j = 0; j < size_of(arr_b); j++) {         my_secont_struct = insert_to_avl(arr_b[j]);         // do some calculations that will require both first and second struct     } } destroy(avl_tree); 

We assume that creating the struct will be more costly than searching for it in the tree (by a pretty big margin).

The second option would be to discard the tree altogether, and just create the structs inside the loop no matter what.

Any suggestions on how to analyze this? Note that the tree is optimized to the best of knowledge. This is for C language. Thanks in advance.

P.S I’m not interested in the Big O analysis. This is a real world problem and not a research one.