A set is described as a group of distinct elements, with each element being unique within the set. Unlike arrays, sets are flexible in size and can vary in length. Once an element is included in a set, it remains unchanged. To update a number in a set, you must first remove the original number and then add the modified version.
Following are the operations that can be performed on a set -
- add(value) - This function adds an element in the set
- intersectionSet(S) - Return the intersection of two sets in the set S
- toArray - Converts a set into an array of elements
- contains(s) - Returns the set if an element to be searched is present in the set
- displaySet - Print the set from beginning to end
- getSize - To get the size of the set
- unionSet(s) - To display the union of two sets with set s
Implementation of sets using BST
The set data structure utilizes the BST (Binary Search Tree) data structure internally. Consequently, we will insert the elements into the tree and leverage this tree structure to establish the Set.
- Craft a template for BST.
In a tree data structure, each node consists of three components - the node's value and references to its left and right children. This structure is represented as follows -
template <typename T>
struct Node { // Create a node of BST
T data; // Node value
Node* left; // Pointer to the left child
Node* right; // Pointer to the right child
};
After establishing a tree structure, the nodes are added to the tree through the insert method. Within a Binary Search Tree (BST), values smaller than the root are positioned to the left side of the tree, while values greater than the root are positioned to the right side of the tree.
The function containsNode is utilized to determine if a node exists within the tree.
The function inorder is employed to display the inorder traversal of the BST.
- Incorporate the BST template within the Set class.
Once the Binary Search Tree (BST) has been established to manage the internal operations of the set, a template for the set is generated to incorporate the BST functionality. This template includes a root node for storing data and utilizes a size variable to retrieve the set's size.
The Set class contains a constructor by default that sets the root of the Binary Search Tree (BST) to NULL, and it also includes a copy constructor for duplicating one set into another set.
// create a class template for implementing a set in BST
template <typename T>
class Set { // Create class set
Node<T>* root; // Root to store the data
int size; // It indicates the size of the set
};
The add function is utilized for inserting values into the set. It avoids adding duplicate data by checking with the containsNode function. If a new element is detected, it is then included in the set.
The function contains verifies the existence of a specific element within the set. It internally invokes containsNode within the Binary Search Tree (BST).
The displaySet function is employed to showcase the elements within the set. It internally invokes the inorder method of the BST.
The getSize function retrieves the set's size.
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stack>
#include <string>
using namespace std;
template <typename T>
struct Node { // Create a node of BST
T data; // Node value
Node* left; // Pointer to the left child
Node* right; // Pointer to the right child
public:
// this function prints inorder traversal of BST
void inorder(Node* r)
{
if (r == NULL) { // If we reach last level
return;
}
inorder(r->left); // print left child
cout << r->data << " "; // print the node value
inorder(r->right); // print the right child
}
/*
Function to check if BST contains a node
with the given data
r pointer to the root node
d the data to search in the BST
The function returns 1 if the node is present in the BST else 0
*/
int containsNode(Node* r, T d)
{
if (r == NULL) { // If we reach last level or tree is empty
return 0;
}
int x = r->data == d ? 1 : 0; // Check for duplicacy
// Traverse in right and left subtree
return x | containsNode(r->left, d) | containsNode(r->right, d);
}
/*
Function to insert a node with
given data into the BST
r pointer to the root node in the BST
d the data to insert in the BST
return pointer to the root of the resultant BST
*/
Node* insert(Node* r, T d)
{
if (r == NULL) { // Add where NULL is encountered which means space is present
Node<T>* tmp = new Node<T>; // Create a new node in BST
tmp->data = d; // insert the data in the BST
tmp->left = tmp->right = NULL; // Allocate left and righcpp tutorialers a NULL
return tmp; // return current node
}
// Insert the node in the left subtree if data is less than current node data
if (d < r->data) {
r->left = insert(r->left, d);
return r;
}
// Insert the node in the right subtree if data is greater than current node data
else if (d > r->data) {
r->right = insert(r->right, d);
return r;
}
else
return r;
}
};
template <typename T> // create a class template for implementing a set in BST
class Set { // Create class set
Node<T>* root; // Root to store the data
int size; // It indicates the size of the set
public:
Set() // If no value passed
{
root = NULL; // Icpp tutorials to NULL
size = 0; // size becomes zero
}
Set(const Set& s) // Copy constructor
{
root = s.root;
size = s.size;
}
void add(const T data) // It add an element to the set
{
if (!root->containsNode(root, data)) { // Check if it is the first element
root = root->insert(root, data); // Insert the data into the set
size++; // Increment the size of the set
}
}
bool contains(T data)
{
return root->containsNode(root, data) ? true : false;
}
void displaySet()
{
cout << "{ ";
root->inorder(root);
cout << "}" << endl;
}
/*
Function to return the current size of the Set
@return size of set
*/
int getSize()
{
return size;
}
};
int main()
{
// Create Set A
Set<int> A;
// Add elements to Set A
A.add(1);
A.add(2);
A.add(3);
A.add(2);
// Display the contents of Set A
cout << "A = ";
A.displaySet();
// Check if Set A contains some elements
cout << "A " << (A.contains(3) ? "contains"
: "does not contain")
<< " 3" << endl;
cout << "A " << (A.contains(4) ? "contains"
: "does not contain")
<< " 4" << endl;
cout << endl;
return 0;
}
Output
A = { 1 2 3 }
A contains 3
A does not contain 4
