BSTree

public class BSTree<T> : NSCopying where T : Equatable
extension BSTree: Equatable
extension BSTree: CustomStringConvertible
extension BSTree: BidirectionalCollection

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

  • True if the tree is a valid binary search tree, meaning that the value of the root node is greater than the value of its left child, and less than that of its right child, and all subtrees meet the same requirement. Note that if only the public functions (insert and remove) are used to modify the tree, it should always be valid.

    Declaration

    Swift

    public var isValid: Bool { get }

  • True if the tree is balanced, meaning that the height of the left subtree of the root is no more than one different from the height of the right subtree, and all subtrees meet the same requirement. Note that if only the public functions (insert and remove) are used to modify the tree, it should always be balanced.

    Declaration

    Swift

    public var isBalanced: Bool { get }

Constructors

  • Initialize with comparator (optional if T is Comparable).

    Declaration

    Swift

    public init(ordered: @escaping Ordered<T>)

    Parameters

    ordered

    Ordered ((T, T) -> Bool)

  • Initialize with an NSCountedSet and comparator (optional if T is Comparable).

    Declaration

    Swift

    public convenience init(countedSet: NSCountedSet, ordered: @escaping Ordered<T>)

    Parameters

    countedSet

    NSCountedSet
    ordered

    Ordered ((T, T) -> Bool)

  • Initialize with an unsorted sequence of values, which can contain duplicates, and a comparator (optional if T is Comparable).

    Declaration

    Swift

    public convenience init<S>(_ vals: S, ordered: @escaping Ordered<T>) where T == S.Element, S : Sequence

    Parameters

    values

    Array
    ordered

    Ordered ((T, T) -> Bool)

Copying

  • Returns a copy of the tree (a shallow copy if T is a reference type).

    Example:

    let tree = BSTree(4, -9, 12, 3, 0, 65, -20, 4, 6)
let tree2 = tree.copy() as! BSTree<Int>

    Declaration

    Swift

    public func copy(with zone: NSZone? = nil) -> Any

Modifying the Tree

  • Insert the given value into the tree. If the value is already in the tree, the count is incremented by one. Time complexity: O(logN)

    Declaration

    Swift

    public func insert(_ val: T)

    Parameters

    val

    The value to insert one of

  • Insert multple values separated by commas. Time complexity: O(log(Nm)) , where m is the number of values being inserted.

    Declaration

    Swift

    public func insert(_ vals: T...)

    Parameters

    vals

    The values to insert

  • Insert the given number of the given value into the tree. If the value is already in the tree, the count is incremented by the given number. Time complexity: O(logN)

    Declaration

    Swift

    public func insert(_ val: T, count: Int)

    Parameters

    val

    The value to insert count of
    count

    The number of val to insert

  • Insert multiple values from a sequence. Time complexity: O(log(Nm)), where m is the number of values being inserted.

    Declaration

    Swift

    public func insert<S>(_ vals: S) where T == S.Element, S : Sequence

    Parameters

    vals

    The values to insert

  • Remove one of the given value from the tree. If the number of the value already in the tree is more than one, the number is decremented by one, otherwise the value is removed from the tree. Time complexity: O(logN)

    Declaration

    Swift

    public func remove(_ val: T)

    Parameters

    val

    The value to remove one of

  • Remove multple values separated by commas. Time complexity: O(log(Nm)), where m is the number of values being removed.

    Declaration

    Swift

    public func remove(_ vals: T...)

    Parameters

    vals

    The values to remove

  • Remove the given number of the given value from the tree. If the given number is >= the number of the value in the tree, the value is removed completed. Time complexity: O(logN)

    Declaration

    Swift

    public func remove(_ val: T, count: Int)

    Parameters

    val

    The value to remove count of
    count

    The number of val to remove

  • Remove from the tree the values given in a sequence. Time complexity: O(log(Nm)), where m is the number of values being removed.

    Declaration

    Swift

    public func remove<S>(_ vals: S) where T == S.Element, S : Sequence

    Parameters

    vals

    The values to insert

  • Remove all occurrences of the given value from the tree. Time complexity: O(logN)

    Declaration

    Swift

    public func removeAll(_ val: T)

    Parameters

    val

    The value to remove all occurrences of

  • Remove all values from the tree. Time complexity: O(1)

    Declaration

    Swift

    public func clear()

