Essays/Extended H

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
)