```avl←{⎕IO ⎕ML←0 1                        ⍝ Adelson-Velskii, Landis trees.

get←{                               ⍝ value for key ⍵ from AVL tree ⍺.
⍺≡0:                            ⍝ key not in tree: no value.
(k v)_ subs←⍺                   ⍝ next key, value and subtrees.
k≡⍵:v                           ⍝ match: value from tree.
dir←-/⍋↑⍵ k                     ⍝ natch: search direction.
sub sib←dir wise subs           ⍝ subtree to search and its sibling.
sub ∇ ⍵                         ⍝ value from subtree.
}                                   ⍝ :: t ∇ k → v

put←{                               ⍝ tree ⍺ with key=value ⍵.
⍺≡0:(⍵ 0(0 0))1                 ⍝ null tree: new leaf, height incr.
(kv obal subs)(key val)←⍺ ⍵     ⍝ next node and key=val pair.
key≡⊃kv:(⍵ obal subs)0          ⍝ match: just replace value.
dir obv←1 ¯1×-/⍋↑key(⊃kv)       ⍝ natch: search direction and obverse.
sub sib←dir wise subs           ⍝ subtree to search and its sibling.
nsub inc←sub ∇ ⍵                ⍝ new subtree and height increment.
new←obv proj kv obal(nsub sib)  ⍝ tree with new node.
inc=0:new 0                     ⍝ no height increment: done.
(dir balance new)(obal=0)       ⍝ height increment if OLD balance is 0.
}                                   ⍝ :: t ∇ k v → t i

rem←{                               ⍝ tree ⍺ without key ⍵.
⍺≡0:0 0                         ⍝ key not in tree: done.
⍵≡⊃⊃⍺:rmnode ⍺                  ⍝ match: remove node.
dir obv←1 ¯1×-/⍋↑⍵(⊃⊃⍺)         ⍝ natch: search direction and obverse.
kv obal(sub sib)←obv proj ⍺     ⍝ subtree to search and its sibling.
nsub inc←sub ∇ ⍵                ⍝ new subtree and height increment.
new←obv proj kv obal(nsub sib)  ⍝ tree with node removed.
inc=0:new 0                     ⍝ no height decrement: done.
nkv nbal nsubs←obv balance new  ⍝ balanced tree.
(nkv nbal nsubs)(-nbal=0)       ⍝ height decrement if NEW balance is 0.
}                                   ⍝ :: t ∇ k → t i

rmnode←{                            ⍝ node ⍵ removed.
kv obal subs←⍵                  ⍝ subnodes.
0∊subs:((subs⍳0)⊃⌽subs)¯1       ⍝ either sub null: the other.
lft rgt←subs                    ⍝ left and right non-null subtrees.
(sk sv)_ _←rgt limt ¯1          ⍝ successor key=val.
rem inc←rgt rem sk              ⍝ right subtree with successor removed.
new←(sk sv)obal(lft rem)        ⍝ target node replaced with successor.
inc=0:new 0                     ⍝ no height decrement: done.
nkv nbal nsubs←¯1 balance new   ⍝ new balanced node.
(nkv nbal nsubs)(-nbal=0)       ⍝ height decrement if NEW balance is 0.
}                                   ⍝ :: ∇ t → t i

limt←{                              ⍝ ⍵-most node of (sub)tree ⍺.
sub←⊃⍵ wise⊃⌽⍺                  ⍝ ⍵-sub.
sub≡0:⍺                         ⍝ null: this.
sub ∇ ⍵                         ⍝ else: ⍵-most of sub.
}                                   ⍝ :: t ∇ d → t

balance←{                           ⍝ tree ⍵ with balancing moment ⍺.
kv obal subs←⍵                  ⍝ original tree.
new←⍺+obal                      ⍝ new balance.
0∊obal new:kv new subs          ⍝ balance bits absorb moment: done.
(_ Bbal _)_←obal wise subs      ⍝ otherwise:
Bbal≠-obal:(-obal)rot1 ⍵        ⍝   single or
(-obal)rot2 ⍵        ⍝     double rotation.
}                                   ⍝ :: m ∇ t → t

rot1←{                              ⍝ single ⍺-rotation of tree ⍵.
Akv Abal(B r)←⍺ proj ⍵          ⍝    <<A         yB>
Bkv Bbal(p q)←⍺ proj B          ⍝     / \        / \      where x y z
AAbal←-⍺×Bbal=0                 ⍝   <Bx  r  =>  p  <Az    are such that:
BBbal←+⍺×Bbal=0                 ⍝   / \            / \    <B> →  B> <A
AA←⍺ proj Akv AAbal(q r)        ⍝  p   q          q   r   <B  → <B> <A>
⍺ proj Bkv BBbal(p AA)          ⍝
}                                   ⍝ :: d ∇ t → t

rot2←{                              ⍝ double ⍺-rotation of tree ⍵.
Akv Abal(B s)←⍺ proj ⍵          ⍝    <<A         <<A          <C>
Bkv Bbal(p C)←⍺ proj B          ⍝     / \         ⌿ \         / \
Ckv Cbal(q r)←⍺ proj C          ⍝    B>  s  =>  <C.  s  =>  <By xA>
AAbal←⍺×Cbal=-⍺                 ⍝   / ⍀         / \         / \ / \
BBbal←-⍺×Cbal=⍺                 ⍝  p  xCy     <B.  r       p  q r  s
BB←⍺ proj Bkv BBbal(p q)        ⍝     / \     / \
AA←⍺ proj Akv AAbal(r s)        ⍝    q   r   p   q
⍺ proj Ckv 0(BB AA)             ⍝                   where:
}                                   ⍝ :: d ∇ t → t      x y∊'<>' '< ' ' >'

vec←{                               ⍝ enlist of tree ⍵.
0≡⍵:⍬                           ⍝ null tree: null vector.
key_val bal(lft rgt)←⍵          ⍝ node info and subtrees.
(∇ lft),(⊂key_val),∇ rgt        ⍝ left_vec, key=val, right_vec.
}                                   ⍝ :: ∇ t → [k v]

chk←{                               ⍝ tree stats / integrity check.
0=≡⍵:(⍵≡0)0 0 0 ⍬               ⍝ null: ok maxbal=0 height=0 key-range.
(key _)bal subs←⍵               ⍝ key, balance and subtrees.
stats←(⍺+1)∇¨subs               ⍝ subtrees stats.
oks szs dps hts krs←↓⍉↑stats    ⍝ oks sizes depths heights key-ranges.
keys←↑key{⍺,(⊂⍺⍺),⍵}/krs        ⍝ subtree key ranges.
okkey←{⍵≡⍳⍴⍵}⍋↑keys             ⍝ left keys << key >> right keys.
okhgt←bal=--/hts                ⍝ balance is height difference.
okbal←bal∊¯1 0 1                ⍝ balance is in range.
ok←okkey∧okbal∧okhgt∧∧/oks      ⍝ subtree is good.
sz←1++/szs                      ⍝ subtree size.
dp←⍺++/dps                      ⍝ total node depth.
ht←1+⌈/hts                      ⍝ subtree height.
kr←⌽2⍴¯1⌽keys                   ⍝ key range for subtree.
⍺>0:ok sz dp ht kr              ⍝ subtree: ok size tot_dep height range.
ok sz(⌊0.5+dp÷sz)ht             ⍝ root: ok size mean_depth height.
}                                   ⍝ :: ∇ t → y s d h {r}

fmt←{                               ⍝ formatted tree ⍵.
null←0 0⍴''                     ⍝ format of null tree.
⍵≡0:null                        ⍝ null tree: null format.
(key val)bal subs←⍵             ⍝ node info.
key_val←⍺,↑,/⍕¨key'='val        ⍝ formatted >>key=value
deco←(1+bal)⊃'><' '─' '<>'      ⍝ balance decorators.
fmts←{⊖⍵}\'┌└'{                 ⍝ hang subtrees by ┌─ ─┐ branches.
0 0≡⍴⍵:⍵                    ⍝ null: done.
⍉⌽↑(⊂⌽⍺,mask/'│'),↓⌽⍉⍵      ⍝ subtree suspended by branch.
}¨{⊖⍵}\deco ∇¨subs              ⍝ formatted subtrees.
case←~null null≡¨fmts           ⍝ non-null subtree cases.
join←(2⊥case)⊃'∘┐┘┤'            ⍝ subtree joining char.
join≡'∘':↑,↓key_val             ⍝ leaf: done.
}                                   ⍝ :: ∇ t → [-;]

proj←{(⍺=0 0 ¯1)⌽¨⍵}                ⍝ ⍺-projection of node ⍵.
wise←{(⍺=1)⌽⍵}                      ⍝ subtrees ⍵ in -⍺, +⍺ order.

op←⍺⍺{f←⍺⍺ ⋄ ⊃⎕CR'f'}0              ⍝ operand label.

'∪'≡op:⊃⍺ put ⍵                     ⍝ tree ⍺ with key=value pair ⍵.
'⍎'≡op:⍺ get ⍵                      ⍝ value for key ⍺ in tree ⍵.
'~'≡op:⊃⍺ rem ⍵                     ⍝ tree ⍺ without key ⍵.
'⍕'≡op:''fmt ⍵                      ⍝ formatted tree ⍵.
'∊'≡op:vec ⍵                        ⍝ vector of key=value pairs for tree ⍵.
'?'≡op:4↑0 chk ⍵                    ⍝ stats for tree ⍵: ok size dpth height.
}

code_colours

test script

Back to: notes

Back to: Workspaces
```