Balanced trees

[Steven D'Aprano]

On Wed, 19 Mar 2014 01:11:33 +0200, Marko Rauhamaa wrote:

> Dan Stromberg <drsalists at gmail.com>:

>> Rather than throw out unbalanced binary tree altogether, it makes more
>> sense to run it until it gets "too slow".
> 
> I disagree strongly. You should throw out unbalanced binary trees and
> linked lists and the like and concentrate on solid contenders.

If you are in a position to randomize the data before storing it in the 
tree, an unbalanced binary tree is a solid contender. The overhead will 
likely be much less than any balanced tree, and the probability of 
degenerate behaviour negligible for any amount of data big enough to 
really matter.



-- 
Steven