Binary search tree: traverse: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 13: Line 13:


== Abstract View ==
== Abstract View ==
'''Invariant:''' Before and after each iteration:
# <math>S</math> contains all nodes on the path (called the '''current path''') from the root to some binary search tree node (called the '''current node''') in the order from the root to the current node (in particualr, the current node is the top element of <math>S</math>).
# Let '''''elem''''' be some element of the stack:]
## If <math>elem.seendChildren = 0</math>, neither <math>elem.node.key</math> nor one of the keys in the [[Directed Tree|subtree]] rooted at <math>elem.node.right</math> has been appended to <math>L</math> so far; possibly, some or all keys in the subtree rooted at <math>elem.node.left</math> have already been appended.
## If <math>elem.seenChildren = 1</math>, all keys in the [[Directed Tree|subtree]] rooted at <math>elem.node.left</math> and, afterwards, <math>elem.node.key</math> have already been appended to <math>L</math>; possibly, some or all keys in the subtree rooted at <math>elem.node.right</math> have been appended as well.
## If <math>elem.seendChildren = 2</math>, all keys in the [[Directed Tree|subtree]] rooted at <math>elem.node</math> have been appended to <math>L</math>
'''Variant:''' Indentify the current content of <math>S</math>  with the string of length <math>|S|</math> over the alphabet <math>\{0,1,2\}</math> that is formed by the <math>seenChildren</math> values of the stack elements <in the order from the root to the current node). Then the current string immediately '''after''' the iteration
# is either empty (which, clearly, is tantamount to <math>S</math> being empty),
# or it is lexicographically larger than the string immediately '''before''' the iteration.
'''Break condition:''' <math>S</math> is empty.


== Induction Basis ==
== Induction Basis ==

Revision as of 20:26, 25 September 2014


Genaral Information

Algorithmic problem: Sorted sequence: traverse

Type of algorithm: loop

Auxiliary data:

  1. A stack S whose elements are pairs consisting of
    1. a natural number seenChildren in the range [math]\displaystyle{ \{0,1,2\} }[/math] and
    2. a binary search tree node node.
  2. Pointers elem and elem' to stack elements.

Abstract View

Invariant: Before and after each iteration:

  1. [math]\displaystyle{ S }[/math] contains all nodes on the path (called the current path) from the root to some binary search tree node (called the current node) in the order from the root to the current node (in particualr, the current node is the top element of [math]\displaystyle{ S }[/math]).
  2. Let elem be some element of the stack:]
    1. If [math]\displaystyle{ elem.seendChildren = 0 }[/math], neither [math]\displaystyle{ elem.node.key }[/math] nor one of the keys in the subtree rooted at [math]\displaystyle{ elem.node.right }[/math] has been appended to [math]\displaystyle{ L }[/math] so far; possibly, some or all keys in the subtree rooted at [math]\displaystyle{ elem.node.left }[/math] have already been appended.
    2. If [math]\displaystyle{ elem.seenChildren = 1 }[/math], all keys in the subtree rooted at [math]\displaystyle{ elem.node.left }[/math] and, afterwards, [math]\displaystyle{ elem.node.key }[/math] have already been appended to [math]\displaystyle{ L }[/math]; possibly, some or all keys in the subtree rooted at [math]\displaystyle{ elem.node.right }[/math] have been appended as well.
    3. If [math]\displaystyle{ elem.seendChildren = 2 }[/math], all keys in the subtree rooted at [math]\displaystyle{ elem.node }[/math] have been appended to [math]\displaystyle{ L }[/math]

Variant: Indentify the current content of [math]\displaystyle{ S }[/math] with the string of length [math]\displaystyle{ |S| }[/math] over the alphabet [math]\displaystyle{ \{0,1,2\} }[/math] that is formed by the [math]\displaystyle{ seenChildren }[/math] values of the stack elements <in the order from the root to the current node). Then the current string immediately after the iteration

  1. is either empty (which, clearly, is tantamount to [math]\displaystyle{ S }[/math] being empty),
  2. or it is lexicographically larger than the string immediately before the iteration.

Break condition: [math]\displaystyle{ S }[/math] is empty.

Induction Basis

Induction Step

Complexity

Pseudocode

INORDER-TREE-WALK(x)
if x ≠ NULL
INORDER-TREE-WALK(left[x])
print key[x]
INORDER-TREE-WALK(right[x])