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

Back to: code

Back to: Workspaces
```