Once a node has been found in a balanced tree, the ''next'' or ''previous'' nodes can be explored in [[amortized complexity|amortized]] constant time. Some instances of exploring these "nearby" nodes require traversing up to 2×log(''n'') links (particularly when moving from the rightmost leaf of the root's left sub tree to the leftmost leaf of the root's right sub tree; in the example AVL tree, moving from node 14 to the ''next but one'' node 19 takes 4 steps). However, exploring all ''n'' nodes of the tree in this manner would use each link exactly twice: one traversal to enter the sub tree rooted at that node, another to leave that node's sub tree after having explored it. And since there are ''n''−1 links in any tree, the amortized cost is found to be 2×(''n''−1)/''n'', or approximately 2. |
Once a node has been found in a balanced tree, the ''next'' or ''previous'' nodes can be explored in [[amortized complexity|amortized]] constant time. Some instances of exploring these "nearby" nodes require traversing up to 2×log(''n'') links (particularly when moving from the rightmost leaf of the root's left sub tree to the leftmost leaf of the root's right sub tree; in the example AVL tree, moving from node 14 to the ''next but one'' node 19 takes 4 steps). However, exploring all ''n'' nodes of the tree in this manner would use each link exactly twice: one traversal to enter the sub tree rooted at that node, another to leave that node's sub tree after having explored it. And since there are ''n''−1 links in any tree, the amortized cost is found to be 2×(''n''−1)/''n'', or approximately 2. |