Thread: is there an AVLTree STL class

otherwise I'll have to write my own and I dont wanna

>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

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.

>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

>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?

>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

>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

whatever that means lol

>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