3 people like it.

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:10 years ago
Author:devshorts
Tags: b-tree , tree