Message176720
| 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 |
<201211302325.37439.storchaka@gmail.com> |
| In-reply-to |
<1354307739.71.0.325990342727.issue14621@psf.upfronthosting.co.za> |
| 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).
Agree. However I think that for large enough data a balanced tree is slower
than a hashtable with any slow hash. |
|
History
|
|---|
| Date |
User |
Action |
Args |
| 2012年11月30日 21:25:55 | serhiy.storchaka | set | recipients:
+ 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:54 | serhiy.storchaka | link | issue14621 messages |
| 2012年11月30日 21:25:54 | serhiy.storchaka | create |
|