Rene Rivera ha escrito:
Martin Knoblauch Revuelta wrote:
On 10/31/06, Rene Rivera <grafikrobot@gmail.com> wrote:
* There's no need for the m_next and m_prev fields. You can do inorder, preorder, postorder, and others without them.
Yes, I could, but operators ++ and -- would become O(log n).
I beg to differ. All those traversals can be implemented O(1) per iteration. This is the case for all binary trees.
Umm, it is *amortized* O(1), as allowed by 24.1/8. Without amortization being taken into account, ++ and -- have a worst case complexity O(log n), if I'm not missing something. Although not explicitly stated in the standard, the amortization here has to be done for a complete traversal from begin to end. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo