जावा में बाइनरी सर्च ट्री

binary search tree java implementation code examples

यह ट्यूटोरियल जावा में बाइनरी सर्च ट्री को कवर करता है। आप जावा में BST बनाना, सम्मिलित करना, हटाना और खोजना सीखेंगे, जावा में BST को लागू करेंगे और कार्यान्वित करेंगे:

एक बाइनरी सर्च ट्री (जिसे इसके बाद BST कहा जाता है) एक प्रकार का बाइनरी ट्री है। इसे नोड-आधारित बाइनरी ट्री के रूप में भी परिभाषित किया जा सकता है। BST को 'ऑर्डर किए गए बाइनरी ट्री' के रूप में भी जाना जाता है। BST में, बाईं सबट्री में सभी नोड्स में ऐसे मान होते हैं जो रूट नोड के मान से कम होते हैं।

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

=> एक्सक्लूसिव जावा ट्रेनिंग ट्यूटोरियल सीरीज़ के लिए यहां जाएं।

आप क्या सीखेंगे:

जावा में बाइनरी सर्च ट्री
निष्कर्ष
- अनुशंसित पाठ

एक BST डुप्लिकेट नोड्स की अनुमति नहीं देता है।

नीचे दिए गए चित्र में BST प्रतिनिधित्व दिखाया गया है:

ऊपर दिखाया गया एक नमूना BST है। हम देखते हैं कि 20 इस पेड़ का मूल नोड है। बाएं सबट्री में सभी नोड मान हैं जो 20 से कम हैं। सही सबट्री में सभी नोड्स हैं जो 20 से अधिक हैं। हम कह सकते हैं कि उपरोक्त पेड़ बीएसटी गुणों को पूरा करता है।

प्रविष्टि या विलोपन और वस्तुओं की खोज के समय Arrays और लिंक्ड सूची की तुलना में BST डेटा संरचना को बहुत कुशल माना जाता है।

BST किसी तत्व को खोजने के लिए O (लॉग एन) समय लेता है। जैसा कि तत्वों का आदेश दिया जाता है, एक तत्व की खोज करते समय हर कदम पर आधा उपटैब छोड़ दिया जाता है। यह संभव हो जाता है क्योंकि हम खोजे जाने वाले तत्व के किसी न किसी स्थान को आसानी से निर्धारित कर सकते हैं।

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

एक बाइनरी सर्च ट्री (BST) बनाना

तत्वों की एक सरणी को देखते हुए, हमें एक BST का निर्माण करने की आवश्यकता है।

इसे नीचे दिखाए अनुसार करें:

दिए गए सरणी: 45, 10, 7, 90, 12, 50, 13, 39, 57

आइए पहले शीर्ष तत्व यानी 45 को रूट नोड के रूप में देखें। यहां से हम पहले से ही चर्चा की गई संपत्तियों पर विचार करके BST का निर्माण करेंगे।

एक पेड़ बनाने के लिए, हम सरणी में प्रत्येक तत्व की जड़ के साथ तुलना करेंगे। फिर हम तत्व को पेड़ में एक उपयुक्त स्थान पर रखेंगे।

BST के लिए संपूर्ण निर्माण प्रक्रिया नीचे दिखाई गई है।

BST पूरा किया

बाइनरी सर्च ट्री ऑपरेशंस

BST विभिन्न परिचालनों का समर्थन करता है। निम्न तालिका जावा में BST द्वारा समर्थित विधियों को दिखाती है। हम इनमें से प्रत्येक विधि पर अलग से चर्चा करेंगे।

विधि / ऑपरेशन	विवरण
डालने	BST गुणों का उल्लंघन न करके BST में एक तत्व जोड़ें।
हटाएं	किसी दिए गए नोड को BST से निकालें। नोड रूट नोड, गैर-पत्ती या पत्ती नोड हो सकता है।
खोज	BST में दिए गए तत्व का स्थान खोजें। यह ऑपरेशन जांचता है कि क्या पेड़ में निर्दिष्ट कुंजी है।

BST में एक तत्व डालें

एक तत्व हमेशा BST में लीफ नोड के रूप में डाला जाता है।

नीचे एक तत्व डालने के चरण दिए गए हैं।

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

आइए BST के सम्मिलित ऑपरेशन का एक चित्रण देखें।

निम्नलिखित बीएसटी पर विचार करें और हमें पेड़ में तत्व 2 डालें।

आकृति 1

चित्र 2

BST के लिए सम्मिलित ऑपरेशन ऊपर दिखाया गया है। अंजीर (1) में, हम उस पथ को दिखाते हैं जिसे हम BST में तत्व 2 को सम्मिलित करने के लिए पार करते हैं। हमने उन स्थितियों को भी दिखाया है जो प्रत्येक नोड पर जाँची जाती हैं। पुनरावर्ती तुलना के परिणामस्वरूप, तत्व 2 को 1 के सही बच्चे के रूप में डाला जाता है जैसा कि अंजीर (2) में दिखाया गया है।

BST में सर्च ऑपरेशन

यह खोजने के लिए कि क्या कोई तत्व BST में मौजूद है, हम फिर से रूट से शुरू करते हैं और फिर बाएं या दाएं उपप्रकार का पता लगाते हैं, यह पता लगाने के लिए कि क्या रूट से कम या ज्यादा है।

नीचे सूचीबद्ध किए गए चरण हैं जिनका हमें अनुसरण करना है।

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

एक उदाहरण के साथ खोज ऑपरेशन को चित्रित करें। विचार करें कि हमें कुंजी = 12 खोजना है।

नीचे दिए गए आंकड़े में, हम इस तत्व की खोज करने के लिए हमारे द्वारा अनुसरण किए जाने वाले मार्ग का पता लगाएंगे।

जैसा कि उपरोक्त आंकड़े में दिखाया गया है, हम पहले कुंजी की जड़ से तुलना करते हैं। चूँकि कुंजी अधिक है, हम सही सबट्री को पार करते हैं। सही उपशीर्षक में, हम फिर से सही नोड में पहले नोड के साथ कुंजी की तुलना करते हैं।

हम पाते हैं कि कुंजी 15. से कम है, इसलिए हम नोड 15 के बाईं ओर उपर ले जाते हैं। 15 के तत्काल बाएं नोड 12 है जो कुंजी से मेल खाता है। इस बिंदु पर, हम खोज को रोकते हैं और परिणाम वापस करते हैं।

BST से तत्व निकालें

जब हम BST से एक नोड हटाते हैं, तो नीचे चर्चा की गई तीन संभावनाएँ हैं:

नोड एक पत्ती नोड है

यदि डिलीट किया जाने वाला नोड लीफ नोड है, तो हम सीधे इस नोड को हटा सकते हैं क्योंकि इसमें कोई बाल नोड नहीं है। यह नीचे दी गई छवि में दिखाया गया है।

जैसा कि ऊपर दिखाया गया है, नोड 12 एक पत्ती नोड है और इसे सीधे हटा दिया जा सकता है।

नोड हैव ओनली वन चाइल्ड

जब हमें एक बच्चे के नोड को हटाने की आवश्यकता होती है, तो हम नोड में बच्चे के मूल्य को कॉपी करते हैं और फिर बच्चे को हटा देते हैं।

ऊपर दिए गए आरेख में, हम नोड 90 को हटाना चाहते हैं, जिसमें एक बच्चा 50 है। इसलिए हम 50 को 90 के साथ स्वैप करते हैं और फिर नोड 90 को हटाते हैं जो अब एक बच्चा नोड है।

नोड के दो बच्चे हैं

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

उपरोक्त आरेख में, हम नोड 45 को हटाना चाहते हैं जो BST का मूल नोड है। हम पाते हैं कि इस नोड का सही सबट्री खाली नहीं है। फिर हम सही सबट्री को पार करते हैं और पाते हैं कि नोड 50 यहां न्यूनतम नोड है। इसलिए हम इस मान को 45 की जगह लेते हैं और फिर 45 को हटाते हैं।

यदि हम पेड़ की जांच करते हैं, तो हम देखते हैं कि यह एक BST के गुणों को पूरा करता है। इस प्रकार नोड प्रतिस्थापन सही था।

बाइनरी सर्च ट्री (BST) कार्यान्वयन जावा में

जावा में निम्नलिखित कार्यक्रम उदाहरण के रूप में चित्रण में उपयोग किए गए एक ही पेड़ का उपयोग करके उपरोक्त सभी BST ऑपरेशन का प्रदर्शन प्रदान करता है।

class BST_class { //node class that defines BST node class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } // BST root node Node root; // Constructor for BST =>initial empty tree BST_class(){ root = null; } //delete a node from BST void deleteKey(int key) { root = delete_Recursive(root, key); } //recursive delete function Node delete_Recursive(Node root, int key) { //tree is empty if (root == null) return root; //traverse the tree if (key root.key) //traverse right subtree root.right = delete_Recursive(root.right, key); else { // node contains only one child if (root.left == null) return root.right; else if (root.right == null) return root.left; // node has two children; //get inorder successor (min value in the right subtree) root.key = minValue(root.right); // Delete the inorder successor root.right = delete_Recursive(root.right, root.key); } return root; } int minValue(Node root) { //initially minval = root int minval = root.key; //find minval while (root.left != null) { minval = root.left.key; root = root.left; } return minval; } // insert a node in BST void insert(int key) { root = insert_Recursive(root, key); } //recursive insert function Node insert_Recursive(Node root, int key) { //tree is empty if (root == null) { root = new Node(key); return root; } //traverse the tree if (key root.key) //insert in the right subtree root.right = insert_Recursive(root.right, key); // return pointer return root; } // method for inorder traversal of BST void inorder() { inorder_Recursive(root); } // recursively traverse the BST void inorder_Recursive(Node root) { if (root != null) { inorder_Recursive(root.left); System.out.print(root.key + ' '); inorder_Recursive(root.right); } } boolean search(int key) { root = search_Recursive(root, key); if (root!= null) return true; else return false; } //recursive insert function Node search_Recursive(Node root, int key) // Base Cases: root is null or key is present at root if (root==null } class Main{ public static void main(String[] args) { //create a BST object BST_class bst = new BST_class(); /* BST tree example 45 /  10 90 /  / 7 12 50 */ //insert data into BST bst.insert(45); bst.insert(10); bst.insert(7); bst.insert(12); bst.insert(90); bst.insert(50); //print the BST System.out.println('The BST Created with input data(Left-root-right):'); bst.inorder(); //delete leaf node System.out.println('
The BST after Delete 12(leaf node):'); bst.deleteKey(12); bst.inorder(); //delete the node with one child System.out.println('
The BST after Delete 90 (node with 1 child):'); bst.deleteKey(90); bst.inorder(); //delete node with two children System.out.println('
The BST after Delete 45 (Node with two children):'); bst.deleteKey(45); bst.inorder(); //search a key in the BST boolean ret_val = bst.search (50); System.out.println('
Key 50 found in BST:' + ret_val ); ret_val = bst.search (12); System.out.println('
Key 12 found in BST:' + ret_val ); } }

आउटपुट:

बाइनरी सर्च ट्री (BST) ट्रैवर्सल इन जावा

एक पेड़ एक पदानुक्रमित संरचना है, इस प्रकार हम इसे अन्य डेटा संरचनाओं जैसे सरणियों की तरह रैखिक रूप से नहीं पार कर सकते हैं। किसी भी प्रकार के पेड़ को एक विशेष तरीके से पार करने की आवश्यकता होती है ताकि उसके सभी उपप्रकार और नोड्स कम से कम एक बार देखे जाएं।

उस आदेश के आधार पर, जिसमें रूट नोड, लेफ्ट सबट्री और राइट सबट्री एक ट्री में ट्रैवर्स किए गए हैं, नीचे दिखाए गए अनुसार कुछ ट्रैवर्सल्स हैं:

इनवर्टर ट्रैवर्सल
त्राटक का alवधान
पोस्टऑर्डर ट्रेवरल

उपरोक्त सभी ट्रैवर्सल्स गहराई-पहली तकनीक का उपयोग करते हैं यानी पेड़ को गहराई से घुमाया जाता है।

पेड़ भी ट्रेवर्सल के लिए चौड़ाई-पहली तकनीक का उपयोग करते हैं। इस तकनीक का उपयोग करने वाले दृष्टिकोण को कहा जाता है 'स्तरीय आदेश' ट्रैवर्सल।

इस खंड में, हम उदाहरण के रूप में BST का उपयोग करके प्रत्येक ट्रावेलर्स का प्रदर्शन करेंगे।

उपरोक्त चित्र में दिखाए गए BST के साथ, उपरोक्त वृक्ष के लिए स्तर क्रम निम्न है:

स्तर क्रम ट्रैवर्सल: 10 6 12 4 8

इनवर्टर ट्रैवर्सल

इनवर्टर ट्रैवर्सल अप्रोच ने BST को ऑर्डर में ट्रेस किया, लेफ्ट सबट्री => रूटनोड => राइट सबट्री । इनवर्टर ट्रैवर्सल एक बीएसटी के नोड्स के घटते क्रम को प्रदान करता है।

InOrder Traversal के लिए एल्गोरिथ्म InOrder (bstTree) नीचे दिया गया है।

InOrder (left_subtree) का उपयोग करके बाईं सबट्री को पार करें
रूट नोड पर जाएँ।
InOrder (right_subtree) का उपयोग करके सही सबट्री को पार करें

उपरोक्त पेड़ का इनवर्टर ट्रैवर्सल है:

4 6 8 10 12

जैसा कि देखा गया है, इनवर्टर ट्रैवर्सल के परिणामस्वरूप नोड्स का क्रम घटते क्रम में है।

त्राटक का alवधान

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

PreOrder (bst_tree) ट्रैवर्सल के लिए एल्गोरिथ्म नीचे दिया गया है:

रूट नोड पर जाएँ
PreOrder (left_subtree) के साथ बाईं सबट्री को पार करें।
PreOrder (right_subtree) के साथ सही सबट्री को पार करें।

ऊपर दिए गए BST के लिए प्रीऑर्डर ट्रैवर्सल है:

१० ६ ४ 12 १२

पोस्टऑर्डर ट्रेवरल

पोस्टऑर्डर ट्रेडर ट्रैवेलर्स BST को क्रम में बताता है: लेफ्ट सबट्री-> राइट सबट्री-> रूट नोड । पोस्टऑडर ट्रैवर्सल का उपयोग पेड़ को हटाने या अभिव्यक्ति पेड़ों के मामले में पोस्टफिक्स अभिव्यक्ति प्राप्त करने के लिए किया जाता है।

पोस्टऑडर (bst_tree) ट्रैवर्सल के लिए एल्गोरिथ्म इस प्रकार है:

पोस्टऑर्डर (left_subtree) के साथ बाईं सबट्री को पार करें।
PostOrder (right_subtree) के साथ सही सबट्री को पार करें।
रूट नोड पर जाएँ

उपरोक्त उदाहरण BST के लिए पोस्टऑर्डर ट्रैवरल है:

4 8 6 12 10

अगला, हम एक जावा कार्यान्वयन में गहराई-पहली तकनीक का उपयोग करके इन ट्रैवर्सल्स को लागू करेंगे।

//define node of the BST class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } //BST class class BST_class { // BST root node Node root; BST_class(){ root = null; } //PostOrder Traversal - Left:Right:rootNode (LRn) void postOrder(Node node) { if (node == null) return; // first traverse left subtree recursively postOrder(node.left); // then traverse right subtree recursively postOrder(node.right); // now process root node System.out.print(node.key + ' '); } // InOrder Traversal - Left:rootNode:Right (LnR) void inOrder(Node node) { if (node == null) return; //first traverse left subtree recursively inOrder(node.left); //then go for root node System.out.print(node.key + ' '); //next traverse right subtree recursively inOrder(node.right); } //PreOrder Traversal - rootNode:Left:Right (nLR) void preOrder(Node node) { if (node == null) return; //first print root node first System.out.print(node.key + ' '); // then traverse left subtree recursively preOrder(node.left); // next traverse right subtree recursively preOrder(node.right); } // Wrappers for recursive functions void postOrder_traversal() { postOrder(root); } void inOrder_traversal() { inOrder(root); } void preOrder_traversal() { preOrder(root); } } class Main{ public static void main(String[] args) { //construct a BST BST_class tree = new BST_class(); /* 45 // \ 10 90 // \ 7 12 */ tree.root = new Node(45); tree.root.left = new Node(10); tree.root.right = new Node(90); tree.root.left.left = new Node(7); tree.root.left.right = new Node(12); //PreOrder Traversal System.out.println('BST => PreOrder Traversal:'); tree.preOrder_traversal(); //InOrder Traversal System.out.println('
BST => InOrder Traversal:'); tree.inOrder_traversal(); //PostOrder Traversal System.out.println('
BST => PostOrder Traversal:'); tree.postOrder_traversal(); } }

आउटपुट:

बार बार पूछे जाने वाले प्रश्न

Q # 1) हमें बाइनरी सर्च ट्री की आवश्यकता क्यों है?

उत्तर : जिस तरह से हम रैखिक डेटा संरचना में तत्वों की खोज करते हैं, जैसे बाइनरी सर्च तकनीक का उपयोग कर ऐरे, पेड़ एक पदानुक्रमित संरचना, हमें एक ऐसी संरचना की आवश्यकता होती है जिसका उपयोग किसी पेड़ में तत्वों को खोजने के लिए किया जा सकता है।

यह वह जगह है जहां बाइनरी सर्च ट्री आता है जो हमें तत्वों की कुशल खोज में मदद करता है।

Q # 2) बाइनरी सर्च ट्री के गुण क्या हैं?

जावा में डाइजेस्ट्रा के एल्गोरिथ्म का कार्यान्वयन

उत्तर : एक बाइनरी सर्च ट्री जो बाइनरी ट्री श्रेणी से संबंधित है, में निम्नलिखित गुण हैं:

एक द्विआधारी खोज ट्री में संग्रहीत डेटा अद्वितीय है। यह डुप्लिकेट मानों की अनुमति नहीं देता है।
बाएं उपप्रकार के नोड्स रूट नोड से कम हैं।
सही उपप्रकार के नोड्स रूट नोड से अधिक होते हैं।

Q # 3) बाइनरी सर्च ट्री के एप्लिकेशन क्या हैं?

उत्तर : हम गणित में कुछ निरंतर कार्यों को हल करने के लिए बाइनरी सर्च ट्रीज़ का उपयोग कर सकते हैं। पदानुक्रमित संरचनाओं में डेटा की खोज द्विआधारी खोज पेड़ों के साथ अधिक कुशल हो जाती है। हर चरण के साथ, हम खोज को आधा घटाकर घटा देते हैं।

Q # 4) बाइनरी ट्री और बाइनरी सर्च ट्री में क्या अंतर है?

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

एक द्विआधारी खोज पेड़ में, बाएं उपप्रकार में नोड होते हैं जो रूट नोड से कम या बराबर होते हैं और दाएं उपप्रकार में नोड होते हैं जो रूट नोड से अधिक होते हैं।

Q # 5) क्या बाइनरी सर्च ट्री अद्वितीय है?

उत्तर : एक बाइनरी सर्च ट्री एक बाइनरी ट्री श्रेणी के अंतर्गत आता है। यह इस अर्थ में अद्वितीय है कि यह डुप्लिकेट मानों की अनुमति नहीं देता है और इसके सभी तत्वों को विशिष्ट क्रम के अनुसार क्रमबद्ध किया जाता है।

निष्कर्ष

बाइनरी सर्च ट्री बाइनरी ट्री श्रेणी का एक हिस्सा है और मुख्य रूप से पदानुक्रमित डेटा की खोज के लिए उपयोग किया जाता है। इसका उपयोग कुछ गणितीय समस्याओं को हल करने के लिए भी किया जाता है।

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

=> यहाँ सरल जावा प्रशिक्षण श्रृंखला देखें।

जावा में बाइनरी सर्च ट्री - कार्यान्वयन और कोड उदाहरण