is there an AVLTree STL class

This is a discussion on is there an AVLTree STL class within the C++ Programming forums, part of the General Programming Boards category; otherwise I'll have to write my own and I dont wanna...

  1. #1
    Registered User
    Join Date
    Jan 2002
    Posts
    552

    is there an AVLTree STL class

    otherwise I'll have to write my own and I dont wanna
    C Code. C Code Run. Run Code Run... Please!

    "Love is like a blackhole, you fall into it... then you get ripped apart"

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >is there an AVLTree STL class
    Not as such, but a lot of times the associative containers are suitable replacements for a proper tree. You also have the option of acquiring a third party tree container, which is to be preferred over writing your own since it's already debugged and working.

    -Prelude
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Jan 2002
    Posts
    552
    hmmm, Im unaware of any that could guarantee log(n) search and deletion as an AVL tree would.

    Also, I had better write my own since Im probably gonna need to be able to do an in-order iteration from an arbitrary position in the tree. No big deal though, I had to write a BST with this capability for class last semester so I guess it wouldnt be too tough to add rotations for the AVL

    Perhaps I should write a Skiplist instead lol.
    C Code. C Code Run. Run Code Run... Please!

    "Love is like a blackhole, you fall into it... then you get ripped apart"

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >hmmm, Im unaware of any that could guarantee log(n) search and deletion as an AVL tree would.
    All of the associative containers require insertions, deletions, and searches to be logarithmic.

    >Perhaps I should write a Skiplist instead lol.
    A tree would be better, skip lists are generally more annoying than even balanced trees in my experience and the lack of familiarity with them for most programmers effects maintenance. You also have to consider speed, while still logarithmic, skip lists are still slower than trees. I would only consider using them when memory is at a premium.

    -Prelude
    My best code is written with the delete key.

  5. #5
    Registered User
    Join Date
    Jan 2002
    Posts
    552
    >All of the associative containers require insertions, deletions, and searches to be logarithmic.

    Isnt it the case that they could degenerate into nearly linear running times?
    C Code. C Code Run. Run Code Run... Please!

    "Love is like a blackhole, you fall into it... then you get ripped apart"

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Isnt it the case that they could degenerate into nearly linear running times?
    Perhaps in a particularly non-conforming and dumb implementation. Here's what the standard says:
    Code:
    a.insert(p,t) 
    logarithmic in general, but amortized constant if t is inserted right after p.
    
    a.erase(q)
    amortized constant
    
    a.find(k)
    logarithmic
    -Prelude
    My best code is written with the delete key.

  7. #7
    Evil Member
    Join Date
    Jan 2002
    Posts
    638
    Really? Wow, I never knew that, I always thought it degenerated to linear if it was filled aasymmetrically.

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I always thought it degenerated to linear if it was filled aasymmetrically.
    The associative containers are most easily implemented with a balanced binary tree, no one in their right mind would allow the worst case tree scenario to occur with a generic library. Besides, to meet the minimum requirements for the standard the implementation has to guarantee logarithmic performance. A basic tree cannot do this (barring a quantum space/time flux, but they're rare in C++).

    -Prelude
    My best code is written with the delete key.

  9. #9
    Evil Member
    Join Date
    Jan 2002
    Posts
    638
    > (barring a quantum space/time flux, but they're rare in C++).

    Perhaps for you, Ms. "I never invoke undefined behavior". Try flushing an input stream whilst modifying an object several times in one sequence point in a program whose main() fincttion is declared as returning void on a decently powerful chip. BAM, instant temporal anomaly.

  10. #10
    Registered User
    Join Date
    Jan 2002
    Posts
    552
    whatever that means lol
    C Code. C Code Run. Run Code Run... Please!

    "Love is like a blackhole, you fall into it... then you get ripped apart"

  11. #11
    Evil Member
    Join Date
    Jan 2002
    Posts
    638
    Well I just mean that rending the fabric of time itself is as likely an outcome of running the program I described as any other.

  12. #12
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >BAM, instant temporal anomaly.
    Code:
    /* If you run this you'll be thrown into Sliders episode 12 */
    float *main(double argc, int **argv)
    {
      char *p;
    
      fflush ( printf ( "%s%lf", argv[*(int *)&argc], p += 5 - *p++ / 2 ) );
    
      return "Wait for me professor!";
    }
    -Prelude
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. deriving classes
    By l2u in forum C++ Programming
    Replies: 12
    Last Post: 01-15-2007, 04:01 PM
  2. Need help to build network class
    By weeb0 in forum C++ Programming
    Replies: 0
    Last Post: 02-01-2006, 10:33 AM
  3. help with STL container remove_if on a class
    By Syneris in forum C++ Programming
    Replies: 19
    Last Post: 01-31-2006, 12:56 AM
  4. im extreamly new help
    By rigo305 in forum C++ Programming
    Replies: 27
    Last Post: 04-23-2004, 11:22 PM
  5. structure vs class
    By sana in forum C++ Programming
    Replies: 13
    Last Post: 12-02-2002, 06:18 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21