:PROPERTIES: :ID: cf46bfd2-970d-42fb-9b3b-a0aad0b769fd :mtime: 20231020021143 :ctime: 20231020021142 :END: #+title: binary search tree #+filetags: :public:project: * Definition A binary search tree is a [[id:41b7ac3b-6084-4727-bd44-7bb093dab19a][Datatype]] which implements a map using a tree. The trick is that we impose a structure on the tree. All the keys on the left sub-tree must be less than the value of the node, and all the keys on the right sub-tree must be greater than the value of the node. Note that this means there must exist an instance of a total ordering on the keys. If the binary search tree is balanced, then lookup has time complexity $O(\log n)$ * Examples of Binary Search Trees ** Binary Search Trees in [[id:8952459c-5076-4e68-8a68-5f658209f39e][Ocaml]] #+BEGIN_SRC ocaml #+END_SRC #+BEGIN_SRC ocaml type 'a tree = | Branch of 'a * 'a tree * 'a tree | Leaf #+END_SRC #+RESULTS: : type 'a tree = Branch of 'a * 'a tree * 'a tree | Leaf #+BEGIN_SRC ocaml exception MissingKey of string #+END_SRC #+RESULTS: : exception MissingKey of string #+BEGIN_SRC ocaml let rec lookup key = function | Leaf -> raise (MissingKey key) | Branch ((key', value) , t1 ,t2) -> if key = key' then value else lookup key (if key < key' then t1 else t2) #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml let rec update key value = function | Leaf -> Branch ((key, value), Leaf, Leaf) | Branch ((key', value') , t1 ,t2) -> Branch ((key', if key = key' then value else value'), (if key < key' then update key value else Fun.id) t1 ,(if key > key' then update key value else Fun.id) t2) #+END_SRC #+RESULTS: : <fun> * Time complexity of BST If the binary search tree is balanced, then lookup has time complexity $O(\log n)$. If the binary search tree is unbalanced, then lookup has time complexity $O(n)$.