Sorted sequence

From Algowiki
Jump to: navigation, 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]\mathcal{K}[/math] and a fixed comparison [math]c[/math] defined on [math]\mathcal{K}[/math].

Constructor

Gets a comparison [math]c[/math] to maintain and initializes the sequence so as to be empty.


Insert

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

Output: None.

Precondition: None.

Postcondition: A new element with the key [math]K[/math] is inserted at an appropriate position in sorting order, so the sorting order is maintained.

Traverse

Input: None.

Output: A linear list structure [math]L[/math] containing all elements of the sorted sequence in ascending order.

Precondition: None.

Postcondition: None.

Find

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

Output: A Boolean value, which is true if, and only if, at least one occurrence of [math]K[/math] is currently contained in the sequence.

Precondition: None.

Postcondition: None.

Remove

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

Output: A Boolean value, which is true if, and only if, at least one occurrence of [math]K[/math] is currently contained in the sequence.

Precondition: None.

Postcondition: If the output is true, exactly one occurrence of [math]K[/math] is removed. The choice of the occurrence to be removed is unspecified.

Known Implementations

  1. B-Trees
  2. Binary Search Tree