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:

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

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.

  • $\begingroup$ If you know all elements of the AVL tree as an array beforehand, then you can order that array and directly convert it to a balanced binary search tree, you don't need to use an AVL tree for that. $\endgroup$
    – nir shahar
    Jun 17 at 7:58
  • $\begingroup$ @nirshahar What do you mean? Il have to create the BST anyway and maintain it... $\endgroup$
    – Eminem
    Jun 17 at 8:02
  • 1
    $\begingroup$ You can create the BST directly without repeatedly calling insert $\endgroup$
    – nir shahar
    Jun 17 at 8:05
  • $\begingroup$ @Eminem Fancy search structures like AVL or RB or treaps or whatever are necessary only if you need to interleave your modification operations with your query ones. If you don’t you can sort all of your data in advance then use binary search for the queries: same asymptotic complexity, much faster and simpler in practice (caveat: except if you’re going to be adding a lot of identical elements). Your code looks like arr_a and arr_b are filled in advance, so the suggestion is to split the loops and collect everything you’ll need in a sorted array first, then do the processing. $\endgroup$ Jun 17 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.