⍝ Splay tree:
put ← ∪ splay ⍝ :: tree ← tree ∇ key val
get ← ⍎ splay ⍝ :: val tree ← key ∇ tree
rem ← ~ splay ⍝ :: tree ← tree ∇ key
fmt ← ⍕ splay ⍝ :: cmat ← ∇ tree
chk ← ? splay ⍝ :: ok height size ← ∇ tree
vec ← ∊ splay ⍝ :: (key val)[] ← ∇ tree
dep ← ≡ splay ⍝ :: depth ← key ∇ tree
tree←0∘(put foldl) ⍝ tree from vector of keys.
pairs ← ('one'1) ('two'2) ('three'3) ('four'4) ('five'5) ('six'6) ('seven'7)
fmt tree pairs
┌five=5
┌four=4┘
one=1┤
│ ┌seven=7
│ ┌six=6┘
│ ┌three=3┘
└two=2┘
pairs[⍋↑⊃¨pairs] ≡ vec tree pairs ⍝ check enlist of tree.
1
fmt tree 4 2 1 3 6 5 7 ⍝ balanced inserts.
┌1=1
┌2=2┤
│ └3=3
4=4┤
│ ┌5=5
└6=6┤
└7=7
fmt tree ⍳10 ⍝ linear inserts.
1=1┐
└2=2┐
└3=3┐
└4=4┐
└5=5┐
└6=6┐
└7=7┐
└8=8┐
└9=9┐
└10=10
⍝ This function creates a splay tree from the vector right arg and then
⍝ successively accesses its left arg value until the tree stabilises:
try←{↑fmt\¨↑∘(get/)traj ⍺,⊂tree ⍵} ⍝ see →traj←
10 try ⍳10 ⍝ successive accesses of key=10.
┌──┬─────────────────────────────────────────┐
│10│1=1┐ │
│ │ └2=2┐ │
│ │ └3=3┐ │
│ │ └4=4┐ │
│ │ └5=5┐ │
│ │ └6=6┐ │
│ │ └7=7┐ │
│ │ └8=8┐ │
│ │ └9=9┐ │
│ │ └10=10│
├──┼─────────────────────────────────────────┤
│10│1=1┐ │
│ │ └2=2┐ │
│ │ └3=3┐ │
│ │ └4=4┐ │
│ │ └5=5┐ │
│ │ └6=6┐ │
│ │ └7=7┐ │
│ │ │ ┌8=8│
│ │ │ ┌9=9┘ │
│ │ └10=10┘ │
├──┼─────────────────────────────────────────┤
│10│1=1┐ │
│ │ └2=2┐ │
│ │ └3=3┐ │
│ │ └4=4┐ │
│ │ └5=5┐ │
│ │ │ ┌6=6 │
│ │ │ ┌7=7┤ │
│ │ │ │ │ ┌8=8 │
│ │ │ │ └9=9┘ │
│ │ └10=10┘ │
├──┼─────────────────────────────────────────┤
│10│1=1┐ │
│ │ └2=2┐ │
│ │ └3=3┐ │
│ │ │ ┌4=4 │
│ │ │ ┌5=5┤ │
│ │ │ │ │ ┌6=6 │
│ │ │ │ └7=7┤ │
│ │ │ │ │ ┌8=8 │
│ │ │ │ └9=9┘ │
│ │ └10=10┘ │
├──┼─────────────────────────────────────────┤
│10│1=1┐ │
│ │ │ ┌2=2 │
│ │ │ ┌3=3┤ │
│ │ │ │ │ ┌4=4 │
│ │ │ │ └5=5┤ │
│ │ │ │ │ ┌6=6 │
│ │ │ │ └7=7┤ │
│ │ │ │ │ ┌8=8 │
│ │ │ │ └9=9┘ │
│ │ └10=10┘ │
├──┼─────────────────────────────────────────┤
│10│ ┌1=1┐ │
│ │ │ │ ┌2=2 │
│ │ │ └3=3┤ │
│ │ │ │ ┌4=4 │
│ │ │ └5=5┤ │
│ │ │ │ ┌6=6 │
│ │ │ └7=7┤ │
│ │ │ │ ┌8=8 │
│ │ │ └9=9┘ │
│ │10=10┘ │
└──┴─────────────────────────────────────────┘
1 try ⌽⍳10 ⍝ successive accesses of key=1.
┌─┬─────────────────────────────────────────┐
│1│ ┌1=1│
│ │ ┌2=2┘ │
│ │ ┌3=3┘ │
│ │ ┌4=4┘ │
│ │ ┌5=5┘ │
│ │ ┌6=6┘ │
│ │ ┌7=7┘ │
│ │ ┌8=8┘ │
│ │ ┌9=9┘ │
│ │10=10┘ │
├─┼─────────────────────────────────────────┤
│1│ ┌1=1┐ │
│ │ │ └2=2┐ │
│ │ │ └3=3│
│ │ ┌4=4┘ │
│ │ ┌5=5┘ │
│ │ ┌6=6┘ │
│ │ ┌7=7┘ │
│ │ ┌8=8┘ │
│ │ ┌9=9┘ │
│ │10=10┘ │
├─┼─────────────────────────────────────────┤
│1│ ┌1=1┐ │
│ │ │ │ ┌2=2┐ │
│ │ │ │ │ └3=3 │
│ │ │ └4=4┤ │
│ │ │ └5=5 │
│ │ ┌6=6┘ │
│ │ ┌7=7┘ │
│ │ ┌8=8┘ │
│ │ ┌9=9┘ │
│ │10=10┘ │
├─┼─────────────────────────────────────────┤
│1│ ┌1=1┐ │
│ │ │ │ ┌2=2┐ │
│ │ │ │ │ └3=3 │
│ │ │ │ ┌4=4┤ │
│ │ │ │ │ └5=5 │
│ │ │ └6=6┤ │
│ │ │ └7=7 │
│ │ ┌8=8┘ │
│ │ ┌9=9┘ │
│ │10=10┘ │
├─┼─────────────────────────────────────────┤
│1│ ┌1=1┐ │
│ │ │ │ ┌2=2┐ │
│ │ │ │ │ └3=3 │
│ │ │ │ ┌4=4┤ │
│ │ │ │ │ └5=5 │
│ │ │ │ ┌6=6┤ │
│ │ │ │ │ └7=7 │
│ │ │ └8=8┤ │
│ │ │ └9=9 │
│ │10=10┘ │
├─┼─────────────────────────────────────────┤
│1│1=1┐ │
│ │ │ ┌2=2┐ │
│ │ │ │ └3=3 │
│ │ │ ┌4=4┤ │
│ │ │ │ └5=5 │
│ │ │ ┌6=6┤ │
│ │ │ │ └7=7 │
│ │ │ ┌8=8┤ │
│ │ │ │ └9=9 │
│ │ └10=10┘ │
└─┴─────────────────────────────────────────┘
1 try 3 2 1 ⍝ test double rotation.
┌─┬───────────┐
│1│ ┌1=1│
│ │ ┌2=2┘ │
│ │3=3┘ │
├─┼───────────┤
│1│1=1┐ │
│ │ └2=2┐ │
│ │ └3=3│
└─┴───────────┘
3 try 4 2 3 ⍝ test double counter-rotation.
┌─┬───────────┐
│3│ ┌2=2┐ │
│ │ │ └3=3│
│ │4=4┘ │
├─┼───────────┤
│3│ ┌2=2 │
│ │3=3┤ │
│ │ └4=4 │
└─┴───────────┘
chk tree⍳7 ⍝ tree stats: ok size mean_depth height
1 7 3 7
⎕rl←7*5 ⍝ random seed.
tt ← tree 256?256 ⍝ random 256-node tree.
chk tt ⍝ ... has reasonable height (17).
1 256 8 17
revt←{⊃⌽⍵ get ⍺} ⍝ revised tree, ignoring retrieved value.
tt ← tt revt foldl 256?256 ⍝ search once for each key.
chk tt ⍝ ... increases (worsens) tree height (46).
1 256 23 46
keys←16?256 ⍝ random selection of keys.
keys dep¨⊂tt ⍝ depth of keys.
38 17 8 35 31 24 9 28 31 22 3 14 19 31 29 37
tt ← tt revt foldl 16/keys ⍝ repeated searches for a subset of keys.
keys dep¨⊂tt ⍝ ... reduces key depths.
7 4 6 6 5 6 5 4 4 3 4 2 3 3 2 1
chk tt ⍝ ... reduces (improves) tree height (23).
1 256 9 23
tt ← tt rem foldl 256?256 ⍝ remove all nodes in random order.
tt ⍝ check all nodes removed.
0
Alpha test'_BST' ⍝ common BST tests.
⍝∇ splay foldl traj
Back to: code
Back to: Workspaces