1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
\chapter{TSet}
Implements container for storing ordered set of unique elements.
Takes 2 arguments for specialization, first one is type of elements, second one is comparator class.
Usage example:
\lstinputlisting[language=Pascal]{setexample.pp}
Some methods return type of PNode. It has field Data, which can be used for retrieving data from
that node. This node can be also used for navigation between elements by methods of set class.
(But don't do anything else with it, you can lose data integrity.)
Memory complexity:
Size of stored elements + constant overhead for each stored element (3 pointers + one boolean).
Members list:
\begin{longtable}{|m{10cm}|m{5cm}|}
\hline
Method & Complexity guarantees \\ \hline
\multicolumn{2}{|m{15cm}|}{Description} \\ \hline\hline
\verb!Create! & O(1) \\ \hline
\multicolumn{2}{|m{15cm}|}{Constructor. Creates empty set.} \\ \hline\hline
\verb!function Size(): SizeUInt! & O(1) \\ \hline
\multicolumn{2}{|m{15cm}|}{Returns number of elements in set.} \\\hline\hline
\verb!procedure Insert(value: T)! &
O(lg N), N is number of elements in set \\ \hline
\multicolumn{2}{|m{15cm}|}{Inserts element into set.} \\\hline\hline
\verb!procedure Delete(value: T)! &
O(lg N), N is number of elements in set \\ \hline
\multicolumn{2}{|m{15cm}|}{Deletes value from set. If element is not in set, nothing happens.} \\\hline\hline
\verb!function Find(value: T):PNode! & O(lg N) \\\hline
\multicolumn{2}{|m{15cm}|}{Searches for value in set. If value is not there returns nil. Otherwise
returns pointer to tree node (type PNode), which can be used for retrieving data from set.} \\\hline\hline
\verb!function FindLess(value: T):PNode! & O(lg N) \\\hline
\multicolumn{2}{|m{15cm}|}{Searches for greatest element less than value in set. If such element is not there returns nil. Otherwise
returns pointer to tree node (type PNode), which can be used for retrieving data from set.} \\\hline\hline
\verb!function FindLessEqual(value: T):PNode! & O(lg N) \\\hline
\multicolumn{2}{|m{15cm}|}{Searches for greatest element less or equal than value in set. If such element is not there returns nil. Otherwise
returns pointer to tree node (type PNode), which can be used for retrieving data from set.} \\\hline\hline
\verb!function FindGreater(value: T):PNode! & O(lg N) \\\hline
\multicolumn{2}{|m{15cm}|}{Searches for smallest element greater than value in set. If such element is not there returns nil. Otherwise
returns pointer to tree node (type PNode), which can be used for retrieving data from set.} \\\hline\hline
\verb!function FindGreaterEqual(value: T):PNode! & O(lg N) \\\hline
\multicolumn{2}{|m{15cm}|}{Searches for smallest element greater or equal than value in set. If such element is not there returns nil. Otherwise
returns pointer to tree node (type PNode), which can be used for retrieving data from set.} \\\hline\hline
\verb!function Min:PNode! & O(lg N) \\\hline
\multicolumn{2}{|m{15cm}|}{Returns node containing smallest element of set. If set is empty returns
nil.} \\\hline\hline
\verb!function Max:PNode! & O(lg N) \\\hline
\multicolumn{2}{|m{15cm}|}{Returns node containing largest element of set. If set is empty returns
nil.} \\\hline\hline
\verb!function Next(x:PNode):PNode! & O(lg N) worst case, but traversal from smallest element to
largest takes O(N) time \\\hline
\multicolumn{2}{|m{15cm}|}{Returns successor of x. If x is largest element of set, returns nil.} \\\hline\hline
\verb!function Prev(x:PNode):PNode! & O(lg N) worst case, but traversal from largest element to
smallest takes O(N) time \\\hline
\multicolumn{2}{|m{15cm}|}{Returns predecessor of x. If x is smallest element of set, returns nil.} \\\hline\hline
\verb!function IsEmpty(): boolean! & O(1) \\ \hline
\multicolumn{2}{|m{15cm}|}{Returns true when set is empty.} \\\hline
\end{longtable}
|
