PasteRack.org
Paste # 73832
2025-10-28 04:55:19

Fork as a new paste.

Paste viewed 302 times.


Embed:

average depth of a node in a binary tree

  1. #lang typed/racket
  2.  
  3. ;; this code is licensed under the CRAPL: https://matt.might.net/articles/crapl/
  4.  
  5. ;; a binary tree:
  6. (define-type bt (U Node #f))
  7. (struct Node ([v : Integer] [l : bt] [r : bt])
  8.   #:transparent)
  9.  
  10. ;; an insert function.
  11. ;; (I tested it by shuffling the numbers from 1 to 100, inserting
  12. ;; them, and then looking at it for plausibility. Yikes.)
  13. (define (insert [t : bt] [v : Integer]) : bt
  14.   (match t
  15.     [#f (Node v #f #f)]
  16.     [(Node v1 l1 r1)
  17.      (cond [(= v1 v) (error 'insert "expected unique values")]
  18.            [(< v1 v) (Node v1 l1 (insert r1 v))]
  19.            [else (Node v1 (insert l1 v) r1)])]))
  20.  
  21. ;; the sum of all of the depths in the tree; cur-depth is an
  22. ;; accumulator that keeps track of the current depth
  23. (define (total-depth [t : bt] [cur-depth : Natural]) : Natural
  24.   (match t
  25.     [#f 0]
  26.     [(Node _ l r) (+ cur-depth
  27.                      (total-depth l (add1 cur-depth))
  28.                      (total-depth r (add1 cur-depth)))]))
  29.  
  30. (require typed/rackunit)
  31. (check-equal? (total-depth
  32.                (Node 4 (Node 2 #f (Node 3 #f #f))
  33.                      (Node 100
  34.                            #f
  35.                            #f))
  36.                0)
  37.               (+ 0 1 2 1))
  38.  
  39. ;; the number of nodes in the tree:
  40. (define (size [t : bt]) : Natural
  41.   (match t
  42.     [#f 0]
  43.     [(Node _ l r)
  44.      (+ 1 (size l) (size r))]))
  45.  
  46. ;; the average depth of the nodes in the tree
  47. (define (average-depth [t : bt])
  48.   (/ (total-depth t 0) (size t)))
  49.  
  50. (check-equal? (average-depth
  51.                (Node 4 (Node 2 #f (Node 3 #f #f))
  52.                      (Node 100
  53.                            (Node 75 #f #f)
  54.                            #f)))
  55.               (/ 6 5))
  56.  
  57. ;; shuffle the numbers from 1 to 1000, insert them into an empty tree,
  58. ;; compute the average depth of the nodes in the tree
  59. (define (run-test)
  60.   (average-depth
  61.    (foldl (λ ([v : Integer] [t : bt]) (insert t v)) #f (shuffle (range 1000)))))
  62.  
  63. ;; draw a picture:
  64. (require plot
  65.          math/statistics)
  66.  
  67. (define trials 1000)
  68.  
  69. ;; run a number of trials, build a list:
  70. (define data (for/list : (Listof Real) ([i trials])
  71.    (run-test)))
  72.  
  73. ;; show the mean:
  74. (exact->inexact (mean data))
  75.  
  76. ;; show the density plot
  77. (plot (density data))

=>