LL TO BST

Discussion in 'C++' started by puzzlecracker, Jan 19, 2005.

  1. Do you see any problems with the following algorithm that converts Link
    list to Binary Search tree. Can you think of a better solution?

    node* LLtoBST(node *head, int num)
    {

    node *root=head;
    int i, mid=(num+1)/2;

    if(!head) return NULL;

    if(n==1){
    head->prev=NULL;
    head->next=NULL;
    }

    else{
    for (int i=0;i<mid;++i,root=root->next)
    ;
    root->prev=LLtoBST(head, mid-1);
    root->next=LLtoBST(root->next,mid-1);
    }
    return root;

    }
     
    puzzlecracker, Jan 19, 2005
    #1
    1. Advertising

  2. puzzlecracker

    Howard Guest

    "puzzlecracker" <> wrote in message
    news:...
    > Do you see any problems with the following algorithm that converts Link
    > list to Binary Search tree. >


    Aside from the fact it won't compile, you mean? :)

    >Can you think of a better solution?



    > node* LLtoBST(node *head, int num)
    > {
    >
    > node *root=head;
    > int i, mid=(num+1)/2;


    Why do you declare i here? It's already declared as an int in the loop
    below.

    >
    > if(!head) return NULL;


    This could be at the top, to save a couple steps.

    >
    > if(n==1){


    What's n? Did you mean num?

    > head->prev=NULL;
    > head->next=NULL;
    > }
    >
    > else{
    > for (int i=0;i<mid;++i,root=root->next)
    > ;
    > root->prev=LLtoBST(head, mid-1);


    Suppose num is 4. Then mid = (4+1)/2 = 5/2 = 2. So, mid-1 is 1. So you're
    going to point your "left" member to the original head of the list, with
    only one member. But the loop above just moved the pointer to the third
    item in the list, so you're going to lose the second item, aren't you? I
    suspect that the num passed to this function needs to be mid, not mid-1.

    But that's just for num==4. What about other values of num?

    > root->next=LLtoBST(root->next,mid-1);
    > }
    > return root;
    >
    > }
    >


    Step through this on paper, carefully, for both odd and even values of num.

    Then, once you have a good design, and have coded it so that ther's no
    compile errors, step through it in the debugger and see if it does exactly
    what your paper version did.

    Also, you mention that you're creating a "Binary Search Tree". But you
    don't say whether the linked list is sorted or not. If it isn't then your
    tree isn't going to be sorted, either.

    -Howard
     
    Howard, Jan 19, 2005
    #2
    1. Advertising

  3. pc:

    You should also keep in mind that splitting it down the middle may not
    guarantee the best amortized performance. It depends upon the
    distribution of the queries.

    For example, if you only have right children i.e. with the lowest
    element at the root and the highest element as the (rightmost) leaf,
    this will give the best performance if you're only looking up the
    lowest element.

    If I'm not mistaken, a balanced tree is desirable iff the queries are
    uniformly distributed over the stored items (i.e. if there are no
    queries for items that don't exist). If there are queries for items
    that don't exist, then the analysis gets much hairier.

    Joseph
     
    Joseph Turian, Jan 19, 2005
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Andrew Edwards

    BST & recursion

    Andrew Edwards, Jul 30, 2003, in forum: C++
    Replies:
    12
    Views:
    787
    Karl Heinz Buchegger
    Aug 4, 2003
  2. Rupert harrison

    BST

    Rupert harrison, Sep 15, 2003, in forum: C++
    Replies:
    2
    Views:
    559
    Karl Heinz Buchegger
    Sep 15, 2003
  3. Ridimz

    BST: remove less than

    Ridimz, Oct 4, 2003, in forum: C++
    Replies:
    8
    Views:
    533
    Josh Sebastian
    Oct 7, 2003
  4. Ice
    Replies:
    4
    Views:
    5,015
  5. AshifToday

    BST Source-Code

    AshifToday, May 22, 2005, in forum: C++
    Replies:
    0
    Views:
    624
    AshifToday
    May 22, 2005
Loading...

Share This Page