Re: No trees in the stdlib?

In message <mailman.2144.1245999295.8015.python-list@xxxxxxxxxx>, Miles
Kaufmann wrote:

On Jun 26, 2009, at 2:23 AM, Chris Rebert wrote:

That's pretty much the bisect module in a nutshell. It manipulates a
sorted list using binary search.

With O(n) insertions and removals, though. A decent self-balancing
binary tree will generally do those in O(log n).

For values of n below, say, a million, would you even notice the difference
on modern hardware?

.

Relevant Pages

  • Re: Fortran to find nearest point from set in 3-D
    ... binary search. ... you need an extension of a binary tree to 3-D. ... as well as the algorithms above). ... you'll find a pile of technical papers describing various ...
    (sci.math.num-analysis)
  • Re: Search a list/array of objects for specified criteria?
    ... even where the distribution is uneven. ... we are not talking about a binary tree. ... We are talking about using a binary search algorithm over a sorted list. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: ArrayList BinarySearch vs Contains
    ... thought O notation always represented worst-case, so thanks for correcting me. ... it is NOT true that "the worst-case in a binary search would be ... binary tree, a search on that tree could be as bad as O. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: ArrayList BinarySearch vs Contains
    ... This means that the worst case scenario would be ... it is NOT true that "the worst-case in a binary search would be ... binary tree, a search on that tree could be as bad as O. ... Pete ...
    (microsoft.public.dotnet.languages.csharp)
Loading