2分木

SML 30分プログラム

30分プログラム、その689。ML系の言語といえばバリアント、バリアントと言えば木構造なので、2分木を作ってみました。
そのうち、B木とかに拡張できたらいいね。

使い方

- val t = List.foldl (curry insert) empty [10,3,1,4];
val t = Branch (10,Branch (3,Branch #,Branch #),Leaf) : int tree
- size t;
val it = 4 : int
- mem 10 t;
val it = true : bool
-
val it = true : bool
- mem 0 t;
val it = false : bool

ソースコード

datatype 'a tree = Leaf | Branch of 'a * 'a tree * 'a tree;

val empty = Leaf;

fun insert x Leaf = Branch (x,Leaf,Leaf)
  | insert x (tree as (Branch (y,left,right))) = if x < y then
						     Branch (y, insert x left, right)
						 else if x > y then
						     Branch (y, left, insert x right)
						 else (* x = y *)
						     tree;

fun size Leaf = 0
  | size (Branch (_,left,right)) = 1 + size left + size right;

fun mem x Leaf = false
  | mem x (Branch (y , left, right)) = x = y orelse mem x left orelse mem x right;

(* example *)
fun curry f (a,b) = f a b;

val t = List.foldl (curry insert) empty [10,3,1,4];

参考