Balanced trees

Steven D'Aprano steve+comp.lang.python at
Wed Mar 19 02:15:23 CET 2014

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

> Dan Stromberg <drsalists at>:

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


More information about the Python-list mailing list