पायथन प्रोग्राम: बाइनरी सर्च ट्री में सबसे छोटे और सबसे बड़े तत्वों को खोजना

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

उदाहरण

class BST_Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None

    def insert_elem(self, node):
        if self.key > node.key:
            if self.left is None:
                self.left = node
                node.parent = self
            else:
                self.left.insert_elem(node)
        elif self.key < node.key:
            if self.right is None:
                self.right = node
                node.parent = self
            else:
                self.right.insert_elem(node)

    def search_node(self, key):
        if self.key > key:
            if self.left is not None:
                return self.left.search_node(key)
            else:
                return None
        elif self.key < key:
            if self.right is not None:
                return self.right.search_node(key)
            else:
                return None
        return self

class BSTree:
    def __init__(self):
        self.root = None

    def add_elem(self, key):
        new_node = BST_Node(key)
        if self.root is None:
            self.root = new_node
        else:
            self.root.insert_elem(new_node)

    def search_node(self, key):
        if self.root is not None:
            return self.root.search_node(key)

    def get_smallest_elem(self):
        if self.root is not None:
            current = self.root
            while current.left is not None:
                current = current.left
            return current.key

    def get_largest_elem(self):
        if self.root is not None:
            current = self.root
            while current.right is not None:
                current = current.right
            return current.key

my_instance = BSTree()
print('मेनू (मान लें कोई डुप्लिकेट कुंजी नहीं)')
print('add ')
print('smallest')
print('largest')
print('quit')

while True:
    my_input = input('आप कौन सा ऑपरेशन करेंगे? ').split()
    operation = my_input[0].strip().lower()
    if operation == 'add':
        key = int(my_input[1])
        my_instance.add_elem(key)
    if operation == 'smallest':
        smallest = my_instance.get_smallest_elem()
        print('सबसे छोटा तत्व है: {}'.format(smallest))
    if operation == 'largest':
        largest = my_instance.get_largest_elem()
        print('सबसे बड़ा तत्व है: {}'.format(largest))
    elif operation == 'quit':
        break

आउटपुट

मेनू (मान लें कोई डुप्लिकेट कुंजी नहीं)
add <key>
smallest
largest
quit
आप कौन सा ऑपरेशन करेंगे? add 5
आप कौन सा ऑपरेशन करेंगे? add 8
आप कौन सा ऑपरेशन करेंगे? add 11
आप कौन सा ऑपरेशन करेंगे? add 0
आप कौन सा ऑपरेशन करेंगे? add 3
आप कौन सा ऑपरेशन करेंगे? smallest
सबसे छोटा तत्व है: 0
आप कौन सा ऑपरेशन करेंगे? largest
सबसे बड़ा तत्व है: 11
आप कौन सा ऑपरेशन करेंगे? quit

व्याख्या

• आवश्यक विशेषताओं के साथ 'BST_Node' क्लास बनाई गई है।

• इसमें एक 'init' फ़ंक्शन है जो बाएं, दाएं और पैरेंट नोड्स को 'None' पर सेट करता है।

• इसमें एक 'insert_element' मेथड है जो बाइनरी ट्री में तत्व डालने में मदद करता है।

• 'search_node' नामक एक अन्य मेथड ट्री में एक विशिष्ट नोड खोजता है।

• 'BSTree' नामक एक अन्य क्लास परिभाषित की गई है, जहां रूट को 'None' पर सेट किया गया है।

• 'add_elem' नामक एक मेथड ट्री में तत्व जोड़ने के लिए परिभाषित की गई है।

• 'search_node' नामक एक अन्य मेथड ट्री में एक विशिष्ट नोड खोजने में मदद करता है।

• 'get_smallest_node' नामक एक अन्य मेथड ट्री में सबसे छोटा नोड प्राप्त करने में मदद करता है।

• 'get_largest_node' नामक एक अन्य मेथड ट्री में सबसे बड़ा नोड प्राप्त करने में मदद करता है।

• 'BSTree' क्लास का एक ऑब्जेक्ट बनाया जाता है।

• उपयोगकर्ता द्वारा चुने गए ऑपरेशन के आधार पर, ऑपरेशन किया जाता है।

बाइनरी सर्च ट्री गुण

• बाएं उपट्री के सभी नोड्स की कुंजी रूट की कुंजी से कम होती है

• दाएं उपट्री के सभी नोड्स की कुंजी रूट की कुंजी से अधिक होती है

• बाएं और दाएं उपट्री भी बाइनरी सर्च ट्री होते हैं

• कोई डुप्लिकेट कुंजी नहीं (इस कार्यान्वयन में)

सबसे छोटा/सबसे बड़ा तत्व खोजने का तर्क

• सबसे छोटा: रूट से शुरू करें और तब तक बाएं जाएं जब तक कोई बायां बच्चा न हो

• सबसे बड़ा: रूट से शुरू करें और तब तक दाएं जाएं जब तक कोई दायां बच्चा न हो

• समय जटिलता: O(h) जहां h ट्री की ऊंचाई है (संतुलित ट्री के लिए O(log n), असंतुलित के लिए O(n))

अतिरिक्त उपयोगी मेथड्स

def get_height(self):
    return self._height_helper(self.root)

def _height_helper(self, node):
    if node is None:
        return -1
    return 1 + max(self._height_helper(node.left), self._height_helper(node.right))

def inorder_traversal(self):
    result = []
    self._inorder_helper(self.root, result)
    return result

def _inorder_helper(self, node, result):
    if node:
        self._inorder_helper(node.left, result)
        result.append(node.key)
        self._inorder_helper(node.right, result)