⍝ 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.
⍝∇ redblack
Back to: code
Back to: Workspaces