btree.apl

⍝ Simple BST
jt←↑(2 6) (3 5) (4 0) (0 0) (0 0) (7 8) (0 0) (0 0) ⍝ child nodes
jd← 27    14    10    3     19    35    31    42    ⍝ data
FindJE ← {
  (t d)←⍺
  s←⍵
  1∘{x←⍺⊃d ⋄ n←(1+⍵>x)⊃⍺⌷t ⋄ (⍵=x)∨0=n:⍺ ⋄ n∇⍵}s
}
InsertJE ← {
  (t d)←⍺
  s←⍵
  v←⍺ FindJE ⍵
  t←{(1+≢d)@(⊂v(1+s>v⊃d))⊢⍵}⍣(0≠≢d)⊢t⍪1
  t (d,⍵)
}
⎕←'BST JE'
⎕←(jt jd) FindJE 3
⎕←(jt jd) InsertJE 45


ap←0  1  2  3  2  1  6  6 ⍝ parent nodes
al←1  1  1  1  2  2  1  2 ⍝ position (left=1/right=2)
ad←27 14 10 3  19 35 31 42 ⍝ data
FindAH ← {
  (p l d)←⍺ ⍝ full tree
  s←⍵ ⍝ 
  1∘{x←⍺⊃d ⋄ (⍵=x)∨~(1+⍵>x)∊(⍺=p)/l:⍺ ⋄ ((1+⍵>x)⊃1~⍨⍸⍺=p)∇⍵}s
}
InsertAH ← {
  (p l d)←⍺
  ⎕←v←⍺ FindAH ⍵
  (p,v) (l,1+⍵>v⊃d) (d,⍵)
}
⎕←''
⎕←'BST AH'
⎕←'Find' ((ap al ad) FindAH 3)
⎕←'Find' ((ap al ad) FindAH 45)
⎕←(ap al ad) InsertAH 45

⍝ AVL

⍝ New tree to test with:
⍝   1 2 3 4 5
ap1←0 1 1 2 2
al1←1 1 2 1 2
ad1←5 3 6 1 4
ah1←3 2 1 1 1

RRotAH ← {
  (p l d h)←⍺
  y←⍵
  x←⊃⍸(l=1)∧p=y
  t2←⊃⍸(l=2)∧p=x
  p[x]←p[y]          ⍝ Step 1
  p[y]←x
  l[x]←l[y] ⋄ l[y]←2 ⍝ Step 2
  p[t2]←y ⋄ l[t2]←1  ⍝ Step 3
  h[y]←1+⌈/h[⍸p=y]   ⍝ always update y first, it is the child node.
  h[x]←1+⌈/h[⍸p=x]   ⍝ Step 4
  p l d h 
}
LRotAH ← {
  (p l d h)←⍺
  x←⍵
  ⎕←'y: ',y←⊃⍸(l=2)∧p=x
  t2←⊃⍸(l=1)∧p=y
  p[y]←p[x]          ⍝ Step 1
  p[x]←y
  l[y]←l[x] ⋄ l[x]←1 ⍝ Step 2
  p[t2]←x ⋄ l[t2]←2  ⍝ Step 3
  h[x]←1+⌈/h[⍸p=x]   ⍝ always update y first, it is the child node.
  h[y]←1+⌈/h[⍸p=y]   ⍝ Step 4
  p l d h 
}

⎕←'AVL AH'
⎕←↑r←ap1 al1 ad1 ah1 RRotAH 1
⎕←''
⎕←↑r LRotAH 2