Essays/Extended H
< Essays
Jump to navigation
Jump to search
The extended H algorithm embeds the complete binary tree of depth n on the plane, and finds use in VLSI applications.
o-o-o o-o-o o-o-o o-o-o o-o-o o-o-o o-o-o o-o-o | | | | | | | | o---o---o o---o---o o---o---o o---o---o | | | | | | | | | | | | o-o-o | o-o-o o-o-o | o-o-o o-o-o | o-o-o o-o-o | o-o-o | | | | o-------o-------o o-------o-------o | | | | | | o-o-o | o-o-o | o-o-o | o-o-o o-o-o | o-o-o | o-o-o | o-o-o | | | | | | | | | | | | | | o---o---o | o---o---o o---o---o | o---o---o | | | | | | | | | | o-o-o o-o-o | o-o-o o-o-o o-o-o o-o-o | o-o-o o-o-o | | o---------------o---------------o | | o-o-o o-o-o | o-o-o o-o-o o-o-o o-o-o | o-o-o o-o-o | | | | | | | | | | o---o---o | o---o---o o---o---o | o---o---o | | | | | | | | | | | | | | o-o-o | o-o-o | o-o-o | o-o-o o-o-o | o-o-o | o-o-o | o-o-o | | | | | | o-------o-------o o-------o-------o | | | | o-o-o | o-o-o o-o-o | o-o-o o-o-o | o-o-o o-o-o | o-o-o | | | | | | | | | | | | o---o---o o---o---o o---o---o o---o---o | | | | | | | | o-o-o o-o-o o-o-o o-o-o o-o-o o-o-o o-o-o o-o-o
The embedding can be effected by a recursive algorithm:
vh=: ('|-',a.) {~ ('-|',a.) i. ] extH=: 3 : 0 if. 0=y do. 1 1$'o' else. h=. vh |: extH y-1 'm c'=. <.-:$h ('-' (<m;i.c)}h) (|."1@[,.],.[) s,'-o-',s=. (m,3)$' ' end. )
In extH n there are 2^n leaves, instances of the letter o with exactly one non-blank neighbor (or no neighbors for 0=n ). The root is at the center of the array.
The result forms a striking display. The example at the beginning of this essay is extH 7 .
extH 0 o extH 1 o-o-o extH 2 o o | | o-o-o | | o o extH 3 o-o-o o-o-o | | o---o---o | | o-o-o o-o-o
Alternative solution
H3, halved iterations, eliminating transposition
cc=: (],1:,])@<.@-: c2=: cc #"1 (' | ', ' o-',:' | ')"_ c3=: cc # (' - ',.' o ',.' - ')"_ c4=: cc # (' - ',.' o|',.' - ')"_ c34=: c3`c4@. extH3=: 0&$: : (4 : 0) if. y=0 do. ,:,: 'o' return. end. if. y=1 do. ,:'o-o-o' return. end. g=. h , ( c2 {:$h) , |. h=. 1 extH3 y-2 g ,. (x c34 #g) ,. |."1 g )
See also User:Oleg Kobchenko/Extended H
Contributed by Roger Hui, with additional contributions by Oleg Kobchenko.