Author ReneSac
Recipients Arfrever, Giovanni.Bajo, PaulMcMillan, ReneSac, Vlado.Boza, alex, arigo, benjamin.peterson, camara, christian.heimes, cvrebert, dmalcolm, gregory.p.smith, haypo, koniiiik, lemburg, mark.dickinson, sbermeister, serhiy.storchaka, Ł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, haypo, 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