Created
September 6, 2024 18:08
-
-
Save DanielAugusto191/bcd3951c395c22ef2f55111eb656826c to your computer and use it in GitHub Desktop.
binary search tree
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| (* open Fmt *) | |
| type 'a bst = | |
| | Empty | |
| | Node of { | |
| left : 'a bst; | |
| value : 'a; | |
| right: 'a bst; | |
| } | |
| [@@deriving show] | |
| let rec insert x tree = | |
| match tree with | |
| | Empty -> Node {value = x; left = Empty; right = Empty} | |
| | Node {value; left; right} -> | |
| if x < value then | |
| Node {value; left = insert x left; right} | |
| else | |
| Node {value; left; right = insert x right} | |
| let rec search x tree = | |
| match tree with | |
| | Empty -> false | |
| | Node {value; left; right} -> | |
| if value = x then | |
| true | |
| else | |
| let a = search x left in | |
| let b = search x right in | |
| a || b | |
| let rec delete x = function | |
| | Empty -> Empty | |
| | Node {value; left; right} when x > value -> | |
| Node {value = value; left = delete x left; right} | |
| | Node {value; left; right} when x < value -> | |
| Node {value = value; left = left; right = delete x right} | |
| | Node {value=_; left; right} -> | |
| match (left, right) with | |
| | Empty, Empty -> Empty | |
| | Empty, _ -> right | |
| | _, Empty -> left | |
| | _ -> | |
| let | |
| rec getMin tree = | |
| match tree with | |
| | Node {value;left = Empty;_} -> value | |
| | Node {left; _} -> getMin left | |
| | Empty -> failwith "not ok" | |
| in | |
| let min = getMin right in | |
| Node {value = min; left; right = delete min right} | |
| let rec preOrder tree = | |
| match tree with | |
| | Empty -> [] | |
| | Node {value; left; right} -> [value] @ preOrder left @ preOrder right | |
| let rec inOrder tree = | |
| match tree with | |
| | Empty -> [] | |
| | Node {value; left; right} -> inOrder left @ [value] @ inOrder right | |
| let rec postOrder tree = | |
| match tree with | |
| | Empty -> [] | |
| | Node {value; left; right} -> postOrder left @ postOrder right @ [value] | |
| let _a = Empty;; | |
| let b = Node {value = 50; left = Empty; right = Empty};; | |
| let c = insert 100 b;; | |
| let d = insert 25 c;; | |
| let d = insert 5 d;; | |
| let d = insert 30 d;; | |
| let d = insert 27 d;; | |
| let d = delete 25 d;; | |
| let _ = search 23 d;; | |
| let pre = preOrder d;; | |
| let inO = inOrder d;; | |
| let pos = postOrder d;; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment