Treap in OCaml

treap.ml

(*
 * Copyright (C) 2017 Shinya Yamaoka
 * Licensed under the MIT License.; you may not use this file except in
 * compliance with the license. You may obtain a copy of the License at
 * https://opensource.org/licenses/mit-license.php
 *)
module Treap = struct
    type 'a t = Empty | NonEmpty of 'a node
    and 'a node = {
        size: int;
        priority: int;
        value: 'a;
        left: 'a t;
        right: 'a t
    }

    let empty = Empty

    let create value priority =
        let size = 1 in
        let left = Empty in
        let right = Empty in
        NonEmpty { size; priority; value; left; right; }

    let size_of = function
        | Empty -> 0
        | NonEmpty node -> node.size

    let priority_of = function
        | Empty -> -1
        | NonEmpty node -> node.priority

    let left_of = function
        | Empty -> Empty
        | NonEmpty node -> node.left

    let right_of = function
        | Empty -> Empty
        | NonEmpty node -> node.right

    let is_empty = function
        | Empty -> true
        | _ -> false

    let update_right tree right = match tree with
        | Empty -> Empty
        | NonEmpty node -> NonEmpty { node with right = right }

    let update_left tree left = match tree with
        | Empty -> Empty
        | NonEmpty node -> NonEmpty { node with left = left }

    let update = function
        | Empty -> Empty
        | NonEmpty node ->
                let left_size = size_of node.left in
                let right_size = size_of node.right in
                NonEmpty { node with size = 1 + left_size + right_size }

    let rec merge l r =
        if (is_empty l) || (is_empty r)
        then (if (is_empty l) then r else l)
        else
            begin
                if (priority_of l) > (priority_of r)
                then let t = merge (right_of l) r in update (update_right l t)
                else let t = merge l (left_of r) in update (update_left r t)
            end

    let rec split t k =
        if (is_empty t) then (Empty, Empty)
        else
            begin
                if (k <= (size_of (left_of t)))
                then
                    let (first, second) = split (left_of t) k
                    in (first, update (update_left t second))
                else
                    let j = k - (size_of (left_of t)) - 1 in
                    let (first, second) = split (right_of t) j in
                    (update (update_right t first), second)
            end

    let insert tree k v priority =
        let (first, second) = split tree k in
        let t1 = merge first (create v priority) in
        let t2 = merge t1 second in
        update t2

    let delete tree k =
        let (f1, s1) = split tree (k + 1) in
        let (f2, s2) = split f1 k in
        let t = merge f2 s1 in
        update t

    let rec pretty tree of_value =
        let rec p t depth = match t with
        | Empty -> "Empty"
        | NonEmpty node ->
                let indent = 4 in
                let padding = String.make (depth * indent) ' ' in
                let shallow_padding = String.make ((depth - 1) * indent) ' ' in
                let new_depth = depth + 1 in
                String.concat "\n" [
                    "(NonEmpty";
                    padding ^ "size=" ^ string_of_int node.size;
                    padding ^ "priority=" ^ string_of_int node.priority;
                    padding ^ "value=" ^ of_value node.value;
                    padding ^ "left=" ^ p node.left new_depth;
                    padding ^ "right=" ^ p node.right new_depth;
                    shallow_padding ^ ")";
                ]
    in p tree 1
end;;

let tree1 = Treap.empty in
let tree2 = Treap.insert tree1 1 "1" 9 in
let tree3 = Treap.insert tree2 2 "2" 20 in
let tree4 = Treap.insert tree3 3 "3" 5 in
let tree5 = Treap.insert tree4 4 "4" 4 in
let tree6 = Treap.insert tree5 5 "5" 3 in
begin
    print_string (Treap.pretty (Treap.delete tree6 3) (fun x -> x));
end

How is this code licensed? Could you please add license header?

Sorry for my late comment. This code is distributed under MIT license.