g d w scholarship possibil cpt information pdf academic calendar a cla
Search for question
Question
G
D
W
Scholarship-Possibil...
CPT Information.pdf... Academic Calendar... A class reg - UTASSP... A Maverick Pantry - D...
f Software Engineerin...
H Student Dashboard...
SEARCH ALGORITHMS
с
Mail Gadde, Tejas...
localhost:4200
Please select an algorithm:
Linear Search
O Binary Search
O Binary Tree Search
O Red Black Tree
Enter the input size:
Generate Random Numbers
G
×
+
☆
0
886060,709903,268840,304635,776834,141332,709716,814988,85421,694702,208213,967546,747352,132758,472702,244863,434341,997950,964223,726873,505198,634914,675471,6
100000
Enter search key:
78989
Element not found
Runtime 2.1999999284744263
Submit
myho
र
H
+
9:40 PM
4/10/2024/n Project 2: Search Algorithms
Linear Search
Binary Search in Sorted Array
Binary Search Tree
Red-Black Tree
Data Structures Used:
1. Vector (std::vector<int>):
• Used to store a collection of integers.
•
In the code, it's used to store input values for searching algorithms.
2. Binary Search Tree (struct node):
•
•
Represents a binary search tree node.
Contains a key value, left and right child pointers, and a colour indicator (for
Red-Black Tree).
3. Red-Black Tree (struct Node):
•
Represents a node in a Red-Black Tree.
Contains key value, pointers to parent, left and right children, and a colour
indicator.
Main Methods:
Linear Search Algorithm:
1. linear_searching(int n, vector<int> V):
•
•
•
Description: Performs linear search for an integer n in a vector V.
Parameters:
•
n: The integer to search for.
V: The vector of integers to search in.
Returns:
true if n is found in V, otherwise false.
Binary Search Algorithm:
1. binary_searching(int n, vector<int> V):
•
.
Description: Performs binary search for an integer n in a sorted vector V.
Parameters:
•
•
n: The integer to search for.
V: The sorted vector of integers to search in.
Returns:
true if n is found in V, otherwise false. Binary Search Tree (BST) Algorithm:
1. struct node* newNode(int item):
•
.
Description: Creates a new node for a binary search tree with the given item
as the key.
Parameters:
item: The key value of the new node.
•
Returns:
A pointer to the newly created node.
2. struct node* add(struct node* node, int key):
•
•
•
Description: Adds a new node with the given key to the binary search tree
rooted at node.
Parameters:
•
node: The root of the binary search tree.
key: The key value of the new node to be added.
Returns:
The updated root of the binary search tree after insertion.
3. bool bst_searching(struct node* root, int key):
•
•
Description: Performs binary search in a binary search tree for the given key.
Parameters:
•
•
root: The root node of the binary search tree.
key: The integer to search for.
Returns:
•
true if key is found in the binary search tree, otherwise false.
Red-Black Tree Algorithm:
Search Method:
NodePtr searchTree(int k):
•
•
Description: Searches for a node with the key value k in the Red-Black Tree.
Parameters:
•
•
k: The key value to search for in the Red-Black Tree.
Return Value:
•
Returns a pointer to the node with the key value k if found, otherwise returns
a pointer to the null node TNULL.
Insertion Method:
void insert(int key):
•
Description: Inserts a new node with the key value key into the Red-Black Tree while
maintaining the properties of a Red-Black Tree.
• Parameters: •
key: The key value to be inserted into the Red-Black Tree.
Comparison
• Linear Search:
•
•
•
•
•
Performance: Linear search has a time complexity of O(n), where n is the size
of the array. It performs poorly compared to the other algorithms, especially
as the data size increases.
Improvement: There's not much room for improvement in linear search
unless the data is sorted or some additional information about the data is
available.
Binary Search:
•
.
Performance: Binary search has a time complexity of O(log n), making it
much faster than linear search, especially for large data sets. It requires the
data to be sorted.
Improvement: Binary search is already quite efficient, and there's not much
room for improvement in terms of time complexity.
Binary Search Tree (BST):
•
Performance: Binary search trees have an average-case time complexity of
O(log n) for both search and insertion operations. However, in the worst case
(unbalanced tree), the time complexity can degrade to O(n).
Improvement: Balancing techniques like AVL trees or red-black trees can
improve the worst-case time complexity of binary search trees to O(log n) by
ensuring that the tree remains balanced after insertions.
Red-Black Tree (RBT):
•
.
Performance: Red-black trees guarantee O(log n) time complexity for both
search and insertion operations, even in the worst case. They achieve this by
maintaining the balance and properties of the tree during insertions.
Improvement: Red-black trees are already optimized for performance, and
there's little room for improvement in terms of time complexity. However,
constant factor optimizations can be applied to improve runtime efficiency.
In terms of speed comparison, red-black trees generally outperform binary search trees for
large data sets due to their guaranteed logarithmic time complexity. However, for smaller
data sets, the difference in performance may not be significant.
Overall, the choice of algorithm depends on the specific requirements and characteristics of
the data. If the data set is small and frequently changing, linear search may suffice. For large
and sorted data sets, binary search is a good choice. Binary search trees and red-black trees
are suitable for dynamic data sets with frequent insertions and deletions, with red-black
trees providing better worst-case performance guarantees. 1.40E-03
1.20E-03
1.00E-03
Chart Title
Numbers Linear Binary BST
10
RBT
1.10E-05 1.10E-05 1.00E-06 2.00E-06
100 1.20E-05 9.00E-06 4.00E-06 3.00E-06
1000 7.10E-05 1.90E-05 3.00E-06 5.00E-06
10000 0.00016 2.00E-05 4.00E-06 5.00E-06
100000 0.001206 0.000386 8.00E-06 7.00E-06
8.00E-04
6.00E-04
4.00E-04
2.00E-04
0.00E+00
1
2
3
Binary
4
BST
RBT
Linear
Graph size of array vs seconds
5/n Project 2: Search Algorithms
Linear Search
Binary Search in Sorted Array
Binary Search Tree
Red-Black Tree
Data Structures Used:
1. Vector (std::vector<int>):
• Used to store a collection of integers.
•
In the code, it's used to store input values for searching algorithms.
2. Binary Search Tree (struct node):
•
•
Represents a binary search tree node.
Contains a key value, left and right child pointers, and a colour indicator (for
Red-Black Tree).
3. Red-Black Tree (struct Node):
•
Represents a node in a Red-Black Tree.
Contains key value, pointers to parent, left and right children, and a colour
indicator.
Main Methods:
Linear Search Algorithm:
1. linear_searching(int n, vector<int> V):
•
•
•
Description: Performs linear search for an integer n in a vector V.
Parameters:
•
n: The integer to search for.
V: The vector of integers to search in.
Returns:
true if n is found in V, otherwise false.
Binary Search Algorithm:
1. binary_searching(int n, vector<int> V):
•
.
Description: Performs binary search for an integer n in a sorted vector V.
Parameters:
•
•
n: The integer to search for.
V: The sorted vector of integers to search in.
Returns:
true if n is found in V, otherwise false. Binary Search Tree (BST) Algorithm:
1. struct node* newNode(int item):
•
.
Description: Creates a new node for a binary search tree with the given item
as the key.
Parameters:
item: The key value of the new node.
•
Returns:
A pointer to the newly created node.
2. struct node* add(struct node* node, int key):
•
•
•
Description: Adds a new node with the given key to the binary search tree
rooted at node.
Parameters:
•
node: The root of the binary search tree.
key: The key value of the new node to be added.
Returns:
The updated root of the binary search tree after insertion.
3. bool bst_searching(struct node* root, int key):
•
•
Description: Performs binary search in a binary search tree for the given key.
Parameters:
•
•
root: The root node of the binary search tree.
key: The integer to search for.
Returns:
•
true if key is found in the binary search tree, otherwise false.
Red-Black Tree Algorithm:
Search Method:
NodePtr searchTree(int k):
•
•
Description: Searches for a node with the key value k in the Red-Black Tree.
Parameters:
•
•
k: The key value to search for in the Red-Black Tree.
Return Value:
•
Returns a pointer to the node with the key value k if found, otherwise returns
a pointer to the null node TNULL.
Insertion Method:
void insert(int key):
•
Description: Inserts a new node with the key value key into the Red-Black Tree while
maintaining the properties of a Red-Black Tree.
• Parameters: •
key: The key value to be inserted into the Red-Black Tree.
Comparison
• Linear Search:
•
•
•
•
•
Performance: Linear search has a time complexity of O(n), where n is the size
of the array. It performs poorly compared to the other algorithms, especially
as the data size increases.
Improvement: There's not much room for improvement in linear search
unless the data is sorted or some additional information about the data is
available.
Binary Search:
•
.
Performance: Binary search has a time complexity of O(log n), making it
much faster than linear search, especially for large data sets. It requires the
data to be sorted.
Improvement: Binary search is already quite efficient, and there's not much
room for improvement in terms of time complexity.
Binary Search Tree (BST):
•
Performance: Binary search trees have an average-case time complexity of
O(log n) for both search and insertion operations. However, in the worst case
(unbalanced tree), the time complexity can degrade to O(n).
Improvement: Balancing techniques like AVL trees or red-black trees can
improve the worst-case time complexity of binary search trees to O(log n) by
ensuring that the tree remains balanced after insertions.
Red-Black Tree (RBT):
•
.
Performance: Red-black trees guarantee O(log n) time complexity for both
search and insertion operations, even in the worst case. They achieve this by
maintaining the balance and properties of the tree during insertions.
Improvement: Red-black trees are already optimized for performance, and
there's little room for improvement in terms of time complexity. However,
constant factor optimizations can be applied to improve runtime efficiency.
In terms of speed comparison, red-black trees generally outperform binary search trees for
large data sets due to their guaranteed logarithmic time complexity. However, for smaller
data sets, the difference in performance may not be significant.
Overall, the choice of algorithm depends on the specific requirements and characteristics of
the data. If the data set is small and frequently changing, linear search may suffice. For large
and sorted data sets, binary search is a good choice. Binary search trees and red-black trees
are suitable for dynamic data sets with frequent insertions and deletions, with red-black
trees providing better worst-case performance guarantees. 1.40E-03
1.20E-03
1.00E-03
Chart Title
Numbers Linear Binary BST
10
RBT
1.10E-05 1.10E-05 1.00E-06 2.00E-06
100 1.20E-05 9.00E-06 4.00E-06 3.00E-06
1000 7.10E-05 1.90E-05 3.00E-06 5.00E-06
10000 0.00016 2.00E-05 4.00E-06 5.00E-06
100000 0.001206 0.000386 8.00E-06 7.00E-06
8.00E-04
6.00E-04
4.00E-04
2.00E-04
0.00E+00
1
2
3
Binary
4
BST
RBT
Linear
Graph size of array vs seconds
5/n/n