Question

[12, 21, 12, 26, 11, 13, 26, 30, 12, 2, 3, 13]

(d - 7 pts) For the binary search tree obtained in (c), determine the average number of comparisons for a successful search and the average number of comparisons for an unsuccessful search. (e - 7 pts) Use the sorted array of (b) to construct a binary search tree. (f - 7 pts) For the binary search tree obtained in (e), determine the average number of comparisons for a successful search and the average number of comparisons for an unsuccessful search.

Answer 1

Hello,

The binary search tree obtained for unsorted array takes less time compared to binary search tree obtained for sorted array. I have created an program to demonstrate the same. Execute the program to get the average comparisons for each element required. Let me know if you need have any queries or changes required.

Code:

#include <iostream>
using namespace std;

struct Node
{
   int key;
   struct Node *left, *right;
};

// Function to insert a new Node with given value in Binary Search Tree
Node* insert(Node* node, int value)
{
   // If the tree is empty, return a new Node
   if (node == NULL)
   {
       struct Node *newNode = new Node;
       newNode->key = value;
       newNode->left = newNode->right = NULL;
       return newNode;
   }

   // Insert the value at correct position
   if (value <= node->key)
       node->left = insert(node->left, value);
   else if (value > node->key)
       node->right = insert(node->right, value);

   // Return the node
   return node;
}

// The function creates the binary search tree
Node* binarySearchTree(int list[], int n)
{
   struct Node *root = NULL;

   // Construct the Binary Search Tree
   for (int i = 0; i < n; i++)
       root = insert(root, list[i]);

   return root;
}

// The function sorts the array
void sort(int *list, int n)
{
   for (int i = 0; i < n - 1; i++)
   {
       for (int j = i + 1; j < n; j++)
       {
           // Swap if current value is greater than next value
           if (list[j] < list[i])
           {
               int temp = list[j];
               list[j] = list[i];
               list[i] = temp;
           }
       }
   }
}

// The fuction search's for the given value and returns the numer of traversals
int search(struct Node *node, int value)
{
   struct Node* head = node;

   if (head == NULL || head->key == value)
       return 1;

   if (head->key < value)
       return search(head->right, value) + 1;
   else
       return search(head->left, value) + 1;
}

void main()
{
   int list[] = { 12, 21, 12, 26, 11, 13, 26, 30, 12, 2, 3, 13 };   // Binary tree elements
   int successSearchList[] = { 26, 3, 2, 30, 13 };                   // List of keys for successful search
   int unsuccessSearchList[] = { 100, 1, 5, 56, 29 };               // List of keys for unsuccessful search

   // Length of each array list
   int n = sizeof(list) / sizeof(list[0]);
   int n1 = sizeof(successSearchList) / sizeof(successSearchList[0]);
   int n2 = sizeof(unsuccessSearchList) / sizeof(unsuccessSearchList[0]);
  
   int count = 0;   // Number of traversals
  
   // Create binary search tree
   struct Node *unsorted = binarySearchTree(list, n);
  
   // Calculate traversals for unsorted successful search list
   cout << "*** Unsorted list search result ***" << endl;
   for (int i = 0; i < n1; i++)
       count += search(unsorted, successSearchList[i]);
   cout << "Average number of successful search: " << count / n1 << endl;

   // Calcualte traversals for unsorted unsuccessful search list
   count = 0;
   for (int i = 0; i < n2; i++)
       count += search(unsorted, unsuccessSearchList[i]);
   cout << "Average number of unsuccessful search: " << count / n2 << endl << endl;

   cout << "*** Sorted list search result ***" << endl;
   sort(list, n);
   struct Node *sorted = binarySearchTree(list, n);

   // Calculate traversals for sorted successful search list
   count = 0;
   for (int i = 0; i < n1; i++)
       count += search(sorted, successSearchList[i]);
   cout << "Average number of successful search: " << count / n1 << endl;

   // Calcualte traversals for sorted unsuccessful search list
   count = 0;
   for (int i = 0; i < n2; i++)
       count += search(sorted, unsuccessSearchList[i]);
   cout << "Average number of unsuccessful search: " << count / n2 << endl;

   cout << "\n\n";
   system("pause");
}

Output: