Бінарне дерево пошуку на OCaml

Матеріал з Wikisource

Реалізація алгоритмів роботи з бінарними деревами пошуку на OCaml.

[ред.] Текст програми

[ред.] Тип даних

Тип даних для вузлів бінарного дерева пошуку.

  type ’a bin_tree =
      Empty
    | Node of ’a bin_tree * ’a * ’a bin_tree ;;

[ред.] Функції роботи з бінарними деревами пошуку

[ред.] Перетворення дерева на впорядкований список

  let rec list_of_tree = function
     Empty ! []
   | Node(lb, r, rb) -> (list_of_tree lb) @ (r :: (list_of_tree rb)) ;;
Сигнатура:
  val list_of_tree : 'a bin_tree -> 'a list = <fun>

[ред.] Вставка нового елемента в дерево

  let rec insert x = function
     Empty -> Node(Empty, x, Empty)
   | Node(lb, r, rb) -> if x < r then Node(insert x lb, r, rb)
                                 else Node(lb, r, insert x rb) ;;

Сигнатура:

  val insert : 'a -> 'a bin_tree -> 'a bin_tree = <fun>

[ред.] Перетворення списка на бінарне дерево пошуку

  let rec tree_of_list = function
     [] -> Empty
   | h :: t -> insert h (tree of list t) ;;

Сигнатура:

  val tree_of_list : 'a list -> 'a bin_tree = <fun>

[ред.] Підтвердження

Приклад сортування із допомогою описаних функцій:

 # let sort x = list_of_tree (tree_of_list x) ;;
 val sort : 'a list -> 'a list = <fun>
 # sort [5; 8; 2; 7; 1; 0; 3; 6; 9; 4] ;;
 - : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]

[ред.] Джерела інформації

• Emmanuel Chailloux, Pascal Manoury, Bruno Pagano: Developing Applications With Objective Caml, O'Reilly, 2000.