Value-Specific Queries

  • Return the index (BSTreeIndex) of the value, or nil if the tree doesn’t have the value. Time complexity: O(logN)

    Declaration

    Swift

    public func index(_ val: T) -> Index?

    Parameters

    val

    The value to look for

    Return Value

    index, or nil if not found

  • Return true if the tree contains the given value, false otherwise. Time complexity: O(logN)

    Declaration

    Swift

    public func contains(_ value: T) -> Bool

    Parameters

    value

    The value to look for

    Return Value

    true or false

  • Returns the count of the value in the tree. Zero if the tree doesn’t contain the value. Time complexity: O(logN)

    Declaration

    Swift

    public func count(_ val: T) -> Int

    Parameters

    value

    The value get the count of

    Return Value

    Integer count

  • Returns the index of the least value >= the given value, according to the ordering given by the comparator, or by the ‘<’ operator. Returns nil if there is no ceiling. Time complexity: O(logN)

    Declaration

    Swift

    public func ceilingIndex(_ val: T) -> Index?

    Parameters

    val

    The value to find the ceiling of

    Return Value

    The index (nil if there is no ceiling value)

  • Returns the least value >= the given value, according to the ordering given by the comparator, or by the ‘<’ operator. Returns nil if there is no ceiling. Time complexity: O(logN)

    Declaration

    Swift

    public func ceilingValue(_ val: T) -> T?

    Parameters

    val

    The value to find the ceiling of

    Return Value

    The ceiling value (nil if none)

  • Returns the index of the greatest value <= the given value, according to the ordering given by the comparator, or by the ‘<’ operator. Returns nil if there is no floor. Time complexity: O(logN)

    Declaration

    Swift

    public func floorIndex(_ val: T) -> Index?

    Parameters

    val

    The value to find the floor of

    Return Value

    The index (nil if there is no floor value)

  • Returns the greatest value <= the given value, according to the ordering given by the comparator, or by the ‘<’ operator. Returns nil if there is no floor. Time complexity: O(logN)

    Declaration

    Swift

    public func floorValue(_ val: T) -> T?

    Parameters

    val

    The value to find the floor of

    Return Value

    The floor value (nil if none)

  • Returns the index of the least value > the given value, according to the ordering given by the comparator, or by the ‘<’ operator. Returns nil if there is no higher value. Time complexity: O(logN)

    Declaration

    Swift

    public func higherIndex(_ val: T) -> Index?

    Parameters

    val

    The value to find the higher value of

    Return Value

    The index (nil if there is no higher value)

  • Returns the least value > the given value, according to the ordering given by the comparator, or by the ‘<’ operator. Returns nil if there is no higher value. Time complexity: O(logN)

    Declaration

    Swift

    public func higherValue(_ val: T) -> T?

    Parameters

    val

    The value to find the higher value of

    Return Value

    The higher value (nil if none)

  • Returns the index of the greatest value < the given value, according to the ordering given by the comparator, or by the ‘<’ operator. Returns nil if there is no lower value. Time complexity: O(logN)

    Declaration

    Swift

    public func lowerIndex(_ val: T) -> Index?

    Parameters

    val

    The value to find the lower value of

    Return Value

    The index (nil if there is no lower value)

  • Returns the greatest value < the given value, according to the ordering given by the comparator, or by the ‘<’ operator. Returns nil if there is no lower value. Time complexity: O(logN)

    Declaration

    Swift

    public func lowerValue(_ val: T) -> T?

    Parameters

    val

    The value to find the lower value of

    Return Value

    The lower value (nil if none)

General Queries

  • The number of elements (unique values) in the tree (NOT the sum of all value counts, which is totalCount). This is also the number of nodes. Time complexity: O(1)

    Declaration

    Swift

    public var count: Int { get }

  • The sum of all value counts. Time complexity: O(1)

    Declaration

    Swift

    public var totalCount: Int { get }

  • The height of the tree, i.e. the number of levels minus 1. An empty tree has height -1, a tree with just a root node has height 0, and a tree with two nodes has height 1. Time complexity: O(1)

    Declaration

    Swift

    public var height: Int { get }

  • Index of the first value in the tree, according to the ordering given by the comparator, or nil if the tree is empty. If no comparator is supplied, the ‘<’ operator is used, and the first value is the minimum. Note that this differs from startIndex in that it will be nil if the tree is empty whereas startIndex will not. Time complexity: O(1)

    Declaration

    Swift

    public var firstIndex: Index? { get }

  • The first value in the tree, according to the ordering given by the comparator, or nil if the tree is empty. If no comparator is supplied, the ‘<’ operator is used, and the first value is the minimum. Time complexity: O(1)

    Declaration

    Swift

    public var firstValue: T? { get }

  • Index of the last value in the tree, according to the ordering given by the comparator, or nil if the tree is empty. If no comparator is supplied, the ‘<’ operator is used, and the last value is the maximum. Note that this differs from endIndex in that endIndex is one past lastIndex, and is never nil. Time complexity: O(1)

    Declaration

    Swift

    public var lastIndex: Index? { get }

  • The last value in the tree, according to the ordering given by the comparator, or nil if the tree is empty. If no comparator is supplied, the ‘<’ operator is used, and the last value is the maximum. Time complexity: O(1)

    Declaration

    Swift

    public var lastValue: T? { get }

  • Returns the indices of zero, one, or two median values. There will be zero indices if and only if the tree is empty. There will be two indices if the tree’s totalCount is a multiple of 2 and the values at positions n/2 and n/2 + 1 (starting with 1) differ. Otherwise one index. Time complexity: O(1)

    Declaration

    Swift

    public var medianIndices: [Index] { get }

  • Returns zero, one, or two median values. There will be zero values if and only if the tree is empty. There will be two values if the tree’s totalCount is a multiple of 2 and the values at positions n/2 and n/2 + 1 (starting with 1) differ. Otherwise one value. Time complexity: O(1)

    Declaration

    Swift

    public var medianValues: [T] { get }

