Iterate B-Tree

Iterate simple b-tree

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38:

type Key = int

type BTree = 
    | Node of Key list * BTree * BTree * BTree 
    | Empty

let rec findKey (targetKey:Key) (bTree:BTree) = 
    match bTree with
        | Node (keyList, lessTree, betweenTree, greaterTree) ->
            let minKey = List.min keyList
            let maxKey = List.max keyList
            
            let extractor item = item = targetKey;

            if targetKey < minKey then
                findKey targetKey lessTree

            else if targetKey > maxKey then
                findKey targetKey greaterTree

            else if (List.exists extractor keyList) then
                let foundElement = List.find extractor keyList
                Some(foundElement)
            
            else 
                findKey targetKey betweenTree

        | Empty -> None

let lessTree = Node(([-12; -3; 0], Empty, Empty, Empty))

let greaterTree = Node(([100; 200; 300], Empty, Empty, Empty))

let middleTree = Node(([3], Empty, Empty, Empty))

let tree = Node(([1; 2; 4], lessTree, middleTree, greaterTree))

let key = findKey 3 tree

Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

type BTree =
| Node of Key list * BTree * BTree * BTree
| Empty

Full name: Script.BTree

union case BTree.Node: Key list * BTree * BTree * BTree -> BTree

type Key = int

Full name: Script.Key

type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>

union case BTree.Empty: BTree

val findKey : targetKey:Key -> bTree:BTree -> Key option

Full name: Script.findKey

val targetKey : Key

val bTree : BTree

val keyList : Key list

val lessTree : BTree

val betweenTree : BTree

val greaterTree : BTree

val minKey : Key

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

val min : list:'T list -> 'T (requires comparison)

Full name: Microsoft.FSharp.Collections.List.min

val maxKey : Key

val max : list:'T list -> 'T (requires comparison)

Full name: Microsoft.FSharp.Collections.List.max

val extractor : (Key -> bool)

val item : Key

val exists : predicate:('T -> bool) -> list:'T list -> bool

Full name: Microsoft.FSharp.Collections.List.exists

val foundElement : Key

val find : predicate:('T -> bool) -> list:'T list -> 'T

Full name: Microsoft.FSharp.Collections.List.find

union case Option.Some: Value: 'T -> Option<'T>

union case Option.None: Option<'T>

val lessTree : BTree

Full name: Script.lessTree

val greaterTree : BTree

Full name: Script.greaterTree

val middleTree : BTree

Full name: Script.middleTree

val tree : BTree

Full name: Script.tree

val key : Key option

Full name: Script.key

Raw view Test code New version

More information

Link:	http://fssnip.net/if
Posted:	11 years ago
Author:	devshorts
Tags:	b-tree , tree