Tree

A red-black binary search tree. Adapted from Airspeed Velocity’s implementation, Chris Okasaki’s Purely Functional Data Structures, and Stefan Kahrs’ Red-black trees with types, which is implemented in the Haskell standard library.

Elements must be comparable with Strict total order.

Full documentation is available here.

  • Create an empty Tree.

    Declaration

    Swift

    public init() { self = .Empty }

  • Create a Tree from a sequence

    Declaration

    Swift

    public init<S : SequenceType where S.Generator.Element == Element>(_ seq: S)

  • Create a Tree of elements

    Declaration

    Swift

    public init(arrayLiteral elements: Element...)

  • A description of self, suitable for debugging

    Declaration

    Swift

    public var debugDescription: String

  • Returns the smallest element in self if it’s present, or nil if self is empty

    • Complexity: O(log n)

    Declaration

    Swift

    public var first: Element?

  • Returns the largest element in self if it’s present, or nil if self is empty

    • Complexity: O(log n)

    Declaration

    Swift

    public var last: Element?

  • Returns true iff self is empty

    Declaration

    Swift

    public var isEmpty: Bool

  • Returns the number of elements in self

    • Complexity: O(count)

    Declaration

    Swift

    public var count: Int

  • Returns true iff self contains x

    • Complexity: O(log n)

    Declaration

    Swift

    public func contains(x: Element) -> Bool

  • Inserts x into self

    • Complexity: O(log n)

    Declaration

    Swift

    public mutating func insert(x: Element)

  • Runs a TreeGenerator over the elements of self. (The elements are presented in order, from smallest to largest)

    Declaration

    Swift

    public func generate() -> TreeGenerator<Element>

  • Returns the smallest element in self if it’s present, or nil if self is empty

    • Complexity: O(log n)

    Declaration

    Swift

    public func minElement() ->  Element?

  • Returns the largest element in self if it’s present, or nil if self is empty

    • Complexity: O(log n)

    Declaration

    Swift

    public func maxElement() -> Element?

  • Removes the smallest element from self and returns it if it exists, or returns nil if self is empty.

    • Complexity: O(log n)

    Declaration

    Swift

    public mutating func popFirst() -> Element?

  • Removes the smallest element from self and returns it.

    • Complexity: O(log n)
    • Precondition: !self.isEmpty

    Declaration

    Swift

    public mutating func removeFirst() -> Element?

  • Removes the largest element from self and returns it if it exists, or returns nil if self is empty.

    • Complexity: O(log n)

    Declaration

    Swift

    public mutating func popLast() -> Element?

  • Removes the largest element from self and returns it.

    • Complexity: O(log n)
    • Precondition: !self.isEmpty

    Declaration

    Swift

    public mutating func removeLast() -> Element

  • Removes x from self and returns it if it is present, or nil if it is not.

    • Complexity: O(log n)

    Declaration

    Swift

    public mutating func remove(x: Element) -> Element?

  • Returns a sequence of the elements of self from largest to smallest

    Declaration

    Swift

    public func reverse() -> ReverseTreeGenerator<Element>

  • Remove the member if it was present, insert it if it was not.

    Declaration

    Swift

    public mutating func XOR(x: Element)