⍝ 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