Traversal

  • Return the elements of the tree in sorted order from first to last, according to the ordering given by the comparator, or by the ‘<’ operator, which orders from min to max. Time complexity: O(N)

    Declaration

    Swift

    public func traverseInOrder() -> [Element]

    Return Value

    An array of elements

  • Return the elements of the tree in “pre” order, meaning that the root is the first element returned.

    Declaration

    Swift

    public func traversePreOrder() -> [Element]

    Return Value

    An array of elements

  • Return the elements of the tree in “post” order, meaning that the root is the last element returned.

    Declaration

    Swift

    public func traversePostOrder() -> [Element]

    Return Value

    An array of elements

  • Return the elements of the tree in “level” order, starting with the root and working downward.

    Declaration

    Swift

    public func traverseByLevel() -> [Element]

    Return Value

    An array of elements

Converting

  • Returns an NSCountedSet with the same values and counts as the tree.

    Declaration

    Swift

    public func toCountedSet() -> NSCountedSet

    Return Value

    NSCountedSet

  • Returns an array of the values in the tree, in order, and with duplicates, if there are any values with a count greater than one. The size of the array is equal to totalCount.

    Declaration

    Swift

    public func toValueArray() -> [T]

    Return Value

    Sorted array of values

Comparing

  • Returns true if the two trees have the same values and value counts. They don’t necessarily need to have the same internal node structure.

    Declaration

    Swift

    public static func == (lhs: BSTree<T>, rhs: BSTree<T>) -> Bool

Tree Depictions

  • An ASCII-graphics depiction of the tree.

    Example:

          __42_
     /     \
   13       70(2)
  /  \
 9    17

    Declaration

    Swift

    public var description: String { get }

  • An ASCII-graphics depiction of the tree, with the height of each node given.

    Declaration

    Swift

    public var descriptionWithHeight: String { get }

  • Description with each node’s “next” and “prev” pointers shown.

    Declaration

    Swift

    public var descriptionWithNext: String { get }

  • Description with each node’s node count (the number of nodes in the subtree having that node as root) shown.

    Declaration

    Swift

    public var descriptionWithNodeCount: String { get }

  • Description with each node’s total count (the sum of all valueCount’s in the subtree having that node as root) shown.

    Declaration

    Swift

    public var descriptionWithTotalCount: String { get }

BidirectionalCollection

  • Declaration

    Swift

    public var startIndex: Index { get }

  • Declaration

    Swift

    public var endIndex: Index { get }

  • Declaration

    Swift

    public subscript(i: Index) -> Element { get }

  • Declaration

    Swift

    public func index(after i: Index) -> Index

  • Declaration

    Swift

    public func index(before i: Index) -> Index

Available where T: Comparable

  • Initialize the tree with a default comparator of the type’s ‘<’ operator.

    Declaration

    Swift

    public convenience init()

  • Initialize with an NSCountedSet.

    Declaration

    Swift

    public convenience init(countedSet: NSCountedSet)

    Parameters

    countedSet

    NSCountedSet

  • Initialize with an unsorted sequence of values, which can contain duplicates.

    Declaration

    Swift

    public convenience init<S>(_ vals: S) where T == S.Element, S : Sequence

    Parameters

    values

    Array

  • Initialize with a comma-separated list of values, which can contain duplicates.

    Declaration

    Swift

    public convenience init(_ values: T...)

    Parameters

    values

    Array

Available where T: AdditiveArithmetic

  • sum

    The sum of each value times its count. Time complexity: O(1)

    Declaration

    Swift

    public var sum: T { get set }