Algorithm of the Bst (Binary Search Tree)
The Bst (binary search tree) follows the simplest algorithm:
- First, it begins with identifying whether the tree is vacant. If so, the binary search will terminate the program.
- If the tree is not empty, it searches for the root of the tree.
- The search heads to the subtree if the key value doesn’t match the root value. If the value of the subtree is less than the root value, the search will stop at this point. A search for the appropriate subtree occurs if the subtree’s key value exceeds the root value. In the end, if the key does not exist in the tree, the unsuccessful search message will be returned and the binary search of the tree will be terminated.
Program of the Recursive Binary Search Tree
Here, we begin with the binary search tree program using the recursion method where the function is called itself to break the complex cases into simpler ones.
using namespace std;
int BinSearch(int ArrayIs[], int integer, int start, int end)
{
int midPosition;
if (start > end){
cout << "Integer is not found";
return 0;
} else {
midPosition = (start + end) / 2;
if(ArrayIs[midPosition] == integer){
cout << "Integer is found at " << midPosition << " postion \n";
} else if (integer > ArrayIs[midPosition]) {
BinSearch (ArrayIs, integer, midPosition+1, end);
} else if (integer < ArrayIs[midPosition]) {
BinSearch (ArrayIs, integer, start , midPosition-1);
}
}
}
int main() {
int ArrayIs[50], integer, i, n, start, end;
cout <<"Please provide size of an array (Max 50) \n";
cin >> n;
cout <<"Please provide the sorted values \n";
for(x=0; x<n; x++) {
cin >> ArrayIs[x];
}
cout <<"Please provide a value to be search \n";
cin >> integer;
start = 0;
end = n-1;
BinSearch (ArrayIs, integer, start, end);
return 0;
}
In the given script of the binary search tree, we define the “BinSearch” function where we pass the arrays for the array, the integer is the target element, the start is the beginning index of the array, and the end is the last index of an array as an argument.
Inside the BinSearch() function, we initialize the “midPosition” variable which refers to the mid-index of the array. Then, we set the “if” condition which is used to check whether the start index value is greater than the end index value. If that’s the case, the “Integer is not found” message will be prompted. Otherwise, if the start index value is smaller than the end index value, we use the “(start + end) / 2” formula for the mid index value. This formula calculates the value of the mid index with the target integer. If both matches, the integer is found.
Then, we have the “Else-if” statement which verifies that the specified integer is greater than the BinSearch() function and invokes itself recursively with the modified start index as “midPosition+1” and the same start index.
Similarly, if the specified integer is smaller than the BinSearch() function, it recursively invokes itself with the modified last index as “midPosition-1” using the same last index. The main() function comes next where the numerical value of an array is obtained from the user and is stored in the “ArrIs”. Then, we ask the user to provide the value to be searched. Here, we set the start index to 0 and the last index to “n-1”.
The output of the recursive binary search tree is as follows:
Program of the Iterative Binary Search Tree
Here, we perform the iterative binary search tree method which searches the position of the value in a specified sorted array and returns the “doesn’t exist” message if it is not found.
using namespace std;
int bS(int Arr[], int low, int peak, int n)
{
while (low <= peak) {
int midIndex = low + (peak - low) / 2;
if (Arr[midIndex] == n)
return midIndex;
if (Arr[midIndex] < n)
low = midIndex + 1;
y
else
peak = midIndex - 1;
}
return -1;
}
int main(void)
{
int Arr[] = { 3, 6, 7, 9, 11 };
int n = 9;
int s = sizeof(Arr) / sizeof(Arr[0]);
int res = bS(Arr, 0, s - 1, n);
(res == -1)
? cout << "Number is not present in array"
: cout << "Number is present at index " << res;
return 0;
}
In the given script, we establish a new function which is “bS()” that performs the binary search tree. We pass the “Arr[]”array for the binary search. Then, we input the “low” and “peak” variables which represent the first and last indices of the array. After that, we pass the “n” variable which is the target value to be searched using the iterative binary search.
Next, we dive into the binary function which is “bS()” where the “while” loop is applied. We set a low index to the “while” loop which is smaller than or equal to the peak index. Then, within the “while” loop, we drive the “low + (peak – low) / 2” formula to calculate the mid index of the array. This “while” loop continues until the low index becomes greater than the peak index.
After that, we set the “if” statement, comparing the mid-index value to the specified value. If the specified value is found, the index of that value is returned. Besides that, we have another “if” statement where the mid-index is smaller than the specified value. Then, the low index is updated by “midIndex+1” to search in the array’s right half. When the mid-index exceeds the given value, the function searches the left half of the array and updates the peak index by “midIndex-1”. If the initial condition is met, the specified value is not found and -1 is returned.
Finally, we call the main() function where we assign the sorted value to the “Arr[]” array. Next, we specify that “n” should be searched with a value of “9”. After that, we calle the “bS()” binary function within the “res” variable. Here, we set the low index to 0 and the peak index to “n-1”. “Arr” is where the “n” value will be searched. If the specified element is found, the position of that element in the array will be printed. Otherwise, the prompt will generate the “element is not found” message at the index.
The array is sorted and the searched value is 9. This searched value is found at index “3” of the given array. So, the results that are retrieved in the console are the index value of that searched value of “9”.
Conclusion
In conclusion, we discussed the key concept of the binary search tree and the implementation of this methodology via code. A binary search tree has an improved time complexity and surpasses the linear search. The time complexity on which the binary search tree performs is Olog(n).
