⍝ 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.

Back to: code

Back to: Workspaces