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

डेटा संरचना में वजन-पक्षपाती लेफ्टिस्ट ट्री (Weight-Biased Leftist Trees)


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

वेट बायस्ड लेफ्टिस्ट ट्री (WBLT) का एक उदाहरण:

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

डेटा संरचना में वजन-पक्षपाती लेफ्टिस्ट ट्री (Weight-Biased Leftist Trees)

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

डेटा संरचना में वजन-पक्षपाती लेफ्टिस्ट ट्री (Weight-Biased Leftist Trees)

अब WBLT की परिभाषा इस तरह है:

एक बाइनरी ट्री को वेट बैलेंस्ड लेफ्टिस्ट ट्री (Weight Balanced Leftist Tree) कहा जाता है यदि और केवल यदि, प्रत्येक आंतरिक नोड पर बाएं बच्चे का w(x) दाएं बच्चे के w(x) से बड़ा या बराबर होता है। एक मैक्स (मिन) WBLT एक मैक्स (मिन) ट्री है जो WBLT भी है।


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

    मूल अवधारणा (Basic Concept) बाइनरी ट्री को एक ऐसे ट्री के रूप में परिभाषित किया जाता है जिसमें कोई भी नोड दो से अधिक बच्चे (Children) नहीं रख सकता। किसी भी नोड की उच्चतम डिग्री (Degree) दो होती है। इसका अर्थ है कि बाइनरी ट्री की डिग्री शून्य, एक या दो हो सकती है। उपरोक्त आकृति में, बाइनरी ट्री मे

  1. डेटा स्ट्रक्चर में BSP ट्रीज़ डेटा स्ट्रक्चर में BSP ट्रीज़

    कंप्यूटर साइंस में, बाइनरी स्पेस पार्टीशनिंग (BSP) नामक एक विधि को हाइपरप्लेन्स (Hyperplanes) को पार्टीशन के रूप में लागू करके एक स्पेस को दो कन्वेक्स सेट्स (Convex Sets) में पुनरावर्ती रूप से उप-विभाजित (Recursively Subdividing) करने के लिए लागू किया जाता है। उप-विभाजन की यह प्रक्रिया क्षेत्र में व

  1. डेटा स्ट्रक्चर में रेंज ट्रीज़ डेटा स्ट्रक्चर में रेंज ट्रीज़

    रेंज ट्री (Range Tree) को बिंदुओं की सूची रखने के लिए एक क्रमबद्ध ट्री डेटा स्ट्रक्चर (Ordered Tree Data Structure) के रूप में परिभाषित किया जाता है। यह दिए गए रेंज के भीतर सभी बिंदुओं को कुशलतापूर्वक पुनः प्राप्त करने की अनुमति देता है, और आमतौर पर दो या अधिक आयामों में लागू किया जाता है। यह kd-ट्र