➜

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 ReneSac
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.20:35:39
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1354307739.71.0.325990342727.issue14621@psf.upfronthosting.co.za>
In-reply-to
Content 
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).
History
Date User Action Args
2012-11-30 20:35:39ReneSacsetrecipients: + ReneSac, lemburg, arigo, gregory.p.smith, mark.dickinson, vstinner, christian.heimes, benjamin.peterson, Arfrever, alex, cvrebert, dmalcolm, Giovanni.Bajo, PaulMcMillan, serhiy.storchaka, Vlado.Boza, koniiiik, sbermeister, camara, Łukasz.Rekucki
2012-11-30 20:35:39ReneSacsetmessageid: <1354307739.71.0.325990342727.issue14621@psf.upfronthosting.co.za>
2012-11-30 20:35:39ReneSaclinkissue14621 messages
2012-11-30 20:35:39ReneSaccreate