Binary tree with Splay

Learning
1

Hi,

I have this code that successfully creates a binary tree. But when I include the line let splayedtree = splay_f k t in I see just one element in the tree. So I am assuming that function should be debugged But I also see other messages (some are commented now ) showing that all elements are added.

This functions works perfectly when I used it without that line. Are there obvious defects here ? The data structure isn’t quite perfect now but this particular function inserts properly without that line.

The idea is to splay the tree after addition of every element and continue inserting.

let rec insert_key (k : int ) (t : int splay_tree option ref) : int splay_tree option ref=
 match !t with
  | None |Some Leaf ->
    (* let () = Printf.printf "(insert_key)Inserting new node %d\n" k  in *)

    let new_node = Node { key = k; value = 0; left = None; right = None } in
    t := Some new_node;
    t
  (* | Some tree  -> *)
    
  | Some _tree  ->
     
      let splayedtree = splay_f k t in
      (* let _ = print_splaytree (tree_from_node splayedtree) 1 in *)

      let  insert_node splayedtree =

      match splayedtree with
      |  Node old_key ->
        begin match old_key with
          |  ok  ->
            if k > ok.key then(
              match ok.right with
              | None | Some Leaf ->
                let () = Printf.printf "(insert_key)Inserting %d\n" k  in

              let r = ref (Some (Node { key = k ;value = 0 ; right = Some Leaf; left = Some Leaf} ))in
               ok.right <- !r;
               let _ = print_splaytree t 1 in
               t
             | Some _r ->
               (* let () = Printf.printf "(insert_key)Inserting %d\n" k  in *)

             insert_key k (ref (ok.right ))
             )
            else 
            if k < ok.key then(
              match ok.left with
              | None | Some Leaf ->
                (* let () = Printf.printf "(insert_key)Inserting %d\n" k  in *)

               let l = ref (Some (Node { key = k ;value = 0 ; right = Some Leaf; left = Some Leaf} ))in 
              ok.left <- !l;
              t 
             | Some _l -> 
               (* let () = Printf.printf "(insert_key)Inserting %d\n" k  in *)

             insert_key k (ref (ok.left)); 
            )
          else
             t
        end;
     |Leaf -> t
      in
      let tree_ref = tree_from_node splayedtree in

      begin match !tree_ref with
      | None -> tree_ref
      | Some tr ->

      insert_node tr
      end;

This function is used because I started with this data structure.

let tree_from_node (node:int node1 option): int splay_tree option ref=
  match node with
  | None -> 
    (ref (Some (Node{ key = 0;value=0; left = None; right = None })))
  | Some n ->
    match n with
    | { key ; value;left; right } -> 
      let newNode = (ref (Some (Node {key;value;left;right}))) in
      newNode

type 'a splay_tree = Leaf | Node of 'a node1
and 'a node1 = { key : 'a;value : 'a; mutable left : 'a splay_tree option; mutable right : 'a splay_tree option; }
type 'a t = 'a splay_tree option ref

The pattern matching is verbose due to that but that works.
Is the problem caused by not using the root of the tree always to splay ? I see in the reference code that the root of the tree is used to splay always.