  Ordered sequences of data, specified with a join operation to combine
sequences, serve as a foundation for the implementation of parallel functional
algorithms. This abstract data type can be elegantly and efficiently
implemented using balanced binary trees, where a join operation is provided to
combine two trees and rebalance as necessary. In this work, we present a
verified implementation and cost analysis of joinable red-black trees in
$\textbf{calf}$, a dependent type theory for cost analysis. We implement
red-black trees and auxiliary intermediate data structures in such a way that
all correctness invariants are intrinsically maintained. Then, we describe and
verify precise cost bounds on the operations, making use of the red-black tree
invariants. Finally, we implement standard algorithms on sequences using the
simple join-based signature and bound their cost in the case that red-black
trees are used as the underlying implementation. All proofs are formally
mechanized using the embedding of $\textbf{calf}$ in the Agda theorem prover.
