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

Fig: 1