NB. some abstruse tree problem
NB. ischtche%uwaterloo.ca
NB. mainly an exercise in how to represent trees that carry values at each node
NB. tree building
NB. '' (empty list) for empty trees
leaf =: (;,~)&a: NB. leaf value => value;'';''
br =: (&;)(@,)(&<) NB. L val br R => val ; L ,&< R
NB. see http://pastebin.com/raw.php?i=5J8TQgar for diagram
R =: (leaf 'T') 'R'br '' 'U'br '' 'V'br ((leaf 'Z') 'X'br '') 'W'br leaf 'Y'
H =: (leaf 'L') 'H'br ((leaf 'P') 'N'br '') 'M'br '' 'O'br R 'Q'br leaf 'S'
A =: ((leaf 'D') 'B'br H 'E'br leaf 'I') 'A'br (leaf 'F') 'C'br '' 'G'br leaf 'J'
NB. tree traversal
trav =: {::~ ;/ NB. traverse down to node, end with 0 to get value at node
vl =: 0&{:: NB. value
lt =: 1&{:: NB. left tree
rt =: 2&{:: NB. right tree
'I' -: A trav 1 2 2
NB. modification
NB. y: tree, x: replacement, m: path if newdp
newv =: ; }. NB. new val
newl =: {.@] , [ ; {:@] NB. new left
newr =: }:@] , <@[ NB. new right
newdp =: 1 : 0 NB. new deep
NB. 1 goes left branch, 2 goes right branch, 0 goes value
if. 1 < #m do.
((}.m)newdp [:`lt`rt@.({.m)) newv`newl`newr@.({.m) ]
else.
newv`newl`newr@.({.m)
end.
)
(('' 'T'br 5) 'R'br rt R) -: 5 (1 2)newdp R
NB. everything below is a work in progress!
NB. search
tsearch =: 4 : 0 NB. doesn't work
s =. y i.