This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author serhiy.storchaka
Recipients Arfrever, Giovanni.Bajo, PaulMcMillan, ReneSac, Vlado.Boza, alex, arigo, benjamin.peterson, camara, christian.heimes, cvrebert, dmalcolm, gregory.p.smith, koniiiik, lemburg, mark.dickinson, sbermeister, serhiy.storchaka, vstinner, Łukasz.Rekucki
Date 2012-11-30.21:25:54
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
In-reply-to <>
> Serhiy Storchaka: Yes, but it is still O(log n) worst case. Even in the
> worst case rebalancing, you only need to walk up/down rotating/spliting
> every node in your path. As the tree height is guaranteed to be x * log n
> (x from 1 to 2, depending on the algorithm), the rebalancing operation is
> aways limited by O(log n).

Agree. However I think that for large enough data a balanced tree is slower 
than a hashtable with any slow hash.
Date User Action Args
2012-11-30 21:25:55serhiy.storchakasetrecipients: + serhiy.storchaka, lemburg, arigo, gregory.p.smith, mark.dickinson, vstinner, christian.heimes, benjamin.peterson, Arfrever, alex, cvrebert, dmalcolm, Giovanni.Bajo, PaulMcMillan, Vlado.Boza, koniiiik, sbermeister, camara, Łukasz.Rekucki, ReneSac
2012-11-30 21:25:54serhiy.storchakalinkissue14621 messages
2012-11-30 21:25:54serhiy.storchakacreate