Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> प्रोग्रामिंग

डेटा संरचना में भार-पक्षपाती वामपंथी पेड़


यहाँ हम वामपंथी वृक्ष का एक और रूप देखेंगे। यहां हम एक सबट्री में नोड्स की संख्या पर विचार करेंगे, न कि रूट टू एक्सटर्नल नोड के लिए सबसे छोटे पथ की लंबाई के बजाय। यहां हम नोड x के वजन w(x) को परिभाषित करेंगे, जो रूट x के साथ उपट्री में आंतरिक नोड्स की संख्या होगी। यदि x एक बाहरी नोड है, तो भार 0 है। यदि x आंतरिक नोड है, तो भार उसके बच्चों के भार के योग से एक अधिक है।

वजन पक्षपाती वामपंथी पेड़ (WBLT) का एक उदाहरण यहां दिया गया है -

मान लीजिए बाइनरी ट्री इस तरह है -

डेटा संरचना में भार-पक्षपाती वामपंथी पेड़

यदि हम प्रत्येक नोड के लिए w(x) मानों की गणना करते हैं, तो यह इस तरह होगा -

डेटा संरचना में भार-पक्षपाती वामपंथी पेड़

अब WBLT की परिभाषा इस प्रकार है -

एक बाइनरी ट्री को वेट बैलेंस्ड लेफ्टिस्ट ट्री कहा जाता है, यदि और केवल तभी, प्रत्येक आंतरिक नोड पर बाएं बच्चे का w(x) दाएं बच्चे के w(x) से अधिक या उसके बराबर हो। अधिकतम (न्यूनतम) WBLT एक अधिकतम (न्यूनतम) वृक्ष है जो एक WBLT भी है।


  1. डेटा संरचना में बाइनरी ट्री एडीटी

    मूल अवधारणा एक बाइनरी ट्री को एक ऐसे पेड़ के रूप में परिभाषित किया जाता है जिसमें किसी भी नोड में दो से अधिक बच्चे नहीं हो सकते। किसी भी नोड की उच्चतम डिग्री दो होती है। यह इंगित करता है कि बाइनरी ट्री की डिग्री या तो शून्य या एक या दो होती है। उपरोक्त अंजीर में, बाइनरी ट्री में एक जड़ और दो उप

  1. डेटा संरचना में बसपा पेड़

    कंप्यूटर विज्ञान में, बाइनरी स्पेस पार्टीशनिंग (बीएसपी) के रूप में जाना जाने वाला एक तरीका हाइपरप्लेन को विभाजन के रूप में लागू करके एक स्थान को दो उत्तल सेटों में पुनरावर्ती रूप से उप-विभाजित करने के लिए लागू किया जाता है। उप-विभाजन की यह प्रक्रिया एक पेड़ डेटा संरचना के रूप में क्षेत्र के भीतर वस्

  1. डेटा संरचना में पेड़ों की श्रेणी

    एक श्रेणी ट्री को बिंदुओं की सूची रखने के लिए एक आदेशित ट्री डेटा संरचना के रूप में परिभाषित किया गया है। यह किसी दी गई सीमा के भीतर सभी बिंदुओं को कुशलता से पुनर्प्राप्त करने की अनुमति देता है, और आमतौर पर दो या उच्च आयामों में लागू किया जाता है। O(logd . के तेज़ क्वेरी समय को छोड़कर यह kd-tree के