     private var sentinel = Node(sentinel: ())
     private var root: Node
     private unowned var firstNode, lastNode: Node
-    private var uuid: _TreeUUID
 
     public private(set) var count = 0
 
     /// Copy-on-write optimisation. Return `true` if the tree was copied.
     /// - Complexity: Expected O(1), O(`count`) if the structure was copied and modified.
-    private mutating func ensureUnique() -> Bool {
+    private mutating func ensureUnique() {
         if _slowPath(root != sentinel && !isUniquelyReferenced(&root)) {
             sentinel = Node(sentinel: ())
             root = _RedBlackTreeNode(deepCopy: root, sentinel: sentinel)
             firstNode = root.subtreeMin()
             lastNode = root.subtreeMax()
-            return true
         }
         assert(root == sentinel || isUniquelyReferenced(&root))
-        return false
     }
 
     public init() {
         root = sentinel
         firstNode = sentinel
         lastNode = sentinel
-        uuid = _nextTreeID()
     }
 
     // TODO: initialiser that takes a sorted sequence and constructs a tree in O(n) time

    case Empty
}

private typealias _TreeUUID = UInt64
private func _nextTreeID() -> _TreeUUID {
    struct W {
        static var counter: _TreeUUID = 0
    }
    return W.counter++
}

public struct _RedBlackTreeIndex<Key> : BidirectionalIndexType {

    private typealias Node = _RedBlackTreeNode<Key>
    private typealias Kind = _RedBlackTreeIndexKind<Key>

    private let kind: Kind
    private let treeID: _TreeUUID

    private init(node u: Unowned<Node>, treeID: _TreeUUID) {
        kind = .Node(u)
        self.treeID = treeID
    }
    private init(node: Node, treeID: _TreeUUID) { self.init(node: Unowned(node), treeID: treeID) }

    private init(end u: Unowned<Node>, treeID: _TreeUUID) {
        assert(u.value.successor() == nil, "Cannot make end index for a node that is not the end.")
        kind = .End(last: u)
        self.treeID = treeID
    }
    private init(end last: Node, treeID: _TreeUUID) { self.init(end: Unowned(last), treeID: treeID) }

    private init(empty: (), treeID: _TreeUUID) {
        kind = .Empty
        self.treeID = treeID
    }

    /// - Complexity: Amortised O(1)
    public func successor() -> _RedBlackTreeIndex {
        switch kind {
        case .Node(let u):
            guard let suc = u.value.successor() else { return _RedBlackTreeIndex(end: u, treeID: treeID) }
            return _RedBlackTreeIndex(node: suc, treeID: treeID)
        case .End(_): fallthrough
        case .Empty:
            preconditionFailure("Cannot get successor of the end index.")

        }
        assert(k < nl.key)
        assert(nl.predecessor() == nil || nl.predecessor()!.key <= k)
        return Index(node: nl)
    }

}
