⍝ Red-black trees:

    put ← ∪ redblack            ⍝ ::       t ← t ∇ k v
    rem ← ~ redblack            ⍝ ::       t ← t ∇ k
    get ← ⍎ redblack            ⍝ ::       v ← k ∇ t
    fmt ← ⍕ redblack            ⍝ ::    -[;] ←   ∇ t
    vec ← ∊ redblack            ⍝ :: (k v)[] ←   ∇ t
    chk ← ? redblack            ⍝ ::   ok ht ←   ∇ t

    tree←0∘(put foldl)          ⍝ tree from vector of keys.

    vv ← ('one'1) ('two'2) ('three'3) ('four'4) ('five'5) ('six'6) ('seven'7)

    tt ← tree vv                ⍝ 7-node tree.

    fmt tt                      ⍝ format.
                           ┌[∘]         
                  ┌[five=5]┤            
                  │        └[∘]         
         ┌<four=4>┤                     
         │        │                 ┌[∘]
         │        │         ┌<one=1>┤   
         │        │         │       └[∘]
         │        └[seven=7]┤           
         │                  │       ┌[∘]
         │                  └<six=6>┤   
         │                          └[∘]
[three=3]┤                              
         │       ┌[∘]                   
         └[two=2]┤                      
                 └[∘]                   

    chk tt                      ⍝ tree stats.
1 7 2 4

    'two' get tt                ⍝ value for key "two".
2
    ⊢'eight' get tt             ⍝ no value for key "eight".
6::VALUE ERROR

    vec tt                      ⍝ vector of key=value pairs.
┌────────┬────────┬───────┬─────────┬───────┬─────────┬───────┐
│┌────┬─┐│┌────┬─┐│┌───┬─┐│┌─────┬─┐│┌───┬─┐│┌─────┬─┐│┌───┬─┐│
││five│5│││four│4│││one│1│││seven│7│││six│6│││three│3│││two│2││
│└────┴─┘│└────┴─┘│└───┴─┘│└─────┴─┘│└───┴─┘│└─────┴─┘│└───┴─┘│
└────────┴────────┴───────┴─────────┴───────┴─────────┴───────┘

    fmt tree ⍳15                ⍝ worst (most unbalanced) case.
                 ┌[∘]                          
           ┌[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 ← 1                     ⍝ random seed.
    vv  ← 100?100               ⍝ random vector.

    tt ← tree vv                ⍝ random tree.

    chk tt                      ⍝ tree stats: ok size mean_depth height.
1 100 5 8

    vv ≡ vv get¨⊂tt             ⍝ retrieve each value.
1
    (⍳⍴vv) ≡ vec tt             ⍝ vector of key=value pairs.
1
    tt ← tree ⍳7                ⍝ small tree.

    ∧/⊃∘chk¨tt∘rem¨ ⍳7          ⍝ check removal.
1

    kseq ← 1↓¨,\' ',12↑⎕a       ⍝ key sequences '' 'A' 'AB' 'ABC' ...

    kseq
┌┬─┬──┬───┬────┬─────┬──────┬───────┬────────┬─────────┬──────────┬───────────┬────────────┐
││A│AB│ABC│ABCD│ABCDE│ABCDEF│ABCDEFG│ABCDEFGH│ABCDEFGHI│ABCDEFGHIJ│ABCDEFGHIJK│ABCDEFGHIJKL│
└┴─┴──┴───┴────┴─────┴──────┴───────┴────────┴─────────┴──────────┴───────────┴────────────┘

    fmt∘tree¨  kseq             ⍝ successive inserts A B C ...
┌───┬─────────┬───────────────┬───────────────┬─────────────────────┬─────────────────────┬───────────────────────────┬───────────────────────────┬───────────────────────────┬───────────────────────────┬─────────────────────────────────┬─────────────────────────────────┬─────────────────────────────────┐
│[∘]│     ┌[∘]│     ┌[∘]      │           ┌[∘]│           ┌[∘]      │           ┌[∘]      │           ┌[∘]            │           ┌[∘]            │                 ┌[∘]      │                 ┌[∘]      │                 ┌[∘]            │                 ┌[∘]            │                 ┌[∘]            │
│   │[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]┤                     │
│   │         │           └[∘]│     │     ┌[∘]│     │     ┌[∘]      │     │           ┌[∘]│     │           ┌[∘]      │     │           ┌[∘]      │     │     │     ┌[∘]      │     │     │     ┌[∘]      │     │     │     ┌[∘]            │     │     │     ┌[∘]            │     │     │     ┌[∘]            │
│   │         │               │     └<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]┤                           │
│   │         │               │               │                 └[∘]│           │     ┌[∘]│           │     ┌[∘]      │           │           ┌[∘]│     │           ┌[∘]      │     │           ┌[∘]      │     │           ┌[∘]            │     │           ┌[∘]            │     │                 ┌[∘]      │
│   │         │               │               │                     │           └<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>┤               │
│   │         │               │               │                     │                     │                       └[∘]│                 │     ┌[∘]│           │     ┌[∘]      │           │           ┌[∘]│           │           ┌[∘]      │           │           ┌[∘]      │     │     │     │     ┌[∘]      │
│   │         │               │               │                     │                     │                           │                 └<G=G>┤   │           └[G=G]┤         │           │     ┌<G=G>┤   │           │     ┌[G=G]┤         │           │     ┌[G=G]┤         │     │     │     └[G=G]┤         │
│   │         │               │               │                     │                     │                           │                       └[∘]│                 │     ┌[∘]│           │     │     └[∘]│           │     │     └[∘]      │           │     │     └[∘]      │     │     │           └[∘]      │
│   │         │               │               │                     │                     │                           │                           │                 └<H=H>┤   │           └[H=H]┤         │           └<H=H>┤               │           └<H=H>┤               │     └[H=H]┤                     │
│   │         │               │               │                     │                     │                           │                           │                       └[∘]│                 │     ┌[∘]│                 │     ┌[∘]      │                 │           ┌[∘]│           │           ┌[∘]      │
│   │         │               │               │                     │                     │                           │                           │                           │                 └<I=I>┤   │                 └[I=I]┤         │                 │     ┌<I=I>┤   │           │     ┌[I=I]┤         │
│   │         │               │               │                     │                     │                           │                           │                           │                       └[∘]│                       │     ┌[∘]│                 │     │     └[∘]│           │     │     └[∘]      │
│   │         │               │               │                     │                     │                           │                           │                           │                           │                       └<J=J>┤   │                 └[J=J]┤         │           └<J=J>┤               │
│   │         │               │               │                     │                     │                           │                           │                           │                           │                             └[∘]│                       │     ┌[∘]│                 │     ┌[∘]      │
│   │         │               │               │                     │                     │                           │                           │                           │                           │                                 │                       └<K=K>┤   │                 └[K=K]┤         │
│   │         │               │               │                     │                     │                           │                           │                           │                           │                                 │                             └[∘]│                       │     ┌[∘]│
│   │         │               │               │                     │                     │                           │                           │                           │                           │                                 │                                 │                       └<L=L>┤   │
│   │         │               │               │                     │                     │                           │                           │                           │                           │                                 │                                 │                             └[∘]│
└───┴─────────┴───────────────┴───────────────┴─────────────────────┴─────────────────────┴───────────────────────────┴───────────────────────────┴───────────────────────────┴───────────────────────────┴─────────────────────────────────┴─────────────────────────────────┴─────────────────────────────────┘

    fmt¨ (tree 12↑⎕a)∘(rem foldl)¨ kseq         ⍝ successive removals A B C ...
┌─────────────────────────────────┬───────────────────────────┬───────────────────────────┬───────────────────────────┬───────────────────────────┬───────────────────────────┬───────────────────────────┬─────────────────────┬─────────────────────┬───────────────┬───────────────┬─────────┬───┐
│                 ┌[∘]            │                 ┌[∘]      │                 ┌[∘]      │                 ┌[∘]      │                 ┌[∘]      │           ┌[∘]            │           ┌[∘]            │           ┌[∘]      │           ┌[∘]      │           ┌[∘]│     ┌[∘]      │     ┌[∘]│[∘]│
│           ┌[A=A]┤               │           ┌[B=B]┤         │           ┌[C=C]┤         │           ┌[D=D]┤         │           ┌[E=E]┤         │     ┌[F=F]┤               │     ┌[G=G]┤               │     ┌[H=H]┤         │     ┌[I=I]┤         │     ┌[J=J]┤   │[K=K]┤         │[L=L]┤   │   │
│           │     └[∘]            │           │     │     ┌[∘]│           │     └[∘]      │           │     │     ┌[∘]│           │     └[∘]      │     │     │     ┌[∘]      │     │     └[∘]            │     │     │     ┌[∘]│     │     └[∘]      │     │     └[∘]│     │     ┌[∘]│     └[∘]│   │
│     ┌[B=B]┤                     │           │     └<C=C>┤   │     ┌[D=D]┤               │           │     └<E=E>┤   │     ┌[F=F]┤               │     │     └<G=G>┤         │[H=H]┤                     │     │     └<I=I>┤   │[J=J]┤               │[K=K]┤         │     └<L=L>┤   │         │   │
│     │     │     ┌[∘]            │           │           └[∘]│     │     │           ┌[∘]│           │           └[∘]│     │     │     ┌[∘]      │     │           └[∘]      │     │           ┌[∘]      │     │           └[∘]│     │     ┌[∘]      │     │     ┌[∘]│           └[∘]│         │   │
│     │     └[C=C]┤               │     ┌[D=D]┤               │     │     │     ┌[E=E]┤   │     ┌[F=F]┤               │     │     └[G=G]┤         │[H=H]┤                     │     │     ┌[I=I]┤         │[J=J]┤               │     └[K=K]┤         │     └[L=L]┤   │               │         │   │
│     │           └[∘]            │     │     │           ┌[∘]│     │     │     │     └[∘]│     │     │     ┌[∘]      │     │           └[∘]      │     │           ┌[∘]      │     │     │     └[∘]      │     │     ┌[∘]      │           │     ┌[∘]│           └[∘]│               │         │   │
│[D=D]┤                           │     │     │     ┌[E=E]┤   │     │     └<F=F>┤         │     │     └[G=G]┤         │[H=H]┤                     │     │     ┌[I=I]┤         │     └<J=J>┤               │     └[K=K]┤         │           └<L=L>┤   │               │               │         │   │
│     │                 ┌[∘]      │     │     │     │     └[∘]│     │           │     ┌[∘]│     │           └[∘]      │     │           ┌[∘]      │     │     │     └[∘]      │           │     ┌[∘]      │           │     ┌[∘]│                 └[∘]│               │               │         │   │
│     │           ┌[E=E]┤         │     │     └<F=F>┤         │     │           └[G=G]┤   │[H=H]┤                     │     │     ┌[I=I]┤         │     └<J=J>┤               │           └[K=K]┤         │           └<L=L>┤   │                     │               │               │         │   │
│     │           │     └[∘]      │     │           │     ┌[∘]│     │                 └[∘]│     │           ┌[∘]      │     │     │     └[∘]      │           │     ┌[∘]      │                 │     ┌[∘]│                 └[∘]│                     │               │               │         │   │
│     │     ┌<F=F>┤               │     │           └[G=G]┤   │[H=H]┤                     │     │     ┌[I=I]┤         │     └[J=J]┤               │           └[K=K]┤         │                 └<L=L>┤   │                     │                     │               │               │         │   │
│     │     │     │     ┌[∘]      │     │                 └[∘]│     │           ┌[∘]      │     │     │     └[∘]      │           │     ┌[∘]      │                 │     ┌[∘]│                       └[∘]│                     │                     │               │               │         │   │
│     │     │     └[G=G]┤         │[H=H]┤                     │     │     ┌[I=I]┤         │     └[J=J]┤               │           └[K=K]┤         │                 └<L=L>┤   │                           │                     │                     │               │               │         │   │
│     │     │           └[∘]      │     │           ┌[∘]      │     │     │     └[∘]      │           │     ┌[∘]      │                 │     ┌[∘]│                       └[∘]│                           │                     │                     │               │               │         │   │
│     └[H=H]┤                     │     │     ┌[I=I]┤         │     └[J=J]┤               │           └[K=K]┤         │                 └<L=L>┤   │                           │                           │                     │                     │               │               │         │   │
│           │           ┌[∘]      │     │     │     └[∘]      │           │     ┌[∘]      │                 │     ┌[∘]│                       └[∘]│                           │                           │                     │                     │               │               │         │   │
│           │     ┌[I=I]┤         │     └[J=J]┤               │           └[K=K]┤         │                 └<L=L>┤   │                           │                           │                           │                     │                     │               │               │         │   │
│           │     │     └[∘]      │           │     ┌[∘]      │                 │     ┌[∘]│                       └[∘]│                           │                           │                           │                     │                     │               │               │         │   │
│           └<J=J>┤               │           └[K=K]┤         │                 └<L=L>┤   │                           │                           │                           │                           │                     │                     │               │               │         │   │
│                 │     ┌[∘]      │                 │     ┌[∘]│                       └[∘]│                           │                           │                           │                           │                     │                     │               │               │         │   │
│                 └[K=K]┤         │                 └<L=L>┤   │                           │                           │                           │                           │                           │                     │                     │               │               │         │   │
│                       │     ┌[∘]│                       └[∘]│                           │                           │                           │                           │                           │                     │                     │               │               │         │   │
│                       └<L=L>┤   │                           │                           │                           │                           │                           │                           │                     │                     │               │               │         │   │
│                             └[∘]│                           │                           │                           │                           │                           │                           │                     │                     │               │               │         │   │
└─────────────────────────────────┴───────────────────────────┴───────────────────────────┴───────────────────────────┴───────────────────────────┴───────────────────────────┴───────────────────────────┴─────────────────────┴─────────────────────┴───────────────┴───────────────┴─────────┴───┘

    ⊢Alpha test '_BST'          ⍝ common BST tests.
1

Back to: code

Back to: Workspaces