Serhiy Storchaka added the comment: > 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. ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue14621> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
