डेटा संरचना में बाइनरी ट्री (उदाहरण)
सारा चेन
बाइनरी ट्री क्या है?
बाइनरी शब्द का मतलब दो होता है। ट्री डेटा स्ट्रक्चर में "बाइनरी ट्री" का मतलब एक ऐसा पेड़ होता है, जहाँ प्रत्येक नोड में अधिकतम दो चाइल्ड नोड (बाएं और दाएं नोड) हो सकते हैं। यह एक सरल बाइनरी ट्री है।
हालाँकि, एक और बाइनरी ट्री है जिसका सबसे अधिक बार उपयोग किया जाता है और इसके कई उपयोग मामले हैं। इसे बाइनरी सर्च ट्री (BST) कहा जाता है। यह ट्री सर्च एल्गोरिदम को बहुत तेज़ बना सकता है, ठीक लॉग (n) समय जटिलता। डेटा संरचना में, n का मतलब बाइनरी ट्री में नोड्स की संख्या है।
बाइनरी ट्री और बाइनरी सर्च ट्री के बीच क्या अंतर हैं?
BST और नियमित बाइनरी ट्री के बीच अंतर यह है कि BST में बाएं नोड का मान रूट नोड से छोटा होता है, और दाएं नोड का मान रूट नोड से बड़ा होता है। इसलिए, बाएं उपवृक्ष में हमेशा रूट से छोटा मान होगा, और दाएं उपवृक्ष में हमेशा रूट से बड़ा मान होगा।
बाइनरी सर्च ट्री का उदाहरण
आइये बाइनरी सर्च ट्री की अवधारणाओं को प्रदर्शित करने के लिए निम्नलिखित उदाहरण देखें।
यहाँ आप देख सकते हैं कि सभी नोड्स दिए गए अनुशासन का पालन करते हैं। बाइनरी सर्च ट्री में नोड्स की अधिकतम संख्या के लिए एक सूत्र है। यदि हम उपरोक्त ट्री को देखें, तो हम देख सकते हैं कि सभी लीफ नोड्स को छोड़कर प्रत्येक नोड में दो बच्चे हैं। और दिए गए बाइनरी ट्री की ऊँचाई (h) 4 है। सूत्र है 2h - 1. तो, यह 15 देता है.
ऊपर दी गई छवि एक पूर्ण बाइनरी ट्री या संतुलित बाइनरी ट्री नहीं है, इसे पूर्ण बाइनरी ट्री या संतुलित बाइनरी ट्री कहा जाता है। AVL (बाइनरी ट्री का एक अन्य प्रकार) नामक एक और डेटा संरचना है जो बाइनरी ट्री की ऊंचाई को अनुकूलित करती है और चित्र 3 की तरह BST के लिए तेज़ी से खोज करती है।
ऊपर दिए गए बाइनरी ट्री के इन-ऑर्डर ट्रैवर्सल की गणना करने का प्रयास करें। आप पाएंगे कि यह एक गैर-घटती क्रमबद्ध सरणी देगा, और ट्रैवर्सल एल्गोरिदम बाइनरी ट्री के समान होगा।
बाइनरी ट्री के प्रकार
बाइनरी ट्री के कुछ महत्वपूर्ण प्रकार यहां दिए गए हैं:
- पूर्ण बाइनरी ट्री: इस बाइनरी ट्री में प्रत्येक नोड में 0 या 2 चाइल्ड नोड हो सकते हैं। इस प्रकार के बाइनरी ट्री में केवल एक चाइल्ड नोड की अनुमति नहीं है। इसलिए, लीफ नोड को छोड़कर, सभी नोड्स में 2 चाइल्ड नोड होंगे।
- पूर्ण बाइनरी ट्री: प्रत्येक नोड में 0 या 2 नोड हो सकते हैं। यह पूर्ण बाइनरी ट्री की तरह लगता है, लेकिन सभी लीफ तत्व बाएं उपवृक्ष की ओर झुके होते हैं, जबकि पूर्ण बाइनरी ट्री में नोड दाएं या बाएं उपवृक्ष में हो सकता है।
- परफेक्ट बाइनरी ट्री: सभी नोड्स में 0 या 2 नोड होने चाहिए, और सभी लीफ नोड्स एक ही स्तर या ऊंचाई पर होने चाहिए। पूर्ण बाइनरी ट्री संरचना का उपरोक्त उदाहरण एक परफेक्ट बाइनरी ट्री नहीं है क्योंकि नोड 6 और नोड 1,2,3 एक ही ऊंचाई पर नहीं हैं। लेकिन पूर्ण बाइनरी ट्री का उदाहरण एक परफेक्ट बाइनरी ट्री है।
- पतित बाइनरी वृक्ष: प्रत्येक नोड में केवल एक ही संतान हो सकती है। सभी ऑपरेशन जैसे खोजना, सम्मिलित करना और हटाना O(N) समय लेते हैं।
- संतुलित बाइनरी ट्री: यहाँ इस बाइनरी ट्री में, बाएं और दाएं सबट्री की ऊंचाई का अंतर अधिकतम 1 है। इसलिए, नोड जोड़ते या हटाते समय, हमें ट्री की ऊंचाई को फिर से संतुलित करने की आवश्यकता होती है। इस प्रकार के स्व-संतुलित बाइनरी ट्री को कहा जाता है एवीएल पेड़.
बीएसटी के तीन बुनियादी ऑपरेशन हैं। नीचे उन पर विस्तार से चर्चा की गई है।
सी और सी में बाइनरी ट्री का कार्यान्वयन C++
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int value;
struct Node *left, *right;
}
struct Node *getEmptynode(int val)
{
struct Node *tempNode = (struct Node *)malloc(sizeof(struct Node));
tempNode->value = val;
tempNode->left = NULL;
tempNode->right = NULL;
return tempNode;
}
struct Node *successor(struct Node *node)
{
struct Node *present = node;
// going to the left most node
while (present != NULL && present->left != NULL)
{
present = present->left;
}
return present;
}
struct Node *insert(struct Node *node, int value)
{
if (node == NULL)
{
return getEmptynode(value);
}
if (value < node->value)
{
node->left = insert(node->left, value);
}
else
{
node->right = insert(node->right, value);
}
return node;
}
int searchInBST(struct Node *node, int value)
{
struct Node *current = node;
while (current->value != value)
{
if (current->value > value)
{
current = current->left;
}
else
{
current = current->right;
}
if (current == NULL)
{
return 0;
}
}
return 1;
}
void inorder(struct Node *root)
{
if (root != NULL)
{
inorder(root->left);
cout << root->value << " ";
inorder(root->right);
}
}
struct Node *deleteNode(struct Node *node, int value)
{
if (node == NULL)
{
return node;
}
if (value < node->value)
{
node->left = deleteNode(node->left, value);
}
else if (value > node->value)
{
node->right = deleteNode(node->right, value);
}
else
{
if (node->left == NULL)
{
struct Node *temp = node->right;
free(node);
return temp;
}
else if (node->right == NULL)
{
struct Node *temp = node->left;
free(node);
return temp;
}
struct Node *temp = successor(node->right);
node->value = temp->value;
node->right = deleteNode(node->right, temp->value);
}
return node;
}
int main()
{
struct Node *root = NULL;
root = insert(root, 8);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 2);
root = insert(root, 6);
root = insert(root, 10);
root = insert(root, 14);
root = insert(root, 1);
root = insert(root, 3);
root = insert(root, 5);
root = insert(root, 7);
root = insert(root, 9);
root = insert(root, 11);
root = insert(root, 13);
root = insert(root, 15);
cout << "InOrder Traversal after inserting all nodes: " << endl;
inorder(root);
root = insert(root, -10);
cout << "\nInOrder Traversal after inserting -10 : " << endl;
inorder(root);
cout << "\nSearching -5 in the BST: " << searchInBST(root, -5) << endl;
cout << "Searching -10 in the BST: " << searchInBST(root, -10) << endl;
root = deleteNode(root,8);
cout<<"After deleting node 8, inorder traversal: "<<endl;
inorder(root);
root = deleteNode(root,-10);
cout<<"\nAfter deleting node -10, inorder traversal: "<<endl;
inorder(root);
}
आउटपुट:
InOrder Traversal after inserting all nodes: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: 0 Searching -10 in the BST: 1 After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
बाइनरी ट्री का कार्यान्वयन Python
class Node:
def __init__(self,value):
self.left = None
self.right = None
self.value = value
def insert(root,value):
if root == None:
return Node(value)
if value< root.value:
root.left = insert(root.left,value)
else:
root.right = insert(root.right,value)
return root
def searchInBST(root,value):
current = root
while current.value != value:
if current.value > value:
current = current.left
else:
current = current.right
if current == None:
return "Not found"
return "Found"
def inorder(root):
if root != None:
inorder(root.left)
print(root.value,end=" ")
inorder(root.right)
def successor(root):
present = root
while present != None and present.left != None:
present = present.left
return present
def deleteNode(root,value):
if root == None:
return root
if value < root.value:
root.left = deleteNode(root.left, value)
elif value>root.value:
root.right = deleteNode(root.right, value)
else:
if root.left == None:
temp = root.right
root = None
return temp
elif root.right == None:
temp = root.left
root = None
return temp
temp = successor(root.right)
root.value = temp.value
root.right = deleteNode(root.right, temp.value)
return root
root = Node(8)
root = insert(root, 4)
root = insert(root, 12)
root = insert(root, 2)
root = insert(root, 6)
root = insert(root, 10)
root = insert(root, 14)
root = insert(root, 1)
root = insert(root, 3)
root = insert(root, 5)
root = insert(root, 7)
root = insert(root, 9)
root = insert(root, 11)
root = insert(root, 13)
root = insert(root, 15)
print("InOrder Traversal after inserting all nodes: ")
inorder(root)
root = insert(root, -10)
print("\nInOrder Traversal after inserting -10 : ")
inorder(root)
print("\nSearching -5 in the BST: ",searchInBST(root, -5))
print("Searching -5 in the BST: ",searchInBST(root, -10))
root = deleteNode(root,8)
print("After deleting node 8, inorder traversal:")
inorder(root)
root = deleteNode(root,-10)
print("\nAfter deleting node -10, inorder traversal:")
inorder(root)
आउटपुट:
InOrder Traversal after inserting all nodes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : -10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: Not found Searching -5 in the BST: Found After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
बाइनरी ट्री का अनुप्रयोग
बाइनरी ट्री के कुछ सामान्य अनुप्रयोग इस प्रकार हैं:
- नोड डेटा को क्रमबद्ध क्रम में व्यवस्थित करना
- प्रोग्रामिंग भाषा लाइब्रेरी में मानचित्र और सेट नोड ऑब्जेक्ट में उपयोग किया जाता है।
- डेटा संरचनाओं में तत्वों की खोज करना
» हमारे अगले ट्यूटोरियल के बारे में जानें संयोजन एल्गोरिथ्म
