TT/ngnk-libs/trees/hsuthesis.k

\l trees.k
`0:("Tree data cut-and-pasted from Aaron Hsu's Thesis (https://scholarworks.iu.edu/dspace/handle/2022/24749)"
   "is rendered with the algorithms here.  Feel free to match against those rendered in the thesis.")

/ show tree x (given by DFS preorder parent vector) with labels y
sh:{(tr;l):pad[p]t1[p:1+|/#'y]x;`0:"P:",`k@x;`0:(,""),/+(tr;ctl@y@l)}

TL:"ABEFGLMNOPVZ"

`0:"p.61"
:D:0 1 2 1 2 3 2 1 2 3 3 2 3 3 2
sh[p@ \D;$!#D]

`0:"p.71"
:D:0 1 2 3 1 2 3 3 4 1 2 3 4 5 6 5 5 6 3 4 5 6 5 5 6 3 4
T:3 1 0 7 1 2 9 0 10 1 3 1 2 0 10 9 0 10 1 2 0 10 9 0 10 0 10
K:1 0 0 0 0 1 0 1 0 1 1 0 2 1 0 0 1 0 0 2 1 0 0 1 0 1 0
X:0 -5 0 -6 -7 0 -8 0 -5 -9 0 -10 0 0 -1 -11 0 -5 -12 0 0 -10 -8 0 -10 0 -12
sh[p@ \D;,/'+(TL@T;$K)]

`0:"p.73"
:D:0 1 2 3 1 2 3 3 4 1 2 3 4 5 6 5 5 6 3 4 5 6 5 5 6 3 4
sh[p@ \D;$!#D]

`0:"p.79"
D:0 1 2 3 1 2 3 3 4 1 2 3 4 5 6 5 5 6 3 4 5 6 5 5 6 3 4
P:0 0 1 2 0 4 5 5 7 0 9 10 11 12 13 12 12 16 10 18 19 20 19 19 23 10 25
`0:"depth:"
sh[p@ \D;$!#D]
`0:"parent:"
sh[P;$P]

`0:"p.80"
P:0 0 1 2 0 4 5 5 7 0 9 10 11 12 13 12 12 16 10 18 19 20 19 19 23 10 25
T:3 1 0 7 1 2 9 0 10 1 3 1 2 0 10 9 0 10 1 2 0 10 9 0 10 0 10
K:1 0 0 0 0 1 0 1 0 1 1 0 2 1 0 0 1 0 0 2 1 0 0 1 0 1 0
X:0 -5 0 -6 -7 0 -8 0 -5 -10 0 -11 0 0 -1 -12 0 -5 -14 0 0 -11 -8 0 -11 0 -14
sh[p@ \D;TL@T]

`0:"p.82"
D:0 1 2 1 2 3 2 1 2 3 3 2 3 3 2
sh[p@ \D;$!#D]

`0:"p.93"
P:0 0 1 2 0 4 5 5 7 0 9 10 11 12 13 12 12 16 10 18 19 20 19 19 23 10 25
T:3 1 0 7 1 2 9 0 10 1 3 1 2 0 10 9 0 10 1 2 0 10 9 0 10 0 10
sh[P;TL@T]

`0:"p.100"
I:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
D:0 1 2 3 4 5 4 5 6 7 6 6 7 4 5 6 5 6 7 8
P:0 0 1 2 3 4 3 6 7 8 7 7 11 3 13 14 13 16 17 18
T:3 1 3 2 0 10 3 2 0 10 9 0 10 2 0 10 3 2 0 10
K:1 2 1 2 1 0 1 2 1 0 0 1 0 2 1 0 1 2 1 0
N:0 -5 0 0 0 -2 0 0 0 -2 -6 0 -1 0 0 -2 0 0 0 -2

I,:20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
D,:7 7 8 5 6 7 6 7 8 9 8 8 9 6 7
P,:17 17 21 13 23 24 23 26 27 28 27 27 31 23 33
T,:9 0 10 2 0 10 3 2 0 10 9 0 10 0 10
K,:0 1 0 2 1 0 1 2 1 0 0 1 0 1 0
N,:-6 0 -1 0 0 -2 0 0 0 -2 -6 0 -1 0 -1
`0:"depth:"
sh[p@ \D;TL@T]
`0:"parent:"
sh[P;TL@T]

I:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
P:0 0 1 35 3 4 3 36 7 8 7 7 11 3 13 14 13 37 17 18 17 17
T:3 1 10 2 0 10 10 2 0 10 9 0 10 2 0 10 10 2 0 10 9 0
K:1 2 1 2 1 0 1 2 1 0 0 1 0 2 1 0 1 2 1 0 0 1
N:0 -5 35 0 0 -2 36 0 0 -2 -6 0 -1 0 0 -2 37 0 0 -2 -6 0
R:0 0 0 35 35 35 35 36 36 36 36 36 36 35 35 35 35 37 37 37 37 37

I,:22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
P,:21 13 23 24 23 38 27 28 27 27 31 23 33 35 36 37 38
T,:10 2 0 10 10 2 0 10 9 0 10 0 10 3 3 3 3
K,:0 2 1 0 1 2 1 0 0 1 0 1 0 1 1 1 1
N,:-1 0 0 -2 38 0 0 -2 -6 0 -1 0 -1 0 0 0 0
R,:37 35 35 35 35 38 38 38 38 38 38 35 35 0 35 35 35
`0:"resort parent vector"
R:dfo[P]
P:redo[ \P;R]
sh[P;TL@T@<R]

`0:"p.108"
`0:"before:"
I:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
P:0 0 1 15 3 3 5 6 15 8 15 10 11 10 10 15
T:3 1 10 4 10 1 0 7 0 7 2 0 7 9 10 3
K:0 1 1 0 0 0 0 0 0 0 2 0 0 1 0 1
N:0 -5 15 0 -1 -6 0 -7 0 -8 0 0 -9 -10 -1 0
R:0 0 0 15 15 15 15 15 15 15 15 15 15 15 15 0
sh[P;TL@T]

`0:"after:"
I:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
P:0 0 1 2 19 4 4 6 7 8 19 10 11 19 13 14 15 14 14 19
T:3 2 1 10 4 10 2 1 0 7 2 0 7 2 2 0 7 9 10 3
K:0 -1 1 1 0 0 0 0 0 0 0 0 0 0 2 0 0 1 0 1
N:0 -5 -5 19 0 -1 -6 -6 0 -7 0 0 -8 0 0 0 -9 -10 -1 0
R:0 0 0 0 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 0
sh[P;TL@T]

`0:"p.110"
P:0 0 1 15 3 3 5 6 15 8 15 10 11 10 10 15
T:3 1 10 4 10 1 0 7 0 7 2 0 7 9 10 3
sh[P;TL@T]

/
/ ----  Not valid yet ----
`0:"p.112"
P:0 0 0 1 15 3 3 3 5 6 15 15 8 15 15 10 11 10 10 15
T:3 1 1 10 4 10 1 1 0 7 0 0 7 2 2 0 7 9 10 3
K:0 1 1 1 0 0 0 0 0 0 0 0 0 2 2 0 0 1 0 1
N:0 -5 -5 15 0 -1 -6 -6 0 -7 0 0 -8 0 0 0 -9 -10 -1 0
R:0 0 0 0 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 0
`0:"resort parent vector"

R:dfo[P]
\

`0:"p.113"
P:0 0 0 2 19 4 4 4 7 8 19 19 11 19 19 14 15 14 14 19
R:0 0 0 0 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 0
I:2 11 14 7
sh[P;$R]

`0:"p.114"
P:0 0 0 2 19 4 4 4 7 8 19 19 11 19 19 14 15 14 14 19
sh[P;$!#P]

P:0 0 1 2 19 4 4 6 7 8 19 10 11 19 13 14 15 14 14 19
sh[P;$!#P]

`0:"p.117"
`0:"before:"
I:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
P:0 0 1 2 20 4 4 6 7 20 9 10 10 10 9 14 15 20 17 18 20
T:3 2 1 10 4 10 2 0 7 4 2 10 9 10 2 0 7 2 0 7 3
K:0 -1 1 1 0 0 0 0 0 0 2 0 1 0 0 0 0 0 0 0 1
N:0 -5 -5 20 0 -1 0 0 0 0 0 -2 -6 -1 0 0 -7 0 0 -8 0
R:0 0 0 0 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 0
sh[P;TL@T]

`0:"after:"
I:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
P:0 0 1 2 20 20 5 6 7 20 20 9 9 9 10 14 15 20 17 18 20
T:3 2 1 10 10 4 2 0 7 2 4 10 9 10 2 0 7 2 0 7 3
K:0 -1 1 1 0 0 0 0 0 2 0 0 1 0 0 0 0 0 0 0 1
N:0 -5 -5 20 -1 -1 0 0 0 0 0 -2 -6 -1 0 0 -7 0 0 -8 0
R:0 0 0 0 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 0
sh[P;TL@T]

`0:"p.118"
P:0 0 1 2 20 4 4 6 7 20 9 10 10 10 9 14 15 20 17 18 20
sh[P;$!#P]

`0:"p.121"
I:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
P:0 0 1 2 53 4 5 5 5 8 9 0 11 12 54 14 15 15 15 18
T:3 2 1 10 2 2 10 9 2 0 9 2 1 10 2 2 10 9 2 0
K:0 -1 1 1 0 2 0 1 3 3 0 -1 1 1 0 2 0 1 3 3
N:0 -5 -5 53 0 0 -1 -6 0 0 -7 -8 -8 54 0 0 -1 -6 0 0
R:0 0 0 0 53 53 53 53 53 53 53 0 0 0 54 54 54 54 54 54

I,:20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
P,:19 18 21 0 23 24 55 26 27 27 27 30 31 30 33 30 35 0 37 38
T,:9 0 9 2 1 10 2 2 10 9 2 0 9 0 9 0 9 2 1 10
K,:0 3 0 -1 1 1 0 2 0 1 3 3 0 3 0 3 0 -1 1 1
N,:-7 0 -7 -9 -9 55 0 0 -1 -6 0 0 -7 0 -7 0 -7 -10 -10 56
R,:54 54 54 0 0 0 55 55 55 55 55 55 55 55 55 55 55 0 0 0

I,:40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
P,:56 40 41 41 41 44 45 44 47 44 49 44 51 53 54 55 56
T,:2 2 10 9 2 0 9 0 9 0 9 0 9 3 3 3 3
K,:0 2 0 1 3 3 0 3 0 3 0 3 0 1 1 1 1
N,:0 0 -1 -6 0 0 -7 0 -7 0 -7 0 -7 0 0 0 0
R,:56 56 56 56 56 56 56 56 56 56 56 56 56 0 0 0 0
`0:"resort parent vector"
R:dfo[P]
P:redo[ \P;R]
sh[P;TL@T@<R]

P:0 0 1 2 53 4 5 5 5 8 9 0 11 12 54 14 15 15 15 18 19 18 21 0
P,:23 24 55 26 27 27 27 30 31 30 33 30 35 0 37 38 56 40 41
P,:41 41 44 45 44 47 44 49 44 51 53 54 55 56

`0:"resort parent vector"
R:dfo[P]
P:redo[ \P;R]
sh[P;TL@T@<R]

`0:"p.123"
`0:"before:"
I:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
P:0 0 1 2 24 4 5 6 6 6 24 10 11 12 13 13 12 16 16 16
T:3 2 1 10 2 1 2 10 9 10 2 2 2 8 9 9 2 10 9 0
K:0 -1 1 1 -1 0 2 0 1 0 0 2 1 2 2 1 2 0 1 0
N:0 -5 -5 24 -6 -6 0 -2 -7 -1 0 0 0 0 -8 -9 0 -6 -10 0
R:0 0 0 0 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24

I,:20 21 22 23 24
P,:19 11 11 22 24
T,:7 9 0 7 3
K,:0 1 0 0 1
N,:-11 -10 0 -12 0
R,:24 24 24 24 0
sh[P;TL@T]

`0:"after:"
I:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
P:0 0 0 0 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24
T:3 10 1 2 10 9 10 2 1 2 0 9 0 9 10 2 9 9 8
K:0 1 1 -1 0 1 0 2 0 -1 0 1 0 1 0 2 1 2 2
N:0 24 -5 -5 -1 -7 -2 0 -6 -6 0 -10 0 -10 -6 0 -9 -8 0
R:0 0 0 0 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24

I,:19 20 21 22 23 24
P,:24 12 24 24 10 24
T,:2 7 2 2 7 3
K,:1 0 2 0 0 1
N,:0 -11 0 0 -12 0
R,:24 24 24 24 24 0
sh[P;TL@T]

`0:"p.131"
D:0 1 2 3 4 5 6 7 7 7 5 6 6 6 3 4 5 5 5 3 4 5 5 5 6 3 4 4 0 0 0 0 0 0 0 0 0
sh[p@ \D;$!#D]

`0:"p.137"
I:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
P:0 0 0 0 44 44 44 4 44 44 44 44 45 45 12 45 45 45 45 45
T:3 10 1 2 0 1 2 7 0 10 2 2 0 1 7 2 0 10 2 2
K:0 1 1 -1 0 0 -1 0 0 1 1 0 0 0 0 -1 0 1 1 0
N:1 44 -5 -5 0 -6 -6 -7 0 45 0 0 0 -8 -9 -8 0 46 0 0
R:0 0 0 0 44 44 44 44 44 44 44 44 45 45 45 45 45 45 45 45

I,:20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
P,:46 46 46 46 46 46 46 46 46 46 26 46 46 46 46 46
T,:10 9 10 2 1 2 0 9 10 2 7 1 2 10 9 10
K,:0 1 0 2 0 -1 0 1 0 2 0 0 -1 0 1 0
N,:-6 -11 -8 0 -10 -10 0 -11 -10 0 -12 -8 -8 -8 -11 -8
R,:46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46

I,:36 37 38 39 40 41 42 43 44 45 46
P,:46 46 46 46 46 46 46 46 44 45 46
T,:2 1 2 10 9 10 2 2 3 3 3
K,:2 0 -1 0 1 0 2 0 1 1 1
N,:0 -6 -6 -6 -11 -6 0 0 1 1 3
R,:46 46 46 46 46 46 46 46 0 44 45
`0:"resort parent vector"
R:dfo[P]
P:redo[ \P;R]
sh[P;TL@T@<R]

`0:"p.184"
P:0 0 1 2 0 4 5 5 7 0 9 10 11 12 13 12 12 16 10 18 19 20 19 19 23 10 25
sh[P;$!#P]

`0:"p.185"
P:0 0 1 2 0 4 5 5 7 8 9 8 8 12 5 14
sh[P;$!#P]