⍝ Binary Search Trees:
put ← ∪ sbst ⍝ insert/update :: tree ← tree ∇ key val
get ← ⍎ sbst ⍝ retrieve val for key :: val tree ← key ∇ tree
rem ← ~ sbst ⍝ remove key from tree :: tree ← tree ∇ key
fmt ← ⍕ sbst ⍝ formatted tree :: char[;] ← ∇ tree
chk ← ? sbst ⍝ tree statistics :: ok height size ← ∇ tree
vec ← ∊ sbst ⍝ enlist of tree :: (key val)[] ← ∇ tree
bal ← = sbst ⍝ balance of tree ⍵ :: tree ← ∇ tree
tree←0∘(put foldl) ⍝ tree from vector of keys.
fmt tree ⍳15 ⍝ unbalanced tree.
1=1┐
└2=2┐
└3=3┐
└4=4┐
└5=5┐
└6=6┐
└7=7┐
└8=8┐
└9=9┐
└10=10┐
└11=11┐
└12=12┐
└13=13┐
└14=14┐
└15=15
⎕rl←7*5 ⍝ set random seed.
fmt tree 15?15 ⍝ random tree.
┌1=1
2=2┤
│ ┌3=3┐
│ │ └4=4
│ ┌5=5┘
│ ┌6=6┘
│ ┌7=7┘
│ ┌8=8┤
│ │ │ ┌9=9
│ │ └10=10┤
│ │ └11=11
└12=12┤
└13=13┐
│ ┌14=14
└15=15┘
fmt bal tree 15?15 ⍝ balanced random tree.
┌1=1
┌2=2┤
│ └3=3
┌4=4┤
│ │ ┌5=5
│ └6=6┤
│ └7=7
8=8┤
│ ┌9=9
│ ┌10=10┤
│ │ └11=11
└12=12┤
│ ┌13=13
└14=14┤
└15=15
pangram←'jackdaws love my big sphinx of quartz'~' '
fmt tree pangram
┌a=a┐
│ │ ┌b=b
│ └c=c┤
│ └d=d┐
│ └e=e┐
│ │ ┌f=f
│ │ ┌g=g┤
│ │ │ └h=h
│ └i=i┘
j=j┤
└k=k┐
│ ┌l=l┐
│ │ │ ┌m=m┐
│ │ │ │ └n=n
│ │ └o=o┤
│ │ └p=p┐
│ │ └q=q┐
│ │ └r=r
│ ┌s=s┤
│ │ │ ┌t=t
│ │ │ ┌u=u┘
│ │ └v=v┘
└w=w┤
│ ┌x=x
└y=y┤
└z=z
fmt bal tree pangram ⍝ balanced tree.
┌a=a
┌b=b┤
│ └c=c
┌d=d┤
│ │ ┌e=e┐
│ │ │ └f=f
│ └g=g┤
│ │ ┌h=h
│ └i=i┤
│ └j=j
k=k┤
│ ┌l=l
│ ┌m=m┤
│ │ └n=n
│ ┌o=o┤
│ │ │ ┌p=p
│ │ └q=q┤
│ │ └r=r
└s=s┤
│ ┌t=t
│ ┌u=u┤
│ │ └v=v
└w=w┤
│ ┌x=x
└y=y┤
└z=z
{fmt bal 0 put foldl ⍵}¨ 1↓¨,\' ',⎕a ⍝ test balancing
┌┬───┬───────┬───────┬───────────┬───────────┬───────────┬───────────┬───────────────┬───────────────┬───────────────┬───────────────┬───────────────┬───────────────┬───────────────┬───────────────┬───────────────────┬───────────────────┬───────────────────┬───────────────────┬───────────────────┬───────────────────┬───────────────────┬───────────────────┬───────────────────┬───────────────────┬───────────────────┐
││A=A│A=A┐ │ ┌A=A│ ┌A=A │ ┌A=A │ ┌A=A┐ │ ┌A=A│ ┌A=A │ ┌A=A │ ┌A=A │ ┌A=A │ ┌A=A │ ┌A=A │ ┌A=A┐ │ ┌A=A│ ┌A=A │ ┌A=A │ ┌A=A │ ┌A=A │ ┌A=A │ ┌A=A │ ┌A=A │ ┌A=A │ ┌A=A │ ┌A=A │ ┌A=A │
││ │ └B=B│B=B┤ │B=B┤ │B=B┤ │ │ └B=B│ ┌B=B┤ │ ┌B=B┤ │ ┌B=B┤ │ ┌B=B┤ │ ┌B=B┤ │ ┌B=B┤ │ ┌B=B┤ │ │ └B=B│ ┌B=B┤ │ ┌B=B┤ │ ┌B=B┤ │ ┌B=B┤ │ ┌B=B┤ │ ┌B=B┤ │ ┌B=B┤ │ ┌B=B┤ │ ┌B=B┤ │ ┌B=B┤ │ ┌B=B┤ │ ┌B=B┤ │
││ │ │ └C=C│ └C=C┐ │ │ ┌C=C│C=C┤ │ │ └C=C│ │ └C=C │ │ └C=C │ │ └C=C │ │ └C=C │ │ └C=C┐ │ │ │ ┌C=C│ ┌C=C┤ │ │ └C=C│ │ └C=C │ │ └C=C │ │ └C=C │ │ └C=C │ │ └C=C │ │ └C=C │ │ └C=C │ │ └C=C │ │ └C=C │ │ └C=C │ │ └C=C │
││ │ │ │ └D=D│ └D=D┤ │ │ ┌D=D│D=D┤ │D=D┤ │D=D┤ │D=D┤ │D=D┤ │ │ └D=D│ │ └D=D┤ │ │ │ ┌D=D│ ┌D=D┤ │ ┌D=D┤ │ ┌D=D┤ │ ┌D=D┤ │ ┌D=D┤ │ ┌D=D┤ │ ┌D=D┤ │ ┌D=D┤ │ ┌D=D┤ │ ┌D=D┤ │ ┌D=D┤ │ ┌D=D┤ │
││ │ │ │ │ └E=E│ └E=E┤ │ │ ┌E=E│ │ ┌E=E │ │ ┌E=E │ │ ┌E=E┐ │ │ ┌E=E│E=E┤ │ │ └E=E│ │ └E=E┤ │ │ │ ┌E=E│ │ │ ┌E=E │ │ │ ┌E=E │ │ │ ┌E=E │ │ │ ┌E=E │ │ │ ┌E=E │ │ │ ┌E=E │ │ │ ┌E=E │ │ │ ┌E=E │ │ │ ┌E=E │ │ │ ┌E=E │ │ │ ┌E=E┐ │
││ │ │ │ │ │ └F=F│ └F=F┤ │ └F=F┤ │ └F=F┤ │ │ │ └F=F│ │ ┌F=F┤ │ │ ┌F=F│F=F┤ │ │ └F=F│ │ └F=F┤ │ │ └F=F┤ │ │ └F=F┤ │ │ └F=F┤ │ │ └F=F┤ │ │ └F=F┤ │ │ └F=F┤ │ │ └F=F┤ │ │ └F=F┤ │ │ └F=F┤ │ │ └F=F┤ │ │ │ │ └F=F│
││ │ │ │ │ │ │ └G=G│ └G=G┐ │ │ ┌G=G│ └G=G┤ │ │ │ └G=G│ │ ┌G=G┤ │ │ ┌G=G│G=G┤ │ │ └G=G│ │ └G=G │ │ └G=G │ │ └G=G │ │ └G=G │ │ └G=G │ │ └G=G │ │ └G=G │ │ └G=G │ │ └G=G┐ │ │ │ ┌G=G│ │ └G=G┤ │
││ │ │ │ │ │ │ │ └H=H│ └H=H┤ │ │ ┌H=H│ └H=H┤ │ │ │ └H=H│ │ ┌H=H┤ │ │ ┌H=H│H=H┤ │H=H┤ │H=H┤ │H=H┤ │H=H┤ │H=H┤ │H=H┤ │H=H┤ │H=H┤ │ │ └H=H│ │ └H=H┤ │ │ │ ┌H=H│
││ │ │ │ │ │ │ │ │ └I=I│ └I=I┤ │ │ ┌I=I│ └I=I┤ │ │ │ └I=I│ │ ┌I=I┤ │ │ ┌I=I│ │ ┌I=I │ │ ┌I=I │ │ ┌I=I │ │ ┌I=I │ │ ┌I=I │ │ ┌I=I │ │ ┌I=I┐ │ │ ┌I=I│I=I┤ │ │ └I=I│ │ └I=I┤ │
││ │ │ │ │ │ │ │ │ │ └J=J│ └J=J┤ │ │ ┌J=J│ └J=J┤ │ │ │ └J=J│ │ ┌J=J┤ │ │ ┌J=J┤ │ │ ┌J=J┤ │ │ ┌J=J┤ │ │ ┌J=J┤ │ │ ┌J=J┤ │ │ ┌J=J┤ │ │ │ └J=J│ │ ┌J=J┤ │ │ ┌J=J│J=J┤ │ │ └J=J│
││ │ │ │ │ │ │ │ │ │ │ └K=K│ └K=K┤ │ │ ┌K=K│ └K=K┤ │ │ │ └K=K│ │ │ └K=K │ │ │ └K=K │ │ │ └K=K │ │ │ └K=K │ │ │ └K=K┐ │ │ │ │ ┌K=K│ │ ┌K=K┤ │ │ │ └K=K│ │ ┌K=K┤ │ │ ┌K=K│K=K┤ │
││ │ │ │ │ │ │ │ │ │ │ │ └L=L│ └L=L┤ │ │ ┌L=L│ └L=L┤ │ └L=L┤ │ └L=L┤ │ └L=L┤ │ └L=L┤ │ │ │ └L=L│ │ │ └L=L┤ │ │ │ │ ┌L=L│ │ ┌L=L┤ │ │ │ └L=L│ │ ┌L=L┤ │ │ ┌L=L│
││ │ │ │ │ │ │ │ │ │ │ │ │ └M=M│ └M=M┤ │ │ ┌M=M│ │ ┌M=M │ │ ┌M=M │ │ ┌M=M┐ │ │ ┌M=M│ └M=M┤ │ │ │ └M=M│ │ │ └M=M┤ │ │ │ │ ┌M=M│ │ ┌M=M┤ │ │ │ └M=M│ │ ┌M=M┤ │
││ │ │ │ │ │ │ │ │ │ │ │ │ │ └N=N│ └N=N┤ │ └N=N┤ │ └N=N┤ │ │ │ └N=N│ │ ┌N=N┤ │ │ ┌N=N│ └N=N┤ │ │ │ └N=N│ │ │ └N=N┤ │ │ │ │ ┌N=N│ │ ┌N=N┤ │ │ │ └N=N│
││ │ │ │ │ │ │ │ │ │ │ │ │ │ │ └O=O│ └O=O┐ │ │ ┌O=O│ └O=O┤ │ │ │ └O=O│ │ ┌O=O┤ │ │ ┌O=O│ └O=O┤ │ │ │ └O=O│ │ │ └O=O┤ │ │ │ │ ┌O=O│ │ ┌O=O┤ │
││ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ └P=P│ └P=P┤ │ │ ┌P=P│ └P=P┤ │ │ │ └P=P│ │ ┌P=P┤ │ │ ┌P=P│ └P=P┤ │ │ │ └P=P│ │ │ └P=P┤ │ │ │ │ ┌P=P│
││ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ └Q=Q│ └Q=Q┤ │ │ ┌Q=Q│ └Q=Q┤ │ │ │ └Q=Q│ │ ┌Q=Q┤ │ │ ┌Q=Q│ └Q=Q┤ │ │ │ └Q=Q│ │ │ └Q=Q┤ │
││ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ └R=R│ └R=R┤ │ │ ┌R=R│ └R=R┤ │ │ │ └R=R│ │ ┌R=R┤ │ │ ┌R=R│ └R=R┤ │ │ │ └R=R│
││ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ └S=S│ └S=S┤ │ │ ┌S=S│ └S=S┤ │ │ │ └S=S│ │ ┌S=S┤ │ │ ┌S=S│ └S=S┤ │
││ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ └T=T│ └T=T┤ │ │ ┌T=T│ └T=T┤ │ │ │ └T=T│ │ ┌T=T┤ │ │ ┌T=T│
││ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ └U=U│ └U=U┤ │ │ ┌U=U│ └U=U┤ │ │ │ └U=U│ │ ┌U=U┤ │
││ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ └V=V│ └V=V┤ │ │ ┌V=V│ └V=V┤ │ │ │ └V=V│
││ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ └W=W│ └W=W┤ │ │ ┌W=W│ └W=W┤ │
││ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ └X=X│ └X=X┤ │ │ ┌X=X│
││ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ └Y=Y│ └Y=Y┤ │
││ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ └Z=Z│
└┴───┴───────┴───────┴───────────┴───────────┴───────────┴───────────┴───────────────┴───────────────┴───────────────┴───────────────┴───────────────┴───────────────┴───────────────┴───────────────┴───────────────────┴───────────────────┴───────────────────┴───────────────────┴───────────────────┴───────────────────┴───────────────────┴───────────────────┴───────────────────┴───────────────────┴───────────────────┘
⍝ Vector of key=value pairs:
pairs ← ('one'1) ('two'2) ('three'3) ('four'4) ('five'5) ('six'6) ('seven'7)
tt←0 put foldl pairs ⍝ pairs folded into tree.
fmt tt ⍝ format of tree.
┌five=5
┌four=4┘
one=1┤
│ ┌seven=7
│ ┌six=6┘
│ ┌three=3┘
└two=2┘
tt ← bal tt ⍝ balanced tree.
fmt tt
┌five=5
┌four=4┤
│ └one=1
seven=7┤
│ ┌six=6
└three=3┤
└two=2
'six'get tt ⍝ value for key 'six'
6
tt ← tt rem'four' ⍝ key 'four' removed.
fmt tt
┌five=5┐
│ └one=1
seven=7┤
│ ┌six=6
└three=3┤
└two=2
vec tt ⍝ vector of key=value pairs
┌────────┬───────┬─────────┬───────┬─────────┬───────┐
│┌────┬─┐│┌───┬─┐│┌─────┬─┐│┌───┬─┐│┌─────┬─┐│┌───┬─┐│
││five│5│││one│1│││seven│7│││six│6│││three│3│││two│2││
│└────┴─┘│└───┴─┘│└─────┴─┘│└───┴─┘│└─────┴─┘│└───┴─┘│
└────────┴───────┴─────────┴───────┴─────────┴───────┘
chk tt ⍝ tree stats: ok size mean_depth height.
1 6 1 3
⎕rl ← 3⊃⎕ts ⍝ daily random seed.
chk bal tree {⍵?⍵} ¯1+2*10 ⍝ check balance of kilo-node random tree.
1 1023 8 10
Alpha test'_BST' ⍝ common BST tests.
⍝∇ sbst
Back to: code
Back to: Workspaces