10ステップ目まで描画したHツリー H木、H tree またはH-Tree は フラクタル 図形の1つであり、直線の両端に、その長さの1/√2 の長さの垂線 を追加し続けることによって構成される図形である。繰り返しパターンがアルファベットの "H" に似ているため、H木と呼ばれる。ハウスドルフ次元 は2であり、矩形 内の任意の点に対し、十分近いH木上の点が存在する。著しい特性として「任意のステップにおいて、中心から端点までの距離がすべて等しい」というものがあり、例えば集積回路 におけるクロックの分配などや、マイクロ波工学 などへの応用などが代表例として知られている。
H木は、任意の長さの線分 を元に、「その線分の両端に垂直な1/√2の長さの2本の線分を追加する」という処理を繰り返すことで構成できる[ 1]
また、白銀比 である1:√2の長方形から開始し、長辺を2等分し、その重心を直線で結ぶという処理でも構築できる。1:√2 = √2/2:1であるため、分割された長方形もまた白銀比の長方形である。他の比で表される長方形でも同様の処理は可能であるが、白銀比でない長方形では、奇数ステップと偶数ステップでは重心間の距離の比が一定ではない。
H木 は自己相似図形（フラクタル図形）であり、そのハウスドルフ次元は2である。
矩形（白銀比の長方形）内の任意の点に対し、十分近いH木上の点が存在する。しかし、全ての点が「含まれる」わけではなく、例えば1ステップ目の線分に対する垂直二等分線はH木に含まれない。
VLSIの設計において、H木は木のノード数に比例する面積を使用する、完全二分木のレイアウトとして用いられる。また、H木の形は長方形内に効率的にグラフを描画可能であり、巡回セールスマン問題の距離の自乗和が大きくなる点の集合としても用いられる。
H木は全てのノードまでの距離が等しいため、中央に発振子を置き、葉ノードの位置に素子を置くことで、クロック の伝播遅延を揃えることができる[ 6] [ 7]
これまで述べたような2次元平面上のH木は、H木の平面に対して垂直な方向に線分を加えるように変更することで、3次元構造へと一般化することが可能である[ 8] フォトニック結晶 やメタマテリアル において artificial electromagnetic atoms を構成することが知られており、マイクロ波工学において潜在的な用途を有する可能性がある。
H木はフラクタルキャノピーの1つであり、隣接する線分間の角度は常に180度である。矩形内の任意の点に対して十分近づくという性質を持つため、「曲線」ではないが、空間充填曲線 に似ている。
位相幾何学 的には、H木にはデンドロイドと同様の性質があるといえる。しかし、デンドロイドは閉集合 である必要があるため、閉集合ではないH木はデンドロイドではない。
マンデルブロ木は、より自然な見た目を生成するために、H木の位置から僅かにずれた位置に、線分の代わりに長方形を使用するフラクタル図形である。長方形同士が重ならないようにするために、スケールを1/√2より小さくする必要がある[ 9]
Bern, Marshall; Eppstein, David (1993), “Worst-case bounds for subadditive geometric graphs” , Proc. 9th Annual Symposium on Computational Geometry , Association for Computing Machinery , pp. 183–188, doi :10.1145/160985.161018 , http://www.ics.uci.edu/~eppstein/pubs/BerEpp-SCG-93.pdf Browning, Sally A. (1980), The Tree Machine: A Highly Concurrent Computing Environment , http://authors.library.caltech.edu/26932/ Burkis, J. (1991), “Clock tree synthesis for high performance ASICs”, IEEE International Conference on ASIC , pp. 9.8.1–9.8.4, doi :10.1109/ASIC.1991.242921 Hou, Bo; Xie, Hang; Wen, Weijia; Sheng, Ping (2008), “Three-dimensional metallic fractals and their photonic crystal characteristics”, Physical Review B 77 : 125113, doi :10.1103/PhysRevB.77.125113 Kaloshin, Vadim; Saprykina, Maria (2012), “An example of a nearly integrable Hamiltonian system with a trajectory dense in a set of maximal Hausdorff dimension”, Communications in Mathematical Physics 315 (3): 643–697, doi :10.1007/s00220-012-1532-x , MR 2981810 Leiserson, Charles E. (1980), “Area-efficient graph layouts”, 21st Annual Symposium on Foundations of Computer Science (FOCS 1980) , pp. 270–281, doi :10.1109/SFCS.1980.13 Nguyen, Quang Vinh; Huang, Mao Lin (2002), “A space-optimized tree visualization”, IEEE Symposium on Information Visualization , pp. 85–92, doi :10.1109/INFVIS.2002.1173152 Ullman, Jeffrey D. (1984), Computational Aspects of VSLI , Computer Science Press Wen, Weijia; Zhou, Lei; Li, Jensen; Ge, Weikun; Chan, C. T.; Sheng, Ping (2002), Subwavelength photonic band gaps from planar fractals , 89 , Physical Review Letters , p. 223901, doi :10.1103/PhysRevLett.89.223901
Kabai, S. (2002), Mathematical Graphics I: Lessons in Computer Graphics Using Mathematica , Püspökladány, Hungary: Uniconstant, p. 231 Lauwerier, H. (1991), Fractals: Endlessly Repeated Geometric Figures , Princeton, NJ: Princeton University Press, pp. 1–2
