Random Braun trees

braunc.rkt

#lang racket

(struct node (x l r) #:transparent)
(define/match (size t)
  [(#f) 0]
  [((node x l r)) (+ 1 (size l) (size r))])

(define braun/c 
  (flat-rec-contract braun/c
                     (or/c #f
                           (struct/dc node
                                      [x any/c]
                                      [l braun/c]
                                      [r braun/c]
                                      #:inv (l r)
                                      (let ([sl (size l)]
                                            [sr (size r)])
                                      (or (= sl sr)
                                          (= sl (add1 sr))))))))
(define tree/c
  (flat-rec-contract 
   tree/c
   (or/c #f
         (struct/c node any/c tree/c tree/c))))

(define d
  (time (for*/list ([_ 100000]
                    [v (in-value (contract-random-generate tree/c))]
                    #:when (braun/c v)) 
          (size v))))

(length d)
(require plot)
(define h
  (for/fold ([h (hash)]) ([i d])
    (hash-update h i add1 0)))
(parameterize ([plot-y-transform cbrt-transform])
  (plot (discrete-histogram (for/list ([(k v) h]) (vector k v)))))
(apply set d)