binary-tree - extended - complete binary tree



बाइनरी पेड़ और बाइनरी खोज पेड़ के बीच अंतर (8)

एक बाइनरी खोज पेड़ में, सभी नोड्स को एक विशिष्ट क्रम में व्यवस्थित किया जाता है - रूट नोड के बाईं ओर नोड्स के रूट की तुलना में एक छोटा मान होता है, और नोड के दाईं ओर के सभी नोड्स के मूल्य के मान से अधिक मूल्य होते हैं जड़।

https://ffff65535.com

क्या कोई उदाहरण के साथ बाइनरी पेड़ और बाइनरी खोज पेड़ के बीच अंतर को समझा सकता है?


एक बाइनरी पेड़ एक पेड़ है जिसका बच्चा दो से अधिक नहीं होता है। एक बाइनरी सर्च पेड़ इनवेरिएंट का पालन करता है कि बाएं बच्चे को रूट नोड की कुंजी से छोटा मान होना चाहिए, जबकि सही बच्चे को रूट नोड की कुंजी से अधिक मूल्य होना चाहिए।


जैसा कि उपर्युक्त सभी ने बाइनरी पेड़ और बाइनरी सर्च पेड़ के बीच के अंतर के बारे में बताया है, मैं सिर्फ यह जांच कर रहा हूं कि दिए गए बाइनरी पेड़ बाइनरी सर्च पेड़ है या नहीं।

boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max)
{

    if(node == null)
    {
        return true;
    }

    boolean left = isBinarySearchTree(node.getLeft(), min, node.getValue());
    boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

    return left && right && (node.getValue()<max) && (node.getValue()>=min);

}

आशा है इससे आपकी मदद होगी। क्षमा करें अगर मैं इस विषय से अलग हो रहा हूं क्योंकि मुझे लगा कि यह यहां उल्लेख करने लायक है।


बाइनरी पेड़: पेड़ जहां प्रत्येक नोड दो पत्तियों तक है

  1
 / \
2   3

बाइनरी खोज पेड़: खोज के लिए प्रयुक्त। एक बाइनरी पेड़ जहां बाएं बच्चे में केवल नोड्स होते हैं जो पैरेंट नोड से कम मूल्यों के साथ होते हैं, और जहां सही बच्चे में केवल माता-पिता के बराबर या उसके बराबर मान वाले नोड होते हैं।

  2
 / \
1   3

बाघ की जांच करने के लिए या दिए गए बाइनरी ट्री नहीं है बाइनरी सर्च ट्री यहां एक वैकल्पिक दृष्टिकोण है।

ट्रैक्टर ट्री इन इनऑर्डर फैशन (यानी वाम चाइल्ड -> अभिभावक -> राइट चाइल्ड), अस्थायी रूप से स्टोर ट्रैवर्स नोड डेटा अस्थायी रूप से अस्थायी रूप से स्टोर करने से पहले, अस्थायी वर्तमान नोड का डेटा पिछले एक या अधिक नहीं है । फिर बस इसे तोड़ दो, पेड़ बाइनरी सर्च ट्री नहीं है और अंत तक आगे बढ़ता है।

जावा के साथ नीचे एक उदाहरण है:

public static boolean isBinarySearchTree(Tree root)
{
    if(root==null)
        return false;

    isBinarySearchTree(root.left);
    if(tree.data<temp)
        return false;
    else
        temp=tree.data;
    isBinarySearchTree(root.right);
    return true;
}

बाहर अस्थायी चर रखरखाव


बाइनरी ट्री पेड़ का एक विशेष रूप है जिसमें दो बच्चे (बाएं बच्चे और दाएं बच्चे) हैं। यह वृक्ष संरचना में डेटा का प्रतिनिधित्व करता है

बाइनरी सर्च ट्री (बीएसटी) एक विशेष प्रकार का बाइनरी ट्री है जो निम्न स्थितियों का पालन करता है:

  1. बाएं बाल नोड अपने माता-पिता नोड से छोटा है
  2. दायां बच्चा नोड अपने माता-पिता नोड से बड़ा है

बाइनरी ट्री एक डेटा संरचना के लिए खड़ा है जो नोड्स से बना है जिसमें केवल दो बच्चों के संदर्भ हो सकते हैं।

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

इस प्रकार, सभी बीएसटी बाइनरी ट्री हैं हालांकि केवल कुछ बाइनरी ट्री भी बीएसटी हो सकते हैं। सूचित करें कि बीएसटी बाइनरी ट्री का सबसेट है।

तो, बाइनरी ट्री बाइनरी सर्च ट्री की तुलना में एक सामान्य डेटा-स्ट्रक्चर का अधिक है। और आपको यह भी सूचित करना होगा कि बाइनरी सर्च ट्री एक सॉर्टेड पेड़ है जबकि सामान्य बाइनरी ट्री के लिए नियमों का ऐसा कोई सेट नहीं है।

बाइनरी ट्री

एक Binary Tree जो BST नहीं है;

         5
       /   \
      /     \
     9       2
    / \     / \
  15   17  19  21

बाइनरी सर्च ट्री (सॉर्टेड ट्री)

एक बाइनरी सर्च ट्री जो बाइनरी ट्री भी है;

         50
       /    \
      /      \
     25      75
    /  \    /  \
  20    30 70   80

बाइनरी सर्च ट्री नोड संपत्ति

यह भी सूचित करें कि बीएसटी में किसी भी माता-पिता नोड के लिए;

  • सभी बाएं नोड्स में पैरेंट नोड के मान से छोटे मान होते हैं। ऊपरी उदाहरण में, मूल्यों के साथ नोड्स {20, 25, 30} जो 50 के बाएं ( बाएं वंशज ) पर स्थित हैं, 50 से छोटे हैं।

  • सभी सही नोड्स के पास पैरेंट नोड के मान से अधिक मूल्य होता है। ऊपरी उदाहरण में, मूल्यों के साथ नोड्स {70, 75, 80} जो 50 के दाएं ( दाएं वंशज ) पर स्थित हैं, 50 से अधिक हैं।

बाइनरी ट्री नोड के लिए ऐसा कोई नियम नहीं है। बाइनरी ट्री नोड के लिए एकमात्र नियम में दो बच्चे हैं, इसलिए यह स्वयं को समझाता है कि बाइनरी क्यों कहा जाता है।


बाइनरी पेड़

बाइनरी पेड़ कुछ भी हो सकता है जिसमें 2 बच्चे और 1 माता-पिता हों। इसे लिंक की गई सूची या सरणी के रूप में या आपके कस्टम एपीआई के साथ कार्यान्वित किया जा सकता है। एक बार जब आप इसमें अधिक विशिष्ट नियम जोड़ना शुरू कर देते हैं, तो यह अधिक विशिष्ट पेड़ बन जाता है। सबसे आम ज्ञात कार्यान्वयन यह है कि, दाईं ओर बाएं और बड़े वाले छोटे नोड्स जोड़ें।

उदाहरण के लिए, आकार 9 और ऊंचाई 3 का एक लेबल वाला बाइनरी पेड़, रूट नोड के साथ जिसका मूल्य 2 है। पेड़ असंतुलित है और क्रमबद्ध नहीं हैhttps://en.wikipedia.org/wiki/Binary_tree

उदाहरण के लिए, बाईं ओर के पेड़ में, ए में 6 बच्चे {बी, सी, डी, ई, एफ, जी} हैं। इसे दाईं ओर बाइनरी पेड़ में परिवर्तित किया जा सकता है।

द्विआधारी खोज

बाइनरी सर्च तकनीक / एल्गोरिदम है जिसका उपयोग नोड चेन पर विशिष्ट आइटम खोजने के लिए किया जाता है। क्रमबद्ध सरणी पर बाइनरी खोज काम करता है

बाइनरी खोज लक्ष्य मान को सरणी के मध्य तत्व से तुलना करती है; यदि वे असमान हैं, तो आधे जिसमें लक्ष्य झूठ नहीं बोल सकता है समाप्त हो गया है और खोज शेष होने तक शेष छमाही तक जारी है या शेष आधा खाली है। https://en.wikipedia.org/wiki/Binary_search_algorithm

बाइनरी खोज का प्रतिनिधित्व करने वाला एक पेड़। यहां खोजा जा रहा सरणी [20, 30, 40, 50, 9 0, 100] है, और लक्ष्य मूल्य 40 है।

बाइनरी खोज पेड़

यह बाइनरी पेड़ के कार्यान्वयन में से एक है। यह खोज के लिए विशिष्ट है।

बाइनरी सर्च पेड़ और बी-पेड़ डेटा स्ट्रक्चर बाइनरी सर्च पर आधारित हैं।

बाइनरी सर्च पेड़ (बीएसटी), जिसे कभी-कभी ऑर्डर या सॉर्टेड बाइनरी पेड़ कहा जाता है, एक विशेष प्रकार का कंटेनर होता है : डेटा संरचनाएं जो "आइटम" (जैसे संख्याएं, नाम इत्यादि) को स्मृति में संग्रहीत करती हैं। https://en.wikipedia.org/wiki/Binary_search_tree

रूट 9 पर 8 के साथ आकार 9 और गहराई 3 का एक बाइनरी खोज पेड़। पत्तियों को खींचा नहीं जाता है।

और अंततः प्रसिद्ध डेटा-संरचनाओं और एल्गोरिदम की प्रदर्शन तुलना के लिए महान स्कीमा लागू:

एल्गोरिदम से लिया गया चित्र (चौथा संस्करण)