algorithm
बाइनरी सर्च ट्रीज़

परिचय

बाइनरी सर्च ट्री - सम्मिलन (पायथन)

यह पायथन का उपयोग करके बाइनरी सर्च ट्री इंसर्शन का एक सरल कार्यान्वयन है।

एक उदाहरण नीचे दिया गया है:

कोड स्निपेट के बाद प्रत्येक छवि निष्पादन दृश्य दिखाती है जो यह कल्पना करना आसान बनाता है कि यह कोड कैसे काम करता है।

class Node:
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.data = val

def insert(root, node):
    if root is None:
        root = node
    else:
        if root.data > node.data:
            if root.l_child is None:
                root.l_child = node
            else:
                insert(root.l_child, node)
        else:
            if root.r_child is None:
                root.r_child = node
            else:
                insert(root.r_child, node)

def in_order_print(root):
    if not root:
        return
    in_order_print(root.l_child)
    print root.data
    in_order_print(root.r_child)

def pre_order_print(root):
    if not root:
        return        
    print root.data
    pre_order_print(root.l_child)
    pre_order_print(root.r_child)    

बाइनरी सर्च ट्री - विलोपन (C ++)

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

अपनी बाइनरी सर्च ट्री प्रॉपर्टी को बनाए रखते हुए एक पेड़ में एक नोड को हटाना ।

नोड को हटाते समय तीन मामलों पर विचार किया जाना है।

• केस 1: डिलीट किया जाने वाला नोड लीफ नोड है। (मूल्य 22 के साथ नोड)।
• केस 2: हटाए जाने वाले नोड में एक बच्चा है। (मूल्य 26 के साथ नोड)।
• केस 3: हटाए जाने वाले नोड में दोनों बच्चे हैं। (मूल्य 49 के साथ नोड)।

मामलों की व्याख्या:

1. जब हटाए जाने वाला नोड पत्ती नोड होता है, तो बस नोड को हटा दें और nullptr को उसके मूल नोड में पास करें।
2. जब हटाए जाने वाले नोड में केवल एक बच्चा होता है, तो बच्चे के मूल्य को नोड मूल्य पर कॉपी करें और बच्चे को हटा दें (मामले में परिवर्तित) 1
3. जब एक नोड को हटाने के लिए दो चिल्ड होते हैं तो उसके दाहिने उप पेड़ से न्यूनतम नोड को कॉपी किया जा सकता है और फिर नोड के सही सबट्री से परिवर्तित किया जा सकता है (केस 2 में परिवर्तित)

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

एक पेड़ में एक नोड की संरचना और विलोपन के लिए कोड:

struct node
{
    int data;
    node *left, *right;
};

node* delete_node(node *root, int data)
{
  if(root == nullptr) return root;
  else if(data < root->data) root->left  = delete_node(root->left, data);
  else if(data > root->data) root->right = delete_node(root->right, data);

  else
  {
    if(root->left == nullptr && root->right == nullptr) // Case 1
    {
      free(root);
      root = nullptr;
    }
    else if(root->left == nullptr)       // Case 2
    {
       node* temp = root;
       root= root->right;
       free(temp);
    }
    else if(root->right == nullptr)      // Case 2
    {
       node* temp = root;
       root = root->left;
       free(temp);
    }
    else                                 // Case 3
    {
       node* temp = root->right;

       while(temp->left != nullptr) temp = temp->left;

       root->data = temp->data;
       root->right = delete_node(root->right, temp->data);
    }
  }
  return root;
}

उपरोक्त कोड की समय जटिलता ओ ( एच ) है, जहां एच पेड़ की ऊंचाई है।

एक BST में सबसे कम सामान्य पूर्वज

BST पर विचार करें:

22 और 26 का सबसे कम सामान्य पूर्वज 24 है

26 और 49 का न्यूनतम सामान्य पूर्वज 46 है

22 और 24 का सबसे कम सामान्य पूर्वज 24 है

बाइनरी सर्च ट्री प्रॉपर्टी का इस्तेमाल नोड्स सबसे कम पूर्वजों को खोजने के लिए किया जा सकता है

Psuedo कोड:

lowestCommonAncestor(root,node1, node2){

if(root == NULL)    
return NULL;



 else if(node1->data == root->data || node2->data== root->data)    
    return root;
    
    else if((node1->data <= root->data && node2->data > root->data)
              || (node2->data <= root->data && node1->data > root->data)){
        
             return root;
    }
    
    else if(root->data > max(node1->data,node2->data)){
            return lowestCommonAncestor(root->left, node1, node2);
    }
        
        else {
            return lowestCommonAncestor(root->right, node1, node2);
      }
        }

बाइनरी सर्च ट्री - पायथन

class Node(object):
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.val = val


class BinarySearchTree(object):
    def insert(self, root, node):
        if root is None:
            return node

        if root.val < node.val:
            root.r_child = self.insert(root.r_child, node)
        else:
            root.l_child = self.insert(root.l_child, node)

        return root


    def in_order_place(self, root):
        if not root:
            return None
        else:
            self.in_order_place(root.l_child)
            print root.val
            self.in_order_place(root.r_child)

    def pre_order_place(self, root):
        if not root:
            return None
        else:
            print root.val
            self.pre_order_place(root.l_child)
            self.pre_order_place(root.r_child)

    def post_order_place(self, root):
        if not root:
            return None
        else:
            self.post_order_place(root.l_child)
            self.post_order_place(root.r_child)
            print root.val

"" "अलग नोड बनाएँ और उसमें डेटा डालें" ""

r = Node(3)
node = BinarySearchTree()
nodeList = [1, 8, 5, 12, 14, 6, 15, 7, 16, 8]

for nd in nodeList:
    node.insert(r, Node(nd))

print "------In order ---------"
print (node.in_order_place(r))
print "------Pre order ---------"
print (node.pre_order_place(r))
print "------Post order ---------"
print (node.post_order_place(r))