इस ट्यूटोरियल में, आप सीखेंगे कि बाइनरी सर्च ट्री कैसे काम करता है। इसके अलावा, आप सी, सी ++, जावा और पायथन में बाइनरी सर्च ट्री के काम करने के उदाहरण पाएंगे।
बाइनरी सर्च ट्री एक डेटा संरचना है जो हमें संख्याओं की क्रमबद्ध सूची को बनाए रखने की अनुमति देता है।
- इसे बाइनरी ट्री कहा जाता है क्योंकि प्रत्येक ट्री नोड में अधिकतम दो बच्चे होते हैं।
- इसे एक खोज वृक्ष कहा जाता है क्योंकि इसका उपयोग
O(log(n))समय में किसी संख्या की उपस्थिति के लिए खोज करने के लिए किया जा सकता है ।
गुण जो एक बाइनरी खोज ट्री को एक नियमित बाइनरी ट्री से अलग करते हैं
- बायीं सबट्री के सभी नोड रूट नोड से कम हैं
- राइट सबट्री के सभी नोड रूट नोड से अधिक हैं
- प्रत्येक नोड के दोनों उपप्रकार भी बीएसटी हैं अर्थात उनके पास उपरोक्त दो गुण हैं
जड़ से छोटे एक मूल्य के साथ एक सही सबट्री वाले पेड़ को यह दिखाने के लिए दिखाया जाता है कि यह वैध बाइनरी सर्च ट्री नहीं है
दायीं ओर बाइनरी ट्री एक बाइनरी सर्च ट्री नहीं है क्योंकि नोड "3" के दायें सबट्री में मान इससे छोटा होता है।
दो बुनियादी ऑपरेशन हैं जो आप बाइनरी सर्च ट्री पर कर सकते हैं:
सर्च ऑपरेशन
एल्गोरिथ्म BST की संपत्ति पर निर्भर करता है कि यदि प्रत्येक बायीं सबट्री में रूट के नीचे मान हैं और प्रत्येक राइट सबट्री में रूट के ऊपर मान हैं।
यदि मान जड़ से नीचे है, तो हम यह सुनिश्चित करने के लिए कह सकते हैं कि मूल्य सही उपप्रकार में नहीं है; हमें केवल बाएं सबट्री में खोज करने की आवश्यकता है और यदि मान रूट से ऊपर है, तो हम यह सुनिश्चित कर सकते हैं कि मान बाईं सबट्री में नहीं है; हमें केवल सही उपशीर्षक में खोज करने की आवश्यकता है।
कलन विधि:
If root == NULL return NULL; If number == root->data return root->data; If number data return search(root->left) If number> root->data return search(root->right)
आइए हम इसे एक आरेख के साथ कल्पना करने का प्रयास करें।
4 ऐसा नहीं पाया गया है, 8 
4 के बाएं उपप्रकार के माध्यम से पार पाया नहीं गया है, इसलिए 3 
4 के दाईं उपप्रकार के माध्यम से पार पाया नहीं जाता है, 6 4 के बाएं उपशीर्षक के माध्यम से पार पाया जाता है
यदि मान पाया जाता है, तो हम मान लौटाते हैं ताकि यह प्रत्येक पुनरावृत्ति चरण में प्रचारित हो जाए जैसा कि नीचे की छवि में दिखाया गया है।
यदि आपने देखा होगा, तो हमने चार बार रिटर्न सर्च (स्ट्रक्चर नोड *) कहा है। जब हम या तो नया नोड या NULL वापस करते हैं, तो मान बार-बार वापस आता है जब तक कि खोज (रूट) अंतिम परिणाम नहीं देता।
यदि मूल्य किसी भी उपप्रकार में पाया जाता है, तो इसे प्रचारित किया जाता है ताकि अंत में इसे वापस कर दिया जाए, अन्यथा अशक्त वापस आ गया है
यदि मान नहीं मिला है, तो हम अंततः पत्ती नोड के बाएं या दाएं बच्चे तक पहुंचते हैं जो कि NULL है और यह प्रचारित और वापस हो जाता है।
ऑपरेशन डालें
सही स्थिति में एक मूल्य सम्मिलित करना खोज के समान है क्योंकि हम इस नियम को बनाए रखने की कोशिश करते हैं कि बाएं सबट्री रूट से कम है और राइट सबट्री रूट से बड़ा है।
हम मूल्य के आधार पर या तो राइट सबट्री या लेफ्ट सबट्री जाते रहते हैं और जब हम किसी पॉइंट पर लेफ्ट या राइट सबट्री शून्य तक पहुंचते हैं, तो हम वहां नया नोड डालते हैं।
कलन विधि:
If node == NULL return createNode(data) if (data data) node->left = insert(node->left, data); else if (data> node->data) node->right = insert(node->right, data); return node;
एल्गोरिथ्म उतना सरल नहीं है जितना दिखता है। आइए कल्पना करने की कोशिश करें कि हम मौजूदा बीएसटी में एक संख्या कैसे जोड़ते हैं।
4 <8 इसलिए, 8 
4> 3 के बाएं बच्चे के माध्यम से अनुप्रस्थ करें, 8 
4 <6 के दाहिने बच्चे के माध्यम से अनुप्रस्थ करें, 6 के बाएं बच्चे के माध्यम से अनुप्रस्थ 
करें 6 के बाएं बच्चे के रूप में 4 डालें
हमने नोड को संलग्न किया है लेकिन हमें अभी भी बाकी पेड़ को कोई नुकसान पहुंचाए बिना कार्य से बाहर निकलना है। यह वह जगह है जहाँ return node;अंत में काम आता है। के मामले में NULL, नए बनाए गए नोड को वापस लौटाया जाता है और मूल नोड से जोड़ा जाता है, अन्यथा उसी नोड को बिना किसी परिवर्तन के लौटा दिया जाता है जब तक हम जड़ तक वापस नहीं जाते।
इससे यह सुनिश्चित हो जाता है कि जैसे-जैसे हम पेड़ को आगे बढ़ाएंगे, दूसरे नोड कनेक्शन नहीं बदले जाएंगे।
छवि को मूल तत्व के अंत में लौटने का महत्व दिखाते हैं ताकि तत्व ऊपर की ओर पुनरावृत्ति चरण के दौरान अपनी स्थिति न खोएं।
विलोपन ऑपरेशन
बाइनरी सर्च ट्री से एक नोड को हटाने के लिए तीन मामले हैं।
केस I
पहले मामले में, हटाए जाने वाला नोड लीफ नोड है। ऐसे मामले में, बस पेड़ से नोड को हटा दें।
4 को 
हटाना है नोड को हटाएं
केस II
दूसरे मामले में, हटाए गए झूठ के नोड में एक ही बच्चा नोड होता है। ऐसे मामले में नीचे दिए गए चरणों का पालन करें:
- उस नोड को उसके बच्चे के नोड से बदलें।
- बच्चे के नोड को उसकी मूल स्थिति से हटा दें।
6 को 
अपने बच्चे के मूल्य को नोड में कॉपी करना है और बच्चे को 
अंतिम पेड़ को हटाना है
केस III
तीसरे मामले में, हटाए जाने वाले नोड में दो बच्चे हैं। ऐसे मामले में नीचे दिए गए चरणों का पालन करें:
- उस नोड का इनवर्टर उत्तराधिकारी प्राप्त करें।
- नोड को इनवर्टर उत्तराधिकारी से बदलें।
- इनवर्टर उत्तराधिकारी को उसकी मूल स्थिति से निकालें।
3 को डिलीट करना है इनवर्टर उत्तराधिकारी के मान को कॉपी करें (4) नोड 
को इनवर्टर उत्तराधिकारी को हटाएं
पायथन, जावा और सी / सी ++ उदाहरण
पायथन जावा सी सी ++ # Binary Search Tree operations in Python # Create a node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Inorder traversal def inorder(root): if root is not None: # Traverse left inorder(root.left) # Traverse root print(str(root.key) + "->", end=' ') # Traverse right inorder(root.right) # Insert a node def insert(node, key): # Return a new node if the tree is empty if node is None: return Node(key) # Traverse to the right place and insert the node if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) return node # Find the inorder successor def minValueNode(node): current = node # Find the leftmost leaf while(current.left is not None): current = current.left return current # Deleting a node def deleteNode(root, key): # Return if the tree is empty if root is None: return root # Find the node to be deleted if key root.key): root.right = deleteNode(root.right, key) else: # If the node is with only one child or no child if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp # If the node has two children, # place the inorder successor in position of the node to be deleted temp = minValueNode(root.right) root.key = temp.key # Delete the inorder successor root.right = deleteNode(root.right, temp.key) return root root = None root = insert(root, 8) root = insert(root, 3) root = insert(root, 1) root = insert(root, 6) root = insert(root, 7) root = insert(root, 10) root = insert(root, 14) root = insert(root, 4) print("Inorder traversal: ", end=' ') inorder(root) print("Delete 10") root = deleteNode(root, 10) print("Inorder traversal: ", end=' ') inorder(root)
// Binary Search Tree operations in Java class BinarySearchTree ( class Node ( int key; Node left, right; public Node(int item) ( key = item; left = right = null; ) ) Node root; BinarySearchTree() ( root = null; ) void insert(int key) ( root = insertKey(root, key); ) // Insert key in the tree Node insertKey(Node root, int key) ( // Return a new node if the tree is empty if (root == null) ( root = new Node(key); return root; ) // Traverse to the right place and insert the node if (key root.key) root.right = insertKey(root.right, key); return root; ) void inorder() ( inorderRec(root); ) // Inorder Traversal void inorderRec(Node root) ( if (root != null) ( inorderRec(root.left); System.out.print(root.key + " -> "); inorderRec(root.right); ) ) void deleteKey(int key) ( root = deleteRec(root, key); ) Node deleteRec(Node root, int key) ( // Return if the tree is empty if (root == null) return root; // Find the node to be deleted if (key root.key) root.right = deleteRec(root.right, key); else ( // If the node is with only one child or no child if (root.left == null) return root.right; else if (root.right == null) return root.left; // If the node has two children // Place the inorder successor in position of the node to be deleted root.key = minValue(root.right); // Delete the inorder successor root.right = deleteRec(root.right, root.key); ) return root; ) // Find the inorder successor int minValue(Node root) ( int minv = root.key; while (root.left != null) ( minv = root.left.key; root = root.left; ) return minv; ) // Driver Program to test above functions public static void main(String() args) ( BinarySearchTree tree = new BinarySearchTree(); tree.insert(8); tree.insert(3); tree.insert(1); tree.insert(6); tree.insert(7); tree.insert(10); tree.insert(14); tree.insert(4); System.out.print("Inorder traversal: "); tree.inorder(); System.out.println("After deleting 10"); tree.deleteKey(10); System.out.print("Inorder traversal: "); tree.inorder(); ) )
// Binary Search Tree operations in C #include #include struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root printf("%d -> ", root->key); // Traverse right inorder(root->right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); printf("Inorder traversal: "); inorder(root); printf("After deleting 10"); root = deleteNode(root, 10); printf("Inorder traversal: "); inorder(root); )
// Binary Search Tree operations in C++ #include using namespace std; struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root cout right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); cout << "Inorder traversal: "; inorder(root); cout << "After deleting 10"; root = deleteNode(root, 10); cout << "Inorder traversal: "; inorder(root); )
बाइनरी सर्च ट्री जटिलताएं
समय जटिलता
| ऑपरेशन | बेस्ट केस कॉम्प्लेक्सिटी | औसत केस जटिलता | सबसे खराब मामला जटिलता |
| खोज | O (लॉग एन) | O (लॉग एन) | पर) |
| सम्मिलन | O (लॉग एन) | O (लॉग एन) | पर) |
| नष्ट करना | O (लॉग एन) | O (लॉग एन) | पर) |
यहां, पेड़ में n नोड्स की संख्या है।
अंतरिक्ष की जटिलता
सभी परिचालनों के लिए अंतरिक्ष जटिलता O (n) है।
बाइनरी सर्च ट्री एप्लीकेशन
- डेटाबेस में बहुस्तरीय अनुक्रमण में
- गतिशील छँटाई के लिए
- यूनिक्स कर्नेल में वर्चुअल मेमोरी क्षेत्रों के प्रबंधन के लिए
