Sorted sequence

From Algowiki
Revision as of 11:19, 26 September 2014 by Jhohmann (talk | contribs) (→‎Remark)
Jump to navigation Jump to search


General Information

Representation invariant:

  1. The abstract data structure sorted sequence implements sorted sequences as defined here.
  2. This abstract data structure is generic and parameterized by a fixed key type [math]\displaystyle{ \kappa }[/math] and a fixed comparision [math]\displaystyle{ c }[/math] defined on [math]\displaystyle{ \kappa }[/math].

Constructor: Gets a comparision [math]\displaystyle{ c }[/math] and initializes ths sequence so as to be empty.

Insert

Input: A key [math]\displaystyle{ K \in \kappa }[/math].

Output:

Precondition:

Postcondition: A new element with the key [math]\displaystyle{ K }[/math] is inserted at the appropriate position in sorting order.

Traverse

Input:

Output: A Linear sequence [math]\displaystyle{ L }[/math] containing all elements of the sorted sequence in ascending order.

Precondition:

Postcondition: All keys of the sorted sequence are appended to [math]\displaystyle{ L }[/math] in ascending order.

Find

Input: A key [math]\displaystyle{ K \in \kappa }[/math].

Output: A Boolean value, which is true if, and only if, [math]\displaystyle{ K }[/math] is currently contained in the sequence.

Precondition:

Postcondition:

Remove

Input: A key [math]\displaystyle{ K \in \kappa }[/math].

Output: A Boolean value, which is true if, and only if, [math]\displaystyle{ K }[/math] is currently stored in the sequence.

Precondition:

Postcondition: If the output is true, one occurrence of [math]\displaystyle{ K }[/math] is removed.

Known Implementations

  1. B-Trees
  2. Binary Search Tree

Remark

  • The number, find, find at position, and remove methods are identical to those of Linear sequences, so they are omitted here.
  • For method traverse see also the remark on iterators for Linear sequences.