Classes

A counted, self-balancing (AVL) binary search tree. Counted means that there are no duplicate nodes with the same value, but values have counts associated with them. BSTree provides much the same capabilities as Java’s TreeSet, except that it is also counted, provides a running median, and, if the values are numeric, provides a running sum.

The type of value being stored must be Comparable, or a comparator of type Ordered must be supplied. The comparator can also be given to override a Comparable type’s innate ordering (e.g. to make the ordering of String values case insentitive). If a comparator isn’t given, the ordering is from min to max.

Insertions, deletions, and specific value queries (index, contains, count, ceiling, floor, higher, lower) have time complexity O(logN). General queries, i.e. the count of unique values, the count of total values, tree height, first, last, and median are all O(1). If the values are numeric, the sum of all values is also available in O(1). Traversing the tree in order, first to last or vice-versa, is O(N).

BSTree conforms to the BidirectionalCollection protocol, and meets all of that protocol’s expected performance requirements. It also conforms to Equatable and NSCopying.

The elements of the Collection are tuples of the form (value: T, count: Int). The indices of the Collection are of non-numeric type BSTreeIndex.

let tree = BSTree(14, 32, 14)  // Don't need comparator, because Int is Comparable
tree.insert(-2)
tree.insert(42, count: 2)      // Insert 2 of value 42
tree.removeAll(14)             // Remove both 14's
print(tree)

   32
  /  \
-2    42(2)

tree.height                    // 1
tree.count                     // 3
tree.totalCount                // 4
tree.firstValue                // -2
tree.lastValue                 // 42
tree.medianValues              // [32, 42]
tree.sum                       // 114
tree.contains(-2)              // true
tree.count(42)                 // 2
tree.ceilingValue(30)          // 32
tree.ceilingValue(32)          // 32
tree.floorValue(32)            // 32
tree.floorValue(35)            // 32
tree.higherValue(32)           // 42
tree.lowerValue(32)            // -2
Array(tree)                    // [(value: -2, count: 1), (value: 32, count: 1), (value: 42, count: 2)]
for elem in tree {
    print("value = \(elem.value), count = \(elem.count)")
}

value = -2, count = 1
value = 32, count = 1
value = 42, count = 2

let index = tree.indexOf(42)    // Type BSTreeIndex<Int>
if let index = index {
    let index2 = tree.index(before: index)
    print("value = \(tree[index2].value), count = \(tree[index2].count)")
}

value = 32, count = 1

See more

public class BSTree<T> : NSCopying where T : Equatable

extension BSTree: Equatable

extension BSTree: CustomStringConvertible

extension BSTree: BidirectionalCollection

A disjoint-set data structure, also known as union-find or merge-find. The data structure stores associations between unique values of type T. Two values are in the same subset if there are associations that link them. The structure allows you to quickly determine whether two values are in the same subset.

There are two methods used to set the associations and determine whether two values are in the same subset:

union(v1, v2) merges the subsets containing v1 and v2, if they’re not already in the same subset.

find(v) returns the root value of the subset. Two values v1 and v2 are in the same subset iff find(v1) = find(v2).

From Wikipedia: While there are several ways of implementing disjoint-set data structures, in practice they are often identified with a particular implementation called a disjoint-set forest. This is a specialized type of forest which performs unions and finds in near constant amortized time. To perform a sequence of m addition, union, or find operations on a disjoint-set forest with n nodes requires total time O(mα(n)), where α(n) is the extremely slow-growing inverse Ackermann function. Disjoint-set forests do not guarantee this performance on a per-operation basis. Individual union and find operations can take longer than a constant times α(n) time, but each operation causes the disjoint-set forest to adjust itself so that successive operations are faster. Disjoint-set forests are both asymptotically optimal and practically efficient.

let ds = DisjointSetTree<Int>()
ds.union(2, 3)
ds.union(3, 4)
ds.find(1)     // 1
ds.find(2)     // 3
ds.find(3)     // 3
ds.find(4)     // 3   (2, 3, and 4 are in the same subset)
ds.find(5)     // 5
print(ds)

4: root = 3
2: root = 3
3: root = 3

See more

public class DisjointSetTree<T> : CustomStringConvertible where T : Hashable