Binary search tree: traverse: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(15 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[Category:Binary Search Tree]]
[[Category:Videos]]
 
[[Category:Algorithms]]
[[Category:Search Algorithms]]
[[Category:Tree Algorithms]]
[[Category:Binary_Search_Tree]]
{{#ev:youtube|https://www.youtube.com/watch?v=PXqM9q57BMk|500|right|Binary search tree: traverse|frame}}
== Genaral Information ==
== Genaral Information ==
'''Algorithmic problem:''' [[Sorted sequence|Sorted sequence: traverse]]
'''Algorithmic problem:''' [[Sorted sequence#Traverse|Sorted sequence: traverse]]


'''Type of algorithm:''' loop
'''Type of algorithm:''' loop


'''Auxiliary data:'''
'''Auxiliary data:'''
# A [[stack]] '''''S''''' whose elements are pairs consisting of
# A [[Sets and sequences#Stacks and queues|stack]] '''''S''''' whose elements are pairs consisting of
## a natural number '''''seenChildren''''' in the range <math>\{0,1,2\}</math> and
## a natural number '''''seenChildren''''' in the range <math>\{0,1,2\}</math> and
## a binary search tree node '''''node'''''.
## a binary search tree node '''''node'''''.
Line 14: Line 18:
== Abstract View ==
== Abstract View ==
'''Invariant:''' Before and after each iteration:
'''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>).
# <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 particular, the current node is the top element of <math>S</math>).
# Let '''''elem''''' be some element of the stack:]
# 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 = 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.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>
## If <math>elem.seenChildren = 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
'''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
Line 25: Line 29:


'''Break condition:''' <math>S</math> is empty.
'''Break condition:''' <math>S</math> is empty.
'''Remark:''' The number of iterations accomplished so far is the natural induction parameter. For conciseness, the induction parameter is omitted in the following.


== Induction Basis ==
== Induction Basis ==
'''Abstract view:''' Initialize <math>S</math> with the root.
'''Implementation:'''
# Create a new stack element <math>elem</math>.
# Set <math> elem.node := root</math>.
# Set <math> elem.seenChildren := 0</math>.
# Ensure that <math>S</math> is empty.
# <math>S.push(elem)</math>.
'''Proof:''' All invariants are trivially fulfilled.


== Induction Step ==
== Induction Step ==
'''Abstract view:'''
# If the left child of the current node has not yet been examined:
## If the left child of the current node exists, proceed to the left child.
#Otherwise, if the right child of the current node has not yet been examined:
## Append the key of the current node to <math>L</math>.
## If the right child of the current node exists, proceed to the right child.
#Otherwise (that is, left and right child examined), proceed to the parent of the current node.
'''Implementation:'''
# Set <math>elem := S.top()</math>.
# Set <math>node := elem.node</math>
# If <math>elem.seenChildren = 0</math>:
## If <math>node.left \neq void</math>:
### Create a new element <math>elem'</math>.
### Set <math>elem'.node := node.left</math>.
### Set <math>elem'.seenChildren := 0</math>.
### <math>S.push(elem')</math>.
## Otherwise:
### Set <math>elem.seenChildren := 1</math>.
### <math>L.append(elem.node.key)</math>.
# Otherwise, if <math>elem.seenChildren = 1</math>:
## If <math>node.right \neq void</math>:
### Create a new elem <math>elem'</math>.
### Set <math>elem'.node := node.right</math>.
### Set <math>elem'.seenChildren := 0</math>.
### <math>S.push(elem')</math>.
## Otherwise, set <math>elem.seenChildren := 2</math>.
# Otherwise, (that is <math>elem.seenChildren = 2</math>).
## <math>S.pop()</math>.
## If <math>S</math> is empty, terminate the algorithm.
## Set <math>elem := S.top()</math>
## Set <math>elem.seenChildren := elem.seenChildren + 1</math>.
## If <math>elem.seenChildren = 1</math> and <math>elem.node.left \neq void</math> then: <math>L.append(elem.node.key)</math>.
'''Correctness:''' Invariant #1 follows immediately from the fact that each push operation simply extends the current path and each pop operation cuts off the end node of the current path. Next consider Invariant #2.
Invariant #2 is trivially maintained both for <math>elem</math> and <math>elem'</math> in Steps 3.1 and 4.1 and <math>elem</math> in Step 3.2 and 4.2 (note the append operation in Step 2.2, which reflects the inclusion of the current node in Invariant 2.2). In Step 5, the algorithm returns from a non-empty subtree, so the increase of <math>seenChildren</math> and the append in case <math>seenChildren = 1</math> are correct. Note that each key is appended only once because Step 3.2.2 applies only if the left child is empty, and Step 5.4, only if the left child is '''not''' empty.
Finally, consider the variant. Whenever a new element is pushed, the new string is an extension of the old string, which is clearly lexicographically larger. On the other hand, whenever an element is removed from <math>S</math>, Step 5.4 ensures that the new string is not just a prefix of the old string but is larger at the last position of the new string (which is the second last position of the old string).


== Complexity ==
== Complexity ==
'''Statement:''' Linear in the length of the sequence in the worst case.
'''Proof:''' Each iteration of the loop takes constant time. Each node is visited in a most three iterations, viz. once with <math>seenChildren = 0,1,2</math> respectively. This obvservation proves the claim.


== Pseudocode ==
== Pseudocode ==

Latest revision as of 13:41, 3 March 2017

Binary search tree: traverse

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 particular, 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.seenChildren = 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.seenChildren = 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.

Remark: The number of iterations accomplished so far is the natural induction parameter. For conciseness, the induction parameter is omitted in the following.

Induction Basis

Abstract view: Initialize [math]\displaystyle{ S }[/math] with the root.

Implementation:

  1. Create a new stack element [math]\displaystyle{ elem }[/math].
  2. Set [math]\displaystyle{ elem.node := root }[/math].
  3. Set [math]\displaystyle{ elem.seenChildren := 0 }[/math].
  4. Ensure that [math]\displaystyle{ S }[/math] is empty.
  5. [math]\displaystyle{ S.push(elem) }[/math].

Proof: All invariants are trivially fulfilled.

Induction Step

Abstract view:

  1. If the left child of the current node has not yet been examined:
    1. If the left child of the current node exists, proceed to the left child.
  2. Otherwise, if the right child of the current node has not yet been examined:
    1. Append the key of the current node to [math]\displaystyle{ L }[/math].
    2. If the right child of the current node exists, proceed to the right child.
  3. Otherwise (that is, left and right child examined), proceed to the parent of the current node.

Implementation:

  1. Set [math]\displaystyle{ elem := S.top() }[/math].
  2. Set [math]\displaystyle{ node := elem.node }[/math]
  3. If [math]\displaystyle{ elem.seenChildren = 0 }[/math]:
    1. If [math]\displaystyle{ node.left \neq void }[/math]:
      1. Create a new element [math]\displaystyle{ elem' }[/math].
      2. Set [math]\displaystyle{ elem'.node := node.left }[/math].
      3. Set [math]\displaystyle{ elem'.seenChildren := 0 }[/math].
      4. [math]\displaystyle{ S.push(elem') }[/math].
    2. Otherwise:
      1. Set [math]\displaystyle{ elem.seenChildren := 1 }[/math].
      2. [math]\displaystyle{ L.append(elem.node.key) }[/math].
  4. Otherwise, if [math]\displaystyle{ elem.seenChildren = 1 }[/math]:
    1. If [math]\displaystyle{ node.right \neq void }[/math]:
      1. Create a new elem [math]\displaystyle{ elem' }[/math].
      2. Set [math]\displaystyle{ elem'.node := node.right }[/math].
      3. Set [math]\displaystyle{ elem'.seenChildren := 0 }[/math].
      4. [math]\displaystyle{ S.push(elem') }[/math].
    2. Otherwise, set [math]\displaystyle{ elem.seenChildren := 2 }[/math].
  5. Otherwise, (that is [math]\displaystyle{ elem.seenChildren = 2 }[/math]).
    1. [math]\displaystyle{ S.pop() }[/math].
    2. If [math]\displaystyle{ S }[/math] is empty, terminate the algorithm.
    3. Set [math]\displaystyle{ elem := S.top() }[/math]
    4. Set [math]\displaystyle{ elem.seenChildren := elem.seenChildren + 1 }[/math].
    5. If [math]\displaystyle{ elem.seenChildren = 1 }[/math] and [math]\displaystyle{ elem.node.left \neq void }[/math] then: [math]\displaystyle{ L.append(elem.node.key) }[/math].

Correctness: Invariant #1 follows immediately from the fact that each push operation simply extends the current path and each pop operation cuts off the end node of the current path. Next consider Invariant #2.

Invariant #2 is trivially maintained both for [math]\displaystyle{ elem }[/math] and [math]\displaystyle{ elem' }[/math] in Steps 3.1 and 4.1 and [math]\displaystyle{ elem }[/math] in Step 3.2 and 4.2 (note the append operation in Step 2.2, which reflects the inclusion of the current node in Invariant 2.2). In Step 5, the algorithm returns from a non-empty subtree, so the increase of [math]\displaystyle{ seenChildren }[/math] and the append in case [math]\displaystyle{ seenChildren = 1 }[/math] are correct. Note that each key is appended only once because Step 3.2.2 applies only if the left child is empty, and Step 5.4, only if the left child is not empty. Finally, consider the variant. Whenever a new element is pushed, the new string is an extension of the old string, which is clearly lexicographically larger. On the other hand, whenever an element is removed from [math]\displaystyle{ S }[/math], Step 5.4 ensures that the new string is not just a prefix of the old string but is larger at the last position of the new string (which is the second last position of the old string).

Complexity

Statement: Linear in the length of the sequence in the worst case.

Proof: Each iteration of the loop takes constant time. Each node is visited in a most three iterations, viz. once with [math]\displaystyle{ seenChildren = 0,1,2 }[/math] respectively. This obvservation proves the claim.

Pseudocode

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