⍝ Insert value ⍵ in AVL tree ⍺:
put ← ∪ avl ⍝ :: tree ← tree ∇ key value
rem ← ~ avl ⍝ :: tree ← tree ∇ key
get ← ⍎ avl ⍝ :: value ← tree ∇ key
chk ← ? avl ⍝ :: ok height maxbal ← ∇ tree
fmt ← ⍕ avl ⍝ :: cmat ← ∇ tree
vec ← ∊ avl ⍝ :: (key val)[] ← ∇ tree
tree←0∘(put foldl) ⍝ tree from vector of keys.
tree ⍳7
┌─┬─┬─────────────────────────────────────────────────────────┐
│4│0│┌───────────────────────────┬───────────────────────────┐│
│ │ ││┌─┬─┬─────────────────────┐│┌─┬─┬─────────────────────┐││
│ │ │││2│0│┌─────────┬─────────┐│││6│0│┌─────────┬─────────┐│││
│ │ │││ │ ││┌─┬─┬───┐│┌─┬─┬───┐││││ │ ││┌─┬─┬───┐│┌─┬─┬───┐││││
│ │ │││ │ │││1│0│0 0│││3│0│0 0│││││ │ │││5│0│0 0│││7│0│0 0│││││
│ │ │││ │ ││└─┴─┴───┘│└─┴─┴───┘││││ │ ││└─┴─┴───┘│└─┴─┴───┘││││
│ │ │││ │ │└─────────┴─────────┘│││ │ │└─────────┴─────────┘│││
│ │ ││└─┴─┴─────────────────────┘│└─┴─┴─────────────────────┘││
│ │ │└───────────────────────────┴───────────────────────────┘│
└─┴─┴─────────────────────────────────────────────────────────┘
fmt tree ⍳7
┌─1=1
┌─2=2┤
│ └─3=3
4=4┤
│ ┌─5=5
└─6=6┤
└─7=7
kseq ← 1↓¨,\' ',12↑⎕a ⍝ key sequence.
kseq
┌┬─┬──┬───┬────┬─────┬──────┬───────┬────────┬─────────┬──────────┬───────────┬────────────┐
││A│AB│ABC│ABCD│ABCDE│ABCDEF│ABCDEFG│ABCDEFGH│ABCDEFGHI│ABCDEFGHIJ│ABCDEFGHIJK│ABCDEFGHIJKL│
└┴─┴──┴───┴────┴─────┴──────┴───────┴────────┴─────────┴──────────┴───────────┴────────────┘
fmt∘tree¨ kseq ⍝ successive inserts A B C ...
┌┬───┬────────┬────────┬─────────────┬─────────────┬─────────────┬─────────────┬──────────────────┬──────────────────┬──────────────────┬──────────────────┬──────────────────┐
││A=A│A=A┐ │ ┌─A=A│ ┌<A=A │ ┌<A=A │ ┌─A=A│ ┌─A=A│ ┌─A=A │ ┌─A=A │ ┌─A=A │ ┌─A=A │ ┌─A=A│
││ │ └>B=B│B=B┤ │B=B┤ │B=B┤ │ ┌─B=B┤ │ ┌─B=B┤ │ ┌<B=B┤ │ ┌<B=B┤ │ ┌<B=B┤ │ ┌<B=B┤ │ ┌─B=B┤ │
││ │ │ └─C=C│ └>C=C┐ │ │ ┌─C=C│ │ └─C=C│ │ └─C=C│ │ └─C=C │ │ └─C=C │ │ └─C=C │ │ └─C=C │ │ └─C=C│
││ │ │ │ └>D=D│ └>D=D┤ │D=D┤ │D=D┤ │D=D┤ │D=D┤ │D=D┤ │D=D┤ │ ┌─D=D┤ │
││ │ │ │ │ └─E=E│ └─E=E┐ │ │ ┌─E=E│ │ ┌<E=E │ │ ┌<E=E │ │ ┌─E=E│ │ ┌─E=E│ │ │ ┌─E=E│
││ │ │ │ │ │ └>F=F│ └─F=F┤ │ └>F=F┤ │ └>F=F┤ │ │ ┌─F=F┤ │ │ ┌─F=F┤ │ │ └─F=F┤ │
││ │ │ │ │ │ │ └─G=G│ └>G=G┐ │ │ ┌─G=G│ │ │ └─G=G│ │ │ └─G=G│ │ └─G=G│
││ │ │ │ │ │ │ │ └>H=H│ └>H=H┤ │ └>H=H┤ │ └>H=H┤ │H=H┤ │
││ │ │ │ │ │ │ │ │ └─I=I│ └─I=I┐ │ │ ┌─I=I│ │ ┌<I=I │
││ │ │ │ │ │ │ │ │ │ └>J=J│ └─J=J┤ │ └─J=J┤ │
││ │ │ │ │ │ │ │ │ │ │ └─K=K│ └>K=K┐ │
││ │ │ │ │ │ │ │ │ │ │ │ └>L=L│
└┴───┴────────┴────────┴─────────────┴─────────────┴─────────────┴─────────────┴──────────────────┴──────────────────┴──────────────────┴──────────────────┴──────────────────┘
(tree 12↑⎕a){fmt ⍺⍺ rem foldl ⍵}¨kseq ⍝ successive removals A B ..
┌──────────────────┬──────────────────┬──────────────────┬──────────────────┬──────────────────┬──────────────────┬─────────────┬─────────────┬─────────────┬────────┬────────┬───┬┐
│ ┌─A=A│ ┌─B=B┐ │ ┌<C=C │ ┌>D=D┐ │ ┌─E=E │ ┌<F=F┐ │ ┌─G=G│ ┌─H=H┐ │ ┌<I=I │ ┌─J=J│K=K┐ │L=L││
│ ┌─B=B┤ │ │ └>C=C│ ┌─D=D┤ │ │ └>E=E│ ┌<F=F┤ │ │ └>G=G │ ┌─H=H┤ │ │ └>I=I│J=J┤ │K=K┤ │ └>L=L│ ││
│ │ └─C=C│ ┌─D=D┤ │ │ │ ┌─E=E│ ┌─F=F┤ │ │ └─G=G │H=H┤ │ │ └─I=I│J=J┤ │ └>K=K┐ │ └─L=L│ │ ││
│ ┌─D=D┤ │ │ │ ┌─E=E│ │ └>F=F┤ │ │ └<G=G │H=H┤ │ │ ┌<I=I │J=J┤ │ └─K=K┐ │ └>L=L│ │ │ ││
│ │ │ ┌─E=E│ │ └─F=F┤ │ │ └─G=G│H=H┤ │ │ ┌<I=I │ └>J=J┤ │ └─K=K┐ │ └>L=L│ │ │ │ ││
│ │ └─F=F┤ │ │ └─G=G│H=H┤ │ │ ┌<I=I │ └>J=J┤ │ └>K=K┐ │ └>L=L│ │ │ │ │ ││
│ │ └─G=G│H=H┤ │ │ ┌<I=I │ └─J=J┤ │ └>K=K┐ │ └>L=L│ │ │ │ │ │ ││
│H=H┤ │ │ ┌<I=I │ └─J=J┤ │ └>K=K┐ │ └>L=L│ │ │ │ │ │ │ ││
│ │ ┌<I=I │ └─J=J┤ │ └>K=K┐ │ └>L=L│ │ │ │ │ │ │ │ ││
│ └─J=J┤ │ └>K=K┐ │ └>L=L│ │ │ │ │ │ │ │ │ ││
│ └>K=K┐ │ └>L=L│ │ │ │ │ │ │ │ │ │ ││
│ └>L=L│ │ │ │ │ │ │ │ │ │ │ ││
└──────────────────┴──────────────────┴──────────────────┴──────────────────┴──────────────────┴──────────────────┴─────────────┴─────────────┴─────────────┴────────┴────────┴───┴┘
⍝ successive removals of root node:
(tree 12↑⎕a){fmt ⍺⍺ rem foldl ⍵}¨,\' HIJDEFGKBCLA'
┌──────────────────┬──────────────────┬──────────────────┬──────────────────┬──────────────────┬─────────────┬─────────────┬─────────────┬─────────────┬────────┬────────┬───┬┐
│ ┌─A=A│ ┌─A=A│ ┌─A=A│ ┌─A=A │ ┌─A=A │ ┌─A=A│ ┌─A=A│ ┌─A=A│ ┌<A=A │ ┌─A=A│ ┌>A=A│A=A││
│ ┌─B=B┤ │ ┌─B=B┤ │ ┌─B=B┤ │ ┌<B=B┤ │ ┌<B=B┤ │ ┌─B=B┤ │ ┌─B=B┤ │ ┌>B=B┤ │B=B┤ │C=C┤ │L=L┘ │ ││
│ │ └─C=C│ │ └─C=C│ │ └─C=C│ │ └─C=C │ │ └─C=C │ │ └─C=C│ │ └─C=C│ │ └─C=C│ │ ┌>C=C│ └─L=L│ │ ││
│ ┌─D=D┤ │ ┌>D=D┤ │ ┌>D=D┤ │D=D┤ │E=E┤ │F=F┤ │G=G┤ │K=K┤ │ └>L=L┘ │ │ │ ││
│ │ │ ┌─E=E│ │ │ ┌─E=E│ │ │ ┌─E=E│ │ ┌─E=E│ │ ┌>F=F┐ │ │ ┌─G=G│ └─K=K┐ │ └<L=L │ │ │ │ ││
│ │ └─F=F┤ │ │ └─F=F┤ │ │ └─F=F┤ │ │ ┌>F=F┤ │ │ │ └>G=G│ └─K=K┤ │ └>L=L│ │ │ │ │ ││
│ │ └─G=G│ │ └─G=G│ │ └─G=G│ │ │ └─G=G│ └>K=K┤ │ └─L=L│ │ │ │ │ │ ││
│H=H┤ │I=I┤ │J=J┤ │ └>K=K┤ │ └<L=L │ │ │ │ │ │ │ ││
│ │ ┌<I=I │ │ ┌─J=J │ └<K=K┐ │ └<L=L │ │ │ │ │ │ │ │ ││
│ └─J=J┤ │ └<K=K┤ │ └>L=L │ │ │ │ │ │ │ │ │ ││
│ └>K=K┐ │ └─L=L │ │ │ │ │ │ │ │ │ │ ││
│ └>L=L│ │ │ │ │ │ │ │ │ │ │ ││
└──────────────────┴──────────────────┴──────────────────┴──────────────────┴──────────────────┴─────────────┴─────────────┴─────────────┴─────────────┴────────┴────────┴───┴┘
display fmt tree ⎕a
┌→──────────────────────┐
↓ ┌─A=A│
│ ┌─B=B┤ │
│ │ └─C=C│
│ ┌─D=D┤ │
│ │ │ ┌─E=E│
│ │ └─F=F┤ │
│ │ └─G=G│
│ ┌─H=H┤ │
│ │ │ ┌─I=I│
│ │ │ ┌─J=J┤ │
│ │ │ │ └─K=K│
│ │ └─L=L┤ │
│ │ │ ┌─M=M│
│ │ └─N=N┤ │
│ │ └─O=O│
│P=P┤ │
│ │ ┌─Q=Q │
│ │ ┌<R=R┤ │
│ │ │ └─S=S │
│ └─T=T┤ │
│ │ ┌─U=U│
│ │ ┌─V=V┤ │
│ │ │ └─W=W│
│ └>X=X┤ │
│ └─Y=Y┐ │
│ └>Z=Z│
└───────────────────────┘
fmt¨ ∪ tree¨↓pmat 5 ⍝ test double rotation.
┌─────────────┬─────────────┬─────────────┬─────────────┬─────────────┬─────────────┐
│ ┌<1=1 │ ┌─1=1┐ │ ┌─1=1┐ │ ┌─1=1│ ┌>1=1│ ┌>1=1│
│2=2┤ │ │ └>2=2│ │ └>2=2│ ┌>2=2┤ │ ┌─2=2┘ │ ┌─2=2┘ │
│ │ ┌─3=3│3=3┤ │3=3┤ │ │ └─3=3│3=3┤ │3=3┤ │
│ └>4=4┤ │ └─4=4┐ │ │ ┌>4=4│4=4┤ │ └─4=4┐ │ │ ┌>4=4│
│ └─5=5│ └>5=5│ └─5=5┘ │ └<5=5 │ └>5=5│ └─5=5┘ │
└─────────────┴─────────────┴─────────────┴─────────────┴─────────────┴─────────────┘
tt←tree ('one'1) ('two'2) ('three'3) ('four'4) ('five'5) ('six'6) ('seven'7)
display fmt tt
┌→─────────────────────────────┐
↓ ┌>five=5 │
│ ┌<four=4┘ │
│one=1┤ │
│ │ ┌>seven=7│
│ │ ┌>six=6┘ │
│ └>three=3┤ │
│ └<two=2 │
└──────────────────────────────┘
vec tt ⍝ enlist of tree.
┌────────┬────────┬───────┬─────────┬───────┬─────────┬───────┐
│┌────┬─┐│┌────┬─┐│┌───┬─┐│┌─────┬─┐│┌───┬─┐│┌─────┬─┐│┌───┬─┐│
││five│5│││four│4│││one│1│││seven│7│││six│6│││three│3│││two│2││
│└────┴─┘│└────┴─┘│└───┴─┘│└─────┴─┘│└───┴─┘│└─────┴─┘│└───┴─┘│
└────────┴────────┴───────┴─────────┴───────┴─────────┴───────┘
tt ← tt put foldl ('one' 11)('two' 22)('three'33)
display fmt tt
┌→───────────────────────────────┐
↓ ┌>five=5 │
│ ┌<four=4┘ │
│one=11┤ │
│ │ ┌>seven=7│
│ │ ┌>six=6┘ │
│ └>three=33┤ │
│ └<two=22 │
└────────────────────────────────┘
0 ≡ tt rem foldl 'seven' 'six' 'five' 'four' 'one' 'two' 'three'
1
0 ≡ tt rem foldl 'six' 'four' 'seven' 'three' 'five' 'one' 'two'
1
tt∘get¨ 'two' 'four' 'six' ⍝ search tree for keys.
22 4 6
⊢tt get 'eight' ⍝ key not in tree.
6::VALUE ERROR
chk tt ⍝ ok size mean_depth height.
1 7 2 4
fib←{ ⍝ Depth-⍵ worst-case fibonacci tree.
⊃⍬⍴⎕io{ ⍝ first item is tree.
⍵=0:0 ⍺ ⍝ f 0 → []
⍵=1:(⍺ 0(0 0))(⍺+1) ⍝ f 1 → ⍺ [] []
l m←⍺ ∇ ⍵-2 ⍝ left subtree and next value
r n←(m+1)∇ ⍵-1 ⍝ right .. .. .. .. ..
(m 1(l r))n ⍝ f ⍵+1 → ⍺ [f ⍵-2] [f ⍵-1]
}⍵ ⍝ :: tree next ← next ∇ depth
}
display fmt fib 7 ⍝ depth-7 worst-case.
┌→──────────────────────────────────────────────┐
↓ ┌<1=1 │
│ ┌<2=2┤ │
│ │ └>3=3┐ │
│ │ └>4=4 │
│ ┌<5=5┤ │
│ │ │ ┌<6=6┐ │
│ │ │ │ └>7=7 │
│ │ └>8=8┤ │
│ │ │ ┌<9=9 │
│ │ └>10=10┤ │
│ │ └>11=11┐ │
│ │ └>12=12 │
│13=13┤ │
│ │ ┌<14=14┐ │
│ │ │ └>15=15 │
│ │ ┌<16=16┤ │
│ │ │ │ ┌<17=17 │
│ │ │ └>18=18┤ │
│ │ │ └>19=19┐ │
│ │ │ └>20=20 │
│ └>21=21┤ │
│ │ ┌<22=22 │
│ │ ┌<23=23┤ │
│ │ │ └>24=24┐ │
│ │ │ └>25=25 │
│ └>26=26┤ │
│ │ ┌<27=27┐ │
│ │ │ └>28=28 │
│ └>29=29┤ │
│ │ ┌<30=30 │
│ └>31=31┤ │
│ └>32=32┐ │
│ └>33=33│
└───────────────────────────────────────────────┘
display fmt (fib 7)rem 1 ⍝ removing worst-case node.
┌→───────────────────────────────────────┐
↓ ┌─2=2 │
│ ┌─3=3┤ │
│ │ └─4=4 │
│ ┌─5=5┤ │
│ │ └─6=6┐ │
│ │ └>7=7 │
│ ┌─8=8┤ │
│ │ │ ┌<9=9 │
│ │ └─10=10┤ │
│ │ └>11=11┐ │
│ │ └>12=12 │
│ ┌─13=13┤ │
│ │ │ ┌<14=14┐ │
│ │ │ │ └>15=15 │
│ │ └─16=16┤ │
│ │ │ ┌<17=17 │
│ │ └>18=18┤ │
│ │ └>19=19┐ │
│ │ └>20=20│
│21=21┤ │
│ │ ┌<22=22 │
│ │ ┌<23=23┤ │
│ │ │ └>24=24┐ │
│ │ │ └>25=25 │
│ └─26=26┤ │
│ │ ┌<27=27┐ │
│ │ │ └>28=28 │
│ └>29=29┤ │
│ │ ┌<30=30 │
│ └>31=31┤ │
│ └>32=32┐ │
│ └>33=33│
└────────────────────────────────────────┘
Alpha test'_BST' ⍝ common BST tests.
⍝∇ avl display foldl pmat
Back to: code
Back to: Workspaces