एच ट्री

Not to be confused with एच ट्री, एक लिनक्स फाइल सिस्टम अनुक्रमण संरचना.

एच ट्री के पहले दस स्तर

फ्रैक्टल ज्यामिति में, एच ट्री एक फ्रैक्टल ट्री संरचना है जो लंबवत रेखा खंडों से निर्मित होता है, प्रत्येक अगले बड़े आसन्न खंड से 2 वर्गमूल के कारक से छोटा होता है। इसे इसलिए ऐसा कहा जाता है क्योंकि इसका दोहराव स्वरूप "एच" अक्षर जैसा दिखता है। इसमें हॉसडॉर्फ आयाम 2 है, और आयत में सभी बिंदु के निकट अव्यवस्थित रूप से आता है। इसके अनुप्रयोगों में वीएलएसआई डिजाइन और माइक्रोवेव इंजीनियरिंग सम्मलित हैं।

निर्माण

एक एच ट्री का निर्माण अव्यवस्थित लंबाई के एक रेखा खंड के साथ प्रारंभ करके किया जा सकता है, इसके अंतिम बिंदुओं के माध्यम से समकोण पर दो छोटे खंडों को खींचकर और एक ही नस में जारी रखते हुए प्रत्येक चरण में खींचे गए रेखा खंडों की लंबाई को ${\sqrt {2}}$ में विभाजित करके बनाया जा सकता है। इस निर्माण के एक संस्करण को भी परिभाषित किया जा सकता है जिसमें प्रत्येक पुनरावृत्ति की लंबाई को $1/{\sqrt {2}}$ से कम के अनुपात से गुणा किया जाता है, लेकिन इस संस्करण के लिए परिणामी आकृति एक फ्रैक्टल सीमा के साथ इसकी बाउंडिंग आयत के केवल एक भाग को आवृत्त करती है।

एक वैकल्पिक प्रक्रिया जो समान फ्रैक्टल सेट उत्पन्न करती है, जो $1:{\sqrt {2}}$ के अनुपात में पक्षों के साथ तथा एक आयत के साथ प्रारंभ करता है और अधिकांशतः इसे दो छोटे चांदी के आयतों में विभाजित करते हैं, प्रत्येक चरण में दो छोटे आयतों के दो केन्द्रक को एक रेखा खंड से जोड़ते हैं। इसी प्रकार की प्रक्रिया किसी भी अन्य बनावट के आयतों के साथ की जा सकती है, लेकिन $1:{\sqrt {2}}$ आयत प्रत्येक चरण में एक ${\sqrt {2}}$ कारक द्वारा समान रूप से घटते हुए रेखा खंड बनावट की ओर जाता है। जबकि अन्य आयतों के लिए पुनरावर्ती निर्माण के विषम और सम स्तरों पर विभिन्न कारकों द्वारा लंबाई घट जाती है।

गुण

एच ट्री एक स्व-समान फ्रैक्टल है; इसका हॉसडॉर्फ आयाम 2 के समतुल्य है।

एच ट्री के बिंदु अव्यवस्थित रूप से एक आयत में प्रतेक (उपविभाजित आयतों के केन्द्रक द्वारा निर्माण में प्रारंभिक आयत के समान) बिंदु के निकट आते हैं। चूंकि, इसमें आयत के सभी बिंदु सम्मलित नहीं हैं; उदाहरण के लिए, प्रारंभिक रेखा खंड (इस खंड के मध्य बिंदु के अतिरिक्त) के लंबवत द्विभाजक पर बिंदु सम्मलित नहीं हैं।

अनुप्रयोग

बड़े पैमाने पर एकीकरण डिज़ाइन में, एच ट्री को एक पूर्ण बाइनरी ट्री के लेआउट के रूप में उपयोग किया जा सकता है, जो कुल क्षेत्रफल का उपयोग करता है जो ट्री के नोड्स की संख्या के अनुपात में होता है। इसके अतिरिक्त, एच ट्री ग्राफ़ आरेखण में ट्री के लिए एक स्पेस कुशल लेआउट बनाता है, और एक बिंदु सेट निर्माण के भाग के रूप में जिसके लिए यात्रा विक्रेता समस्या के वर्ग किनारे की लंबाई का योग बड़ा है। यह सामान्यतः क्लॉक वितरण नेटवर्क के रूप में उपयोग किया जाता है, चिप के सभी भागों में क्लॉक संकेत को रूट करने के लिए प्रत्येक भाग में समान प्रसार विलंब के साथ, और वीएलएसआई मल्टीप्रोसेसरों के लिए इंटरकनेक्शन नेटवर्क के रूप में भी उपयोग किया गया है।

त्रि-आयामी एच ट्री

समतलीय एच ट्री को एच ट्री समतल की दिशा में लंबवत रेखा खंडों को जोड़कर त्रि-आयामी संरचना के लिए सामान्यीकृत किया जा सकता है। परिणामी त्रि-आयामी एच ट्री में हॉसडॉर्फ आयाम 3 के समतुल्य है। समतलीय एच ट्री और इसके त्रि-आयामी संस्करण को फोटोनिक क्रिस्टल और मेटामैटिरियल्स में कृत्रिम विद्युत चुम्बकीय परमाणुओं का गठन करने के लिए पाया गया है और माइक्रोवेव इंजीनियरिंग में संभावित अनुप्रयोग हो सकते हैं।

संबंधित सेट

एच ट्री की तुलना में तेज कोणों के साथ स्व-अतिव्यापी फ्रैक्टल चंदवा

एच ट्री फ्रैक्टल कैनोपी का एक उदाहरण है, जिसमें निकटतम रेखा खंडों के बीच का कोण निरंतर 180 डिग्री होता है। अपने बाउंडिंग आयत के हर बिंदु के निकट अव्यवस्थित रूप से आने की अपनी संपत्ति में, यह एक स्पेस-फिलिंग वक्र जैसा दिखता है, चूंकि यह स्वयं एक वक्र नहीं है।

सांस्थितिकी रूप से, एक एच ट्री में डेंड्रॉइड के समान गुण होते हैं। चूंकि, वे डेंड्रॉइड नहीं हैं: डेंड्रॉइड संवृत सेट होना चाहिए, और एच ट्री संवृत नहीं हैं (उनका संवृत होना संपूर्ण आयत है)।

एच ट्री के रेखा खंडों के स्थान पर घनीभूत बहुभुज शाखाओं के साथ एक ही ट्री की संरचना की विविधताओं को बेनोइट मंडेलब्रॉट द्वारा परिभाषित किया गया है, और कभी-कभी उन्हें मैंडेलब्रॉट ट्री कहा जाता है। इन विविधताओं में, ट्री की पत्तियों और उनकी मोटी शाखाओं के बीच ${\sqrt {2}}$ से थोड़ा अधिक होना चाहिए तथा ओवरलैप से बचने के लिए, माप कारक जिसके द्वारा प्रत्येक स्तर पर बनावट को कम किया जाता है।

संदर्भ

• Bern, Marshall; Eppstein, David (1993), "Worst-case bounds for subadditive geometric graphs", Proc. 9th Annual Symposium on Computational Geometry (PDF), Association for Computing Machinery, pp. 183–188, doi:10.1145/160985.161018, S2CID 14158914.
• Browning, Sally A. (1980), The Tree Machine: A Highly Concurrent Computing Environment, Ph.D. thesis, California Institute of Technology.
• 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, S2CID 60985695.
• Hou, Bo; Xie, Hang; Wen, Weijia; Sheng, Ping (2008), "Three-dimensional metallic fractals and their photonic crystal characteristics" (PDF), Physical Review B, 77 (12): 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, S2CID 253737197.
• Lauwerier, Hans (1991), Fractals: Endlessly Repeated Geometrical Figures, Princeton Science Library, vol. 6, translated by Gill-Hoffstadt, Sophia, Princeton University Press, ISBN 9780691024455
• 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, S2CID 15532332.
• 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, S2CID 22192509.
• 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" (PDF), Physical Review Letters, 89 (22): 223901, doi:10.1103/PhysRevLett.89.223901, PMID 12485068.