rslt ← {larg} (op ##.splay) rarg ⍝ Splay trees.
put ← 'put' splay ⍝ insert/update :: tree ← tree ∇ key val
get ← 'get' splay ⍝ retrieve val for key :: val tree ← key ∇ tree
rem ← 'rem' splay ⍝ remove key from tree :: tree ← tree ∇ key
fmt ← 'fmt' splay ⍝ formatted tree :: char[;] ← ∇ tree
chk ← 'chk' splay ⍝ tree statistics :: ok size depth height ← ∇ tree
vec ← 'vec' splay ⍝ enlist of tree :: (key val)[] ← ∇ tree
dep ← 'dep' splay ⍝ height of key ⍺ :: depth ← key ∇ tree
See →BST←
A splay tree is a self-balancing binary search tree; each time a node is access-
ed, it is rotated nearer to the root. This mean that frequently accessed nodes
wind up with shorter search paths.
Unlike →avl← and →redblack← trees, splay trees are not maintained in a state of
reasonable balance. Instead, nodes with frequently accessed keys _tend_ to
migrate towards the root, which _tends_ to give them shorter access times.
The performance of a splay tree may not be as optimal as one of its more complex
relatives, but its implementation is considerably simpler.
Node Access
-----------
In the following, node [A] is accessed. There are three cases, × two left-right
mirrow-image orientations.
[0] Node [A] is the root node: no change.
[1] Node [A] is the left (right) child of the root.
[2] Node [A] is the left (right) child of a left (right) child.
¯¯¯¯ ¯¯¯¯
[3] Node [A] is the right (left) child of a left (right) child.
¯¯¯¯¯ ¯¯¯¯
Cases [1 2 3] are summarised in the following diagram:
<--- m i r r o r i m a g e s --->
┌──────────────────────┬────────────────────────┐
[1] │ B [A] │ B [A] │
│ / \ → / \ │ / \ → / \ │
│ [A] r p B │ r [A] B p │
│ / \ / \ │ / \ / \ │
│ p q q r │ q p r q │
├──────────────────────┼────────────────────────┤
[2] │ C [A] │ C [A] │
│ / \ → / \ │ / \ → / \ │
│ B s p B │ s B B p │
│ / \ / \ │ / \ / \ │
│ [A] r q C │ r [A] C q │
│ / \ / \ │ / \ / \ │
│p q r s │ q p s r │
├──────────────────────┼────────────────────────┤
[3] │ C [A] │ C [A] │
│ / \ → / \ │ / \ → / \ │
│ B s / \ │ s B / \ │
│ / \ B C │ / \ C B │
│p [A] / \ / \ │ [A] p / \ / \ │
│ / \ p q r s │ / \ s r q p│
│ q r │ r q │
└──────────────────────┴────────────────────────┘
Node removal
------------
[splay] uses the "quicker" method of node removal. See →BST←.
Technical notes
---------------
The tree is implemented as the pair-of-pairs: (key val) (lft rgt)
key: node key
val: node value
lft: left subtree or 0
rgt: right subtree or 0
The two double rotations are coded by applying function [rot] twice. If speed is
critical, we could code them directly as follows:
rotrr←{ ⍝ double ⍵-⍵-wise rotion of tree ⍺.
C(BAr s)←⍵ wise\⍺ ⍝ C A
B(Apq r)←⍵ wise\BAr ⍝ / \ → / \
A(p q)←⍵ wise\Apq ⍝ B s p B
⍝ / \ / \
Crs←⍵ wise\C(r s) ⍝ A r q C
BqC←⍵ wise\B(q Crs) ⍝ / \ / \
⍵ wise\A(p BqC) ⍝ p q r s
}
rotrl←{ ⍝ double ⍵-¯⍵-rotation of tree ⍺.
C(BpA s)←⍵ wise\⍺ ⍝ C A
B(p Aqr)←⍵ wise\BpA ⍝ / \ → / \
A(q r)←⍵ wise\Aqr ⍝ B s / \
⍝ / \ B C
Bpq←⍵ wise\B(p q) ⍝ p A / \ / \
Crs←⍵ wise\C(r s) ⍝ / \ p q r s
⍵ wise\A(Bpq Crs) ⍝ q r
}
Notice that function ⍵-wise is applied under scan (\), which means that it aff-
ects only the second item of the node pair (key val)(lft rgt).
References
----------
http://en.wikipedia.org/wiki/Splay_tree
Examples
--------
⍝ derive splay tree functions:
put ← 'put' splay ⍝ insert/update :: tree ← tree ∇ key val
get ← 'get' splay ⍝ retrieve val for key :: val tree ← key ∇ tree
rem ← 'rem' splay ⍝ remove key from tree :: tree ← tree ∇ key
fmt ← 'fmt' splay ⍝ formatted tree :: char[;] ← ∇ tree
chk ← 'chk' splay ⍝ tree statistics :: ok size depth height ← ∇ tree
vec ← 'vec' splay ⍝ enlist of tree :: (key val)[] ← ∇ tree
dep ← 'dep' splay ⍝ depth of key ⍺ :: depth ← key ∇ tree
⍝ key=value pairs:
pairs ← ('one'1) ('two'2) ('three'3) ('four'4) ('five'5) ('six'6) ('seven'7)
tt ← 0 put foldl pairs ⍝ insert key=val pairs into a splay tree.
display fmt tt ⍝ show resulting tree.
┌→────────────────────────────────┐
↓ ┌five=5 │
│ ┌four=4┘ │
│one=1┤ │
│ │ ┌seven=7│
│ │ ┌six=6┘ │
│ │ ┌three=3┘ │
│ └two=2┘ │
└─────────────────────────────────┘
'seven' dep tt ⍝ depth of key 'seven'.
5
val tt ← 'seven' get tt ⍝ first access of key 'seven',
display fmt tt ⍝ moves it towards the root.
┌→────────────────────────────────┐
↓ ┌five=5 │
│ ┌four=4┘ │
│one=1┤ │
│ │ ┌seven=7┐ │
│ │ │ └six=6┐ │
│ │ │ └three=3│
│ └two=2┘ │
└─────────────────────────────────┘
'seven' dep tt ⍝ new depth of key 'seven'.
3
val tt ← 'seven' get tt ⍝ second access of key 'seven',
display fmt tt ⍝ moves it to the root.
┌→──────────────────────────┐
↓ ┌five=5│
│ ┌four=4┘ │
│ ┌one=1┘ │
│seven=7┤ │
│ │ ┌six=6┐ │
│ │ │ └three=3│
│ └two=2┘ │
└───────────────────────────┘
'seven' dep tt ⍝ depth of key 'seven'.
1
chk tt ⍝ tree is: ok size=7, mean_depth=2, height=4.
1 7 2 4
tt ← tt rem 'seven' ⍝ tree with key 'seven' removed.
display fmt tt
┌→────────────────────────┐
↓ ┌five=5│
│ ┌four=4┘ │
│ ┌one=1┘ │
│six=6┤ │
│ │ ┌three=3 │
│ └two=2┘ │
└─────────────────────────┘
disp vec tt ⍝ enlist of tree key=val pairs.
┌→───────┬────────┬───────┬───────┬─────────┬───────┐
│┌→───┬─┐│┌→───┬─┐│┌→──┬─┐│┌→──┬─┐│┌→────┬─┐│┌→──┬─┐│
││five│5│││four│4│││one│1│││six│6│││three│3│││two│2││
│└───→┴─┘│└───→┴─┘│└──→┴─┘│└──→┴─┘│└────→┴─┘│└──→┴─┘│
└───────→┴───────→┴──────→┴──────→┴────────→┴──────→┘
⍝ Notice how repeated retrieval of a particular key
⍝ lifts its node towards the root:
disp ↑fmt\¨↑∘(get/)traj 10,⊂0 put foldl ⍳10 ⍝ see →traj←
┌→─┬─────────────────────────────────────────┐
↓ │1=1┐ │
│ │ └2=2┐ │
│ │ └3=3┐ │
│ │ └4=4┐ │
│10│ └5=5┐ │
│ │ └6=6┐ │
│ │ └7=7┐ │
│ │ └8=8┐ │
│ │ └9=9┐ │
│ │ └10=10↓
├~─┼────────────────────────────────────────→┤
│ │1=1┐ │
│ │ └2=2┐ │
│ │ └3=3┐ │
│ │ └4=4┐ │
│10│ └5=5┐ │
│ │ └6=6┐ │
│ │ └7=7┐ │
│ │ │ ┌8=8│
│ │ │ ┌9=9┘ │
│ │ └10=10┘ ↓
├~─┼────────────────────────────────────────→┤
│ │ 1=1┐ │
│ │ └2=2┐ │
│ │ └3=3┐ │
│ │ └4=4┐ │
│10│ └5=5┐ │
│ │ │ ┌6=6 │
│ │ │ ┌7=7┤ │
│ │ │ │ │ ┌8=8 │
│ │ │ │ └9=9┘ │
│ │ └10=10┘ ↓
├~─┼────────────────────────────────────────→┤
│ │ 1=1┐ │
│ │ └2=2┐ │
│ │ └3=3┐ │
│ │ │ ┌4=4 │
│10│ │ ┌5=5┤ │
│ │ │ │ │ ┌6=6 │
│ │ │ │ └7=7┤ │
│ │ │ │ │ ┌8=8 │
│ │ │ │ └9=9┘ │
│ │ └10=10┘ ↓
├~─┼────────────────────────────────────────→┤
│ │ 1=1┐ │
│ │ │ ┌2=2 │
│ │ │ ┌3=3┤ │
│ │ │ │ │ ┌4=4 │
│10│ │ │ └5=5┤ │
│ │ │ │ │ ┌6=6 │
│ │ │ │ └7=7┤ │
│ │ │ │ │ ┌8=8 │
│ │ │ │ └9=9┘ │
│ │ └10=10┘ ↓
├~─┼────────────────────────────────────────→┤
│ │ ┌1=1┐ │
│ │ │ │ ┌2=2 │
│ │ │ └3=3┤ │
│ │ │ │ ┌4=4 │
│10│ │ └5=5┤ │
│ │ │ │ ┌6=6 │
│ │ │ └7=7┤ │
│ │ │ │ ┌8=8 │
│ │ │ └9=9┘ │
│ │ 10=10┘ ↓
└~─┴────────────────────────────────────────→┘
See also: BST alists sbst avl redblack foldl traj
Back to: contents
Back to: Dyalog APL
Trouble seeing APL font?