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

Back to: code

Back to: Workspaces
```