Linearly ordered lists
Linearly ordered list
Linearly ordered list is a sequence whose elements are linearly ordered (linear order), which is not necessarily the order of listing.
For example:
Link to original
- A list of natural numbers can be ordered by the relation.
- A list of words can be ordered by the lexicographical order relation, . As below.
Searching for items in a linearly ordered list is important and Binary search trees are particularly useful in representing elements in such a list. There are very efficient methods for:
- searching for data in binary search trees
- revising data in binary search trees
- converting linaerly ordered lists to binary search trees and back
title: Example: lexicographical order on words
First, we order the letters of the English alphabet as usual:
$$
a \prec b \prec c \prec d \prec e \prec ... \prec x \prec y \prec z
$$
Then, we can use this ordering of the letters to order longer words:
- Given two words $w_1$ and $w_2$, we compare them letter by letter, from left to right, passing equal letters.
- If at any point a letter in $w_1$ is $\prec$-smaller than the corresponding letter in $w_2$, then we put $w_1 \prec w_2$.
- If every letter in $w_1$ is equal to the corresponding letter in $w_2$ but $w_2$ is longer than $w_1$, then we also put $w_1 \prec w_2$.
- In any other case, we put $w_2 \prec w_1$.
$$
\text{discreet} \prec \text{discreetness} \prec \text{discrete} \prec \text{discretion} \prec \text{geography}
$$
$$
\prec \text{geology} \prec \text{mathematics} \prec \text{physics} \prec \text{psychology}
$$