Report on Critical Review of Binary Search Tree Algorithm

Report on Critical Review of Binary Search Tree Algorithm What is Binary Search Tree? Binary search tree (BST) is a dynamic data structure, which means that its size is only limited by amount of free memory in the computer and number of elements may differ during the program executed. BST has aComparableKey (and an associated value) for each. All elements in its left sub-tree are less-or-equal to the node (, and all the elements in its right sub-tree are greater than the node (>). Assumexbe a node in a binary search tree. Ifyis a node in the left sub-tree ofx,thenkey[y] [x].Ifyis a node in the right sub-tree ofx,thenkey[x] [y]. A main pro of binary search trees is fast searching. There are three type of binary search tree: Inorder traversal Preorder traversal Postorder traversal In inorder traversal, the left sub-tree of the given node is visited first, then the value at the given node is printed and then the right sub-tree of the given node is visited. This process is applied recursively all the node in the tree until either the left sub-tree is empty or the right sub tree is empty. Java code for inorder traversal: public void printInorder(){ printInOrderRec(root); System.out.println(); } /** * Helper method to recursively print the contents in an inorder way */ private void printInOrderRec(Node currRoot){ if ( currRoot == null ){ return; } printInOrderRec(currRoot.left); System.out.print(currRoot.value+, ); printInOrderRec(currRoot.right); } In preorder traversal, the value at the given node is printed first and then the left sub-tree of the given node is visited and then the right sub-tree of the given node is visited. This process is applied recursively all the node in the tree until either the left sub-tree is empty or the right sub tree is empty. Java code for preorder traversal: public void printPreorder() { printPreOrderRec(root); System.out.println(); } /** * Helper method to recursively print the contents in a Preorder way */ private void printPreOrderRec(Node currRoot) { if (currRoot == null) { return; } System.out.print(currRoot.value + , ); printPreOrderRec(currRoot.left); printPreOrderRec(currRoot.right); } In postorder traversal, the left sub-tree of the given node is traversed first, then the right sub-tree of the given node is traversed and then the value at the given node is printed. This process is applied recursively all the node in the tree until either the left sub-tree is empty or the right sub-tree is empty. Java code for postorder traversal: public void printPostorder() { printPostOrderRec(root); System.out.println(); } /** * Helper method to recursively print the contents in a Postorder way */ private void printPostOrderRec(Node currRoot) { if (currRoot == null) { return; } printPostOrderRec(currRoot.left); printPostOrderRec(currRoot.right); System.out.print(currRoot.value + , ); } Full code example for BST //Represents a node in the Binary Search Tree. class Node { //The value present in the node. public int value; //The reference to the left subtree. public Node left; //The reference to the right subtree. public Node right; public Node(int value) { this.value = value; } } //Represents the Binary Search Tree. class BinarySearchTree { //Refrence for the root of the tree. public Node root; public BinarySearchTree insert(int value) { Node node = new Node(value); if (root == null) { root = node; return this; } insertRec(root, node); return this; } private void insertRec(Node latestRoot, Node node) { if (latestRoot.value > node.value) { if (latestRoot.left == null) { latestRoot.left = node; return; } else { insertRec(latestRoot.left, node); } } else { if (latestRoot.right == null) { latestRoot.right = node; return; } else { insertRec(latestRoot.right, node); } } } //Returns the minimum value in the Binary Search Tree. public int findMinimum() { if (root == null) { return 0; } Node currNode = root; while (currNode.left != null) { currNode = currNode.left; } return currNode.value; } //Returns the maximum value in the Binary Search Tree public int findMaximum() { if (root == null) { return 0; } Node currNode = root; while (currNode.right != null) { currNode = currNode.right; } return currNode.value; } //Printing the contents of the tree in an inorder way. public void printInorder() { printInOrderRec(root); System.out.println(); } //Helper method to recursively print the contents in an inorder way private void printInOrderRec(Node currRoot) { if (currRoot == null) { return; } printInOrderRec(currRoot.left); System.out.print(currRoot.value + , ); printInOrderRec(currRoot.right); } //Printing the contents of the tree in a Preorder way. public void printPreorder() { printPreOrderRec(root); System.out.println(); } //Helper method to recursively print the contents in a Preorder way private void printPreOrderRec(Node currRoot) { if (currRoot == null) { return; } System.out.print(currRoot.value + , ); printPreOrderRec(currRoot.left); printPreOrderRec(currRoot.right); } //Printing the contents of the tree in a Postorder way. public void printPostorder() { printPostOrderRec(root); System.out.println(); } //Helper method to recursively print the contents in a Postorder way private void printPostOrderRec(Node currRoot) { if (currRoot == null) { return; } printPostOrderRec(currRoot.left); printPostOrderRec(currRoot.right); System.out.print(currRoot.value + , ); } } //Main method to run program. class BSTDemo { public static void main(String args []) { BinarySearchTree bst = new BinarySearchTree(); bst .insert(10) .insert(40) .insert(37) .insert(98) .insert(51) .insert(6) .insert(73) .insert(72) .insert(64) .insert(99) .insert(13) .insert(9); System.out.println(The Binary Search Tree Example); System.out.println(Inorder Traversal:); bst.printInorder(); System.out.println(Preorder Traversal:); bst.printPreorder(); System.out.println(Postorder Traversal:); bst.printPostorder(); System.out.println(); System.out.println(The minimum value in the BST: + bst.findMinimum()); System.out.println(The maximum value in the BST: + bst.findMaximum()); } } Output example Linear Search Algorithm Linear search, also known as sequential search, is a operation that checks every element in the list sequentially until the target element is found. The computational complexity for linear search isO(n),making it mostly much less efficient than binary searchO(log n).But when list items can be arranged in order from greatest to lowest and the possibility appear as geometric distribution (f (x)=(1-p) x-1p, x=1,2),then linear search can have the potential to be greatly faster than binary search. The worst case performance scenario for a linear search is that it needs to loop through the entire collection; either because the item is the last one, or because the item isnt found. In other words, if havingNitems in the collection, the worst case scenario to find an item isNiterations. This is known asO(N)using theBig O Notation. The speed of search grows linearly with the number of items within the collection. Linear searches dont require the collection to be sorted. Example java program to show linear search algorithm class LinearSearchDemo { public static int linearSearch(int[] array, int key) { int size = array.length; for(int i=0;i { if(array[i] == key) { return i; } } return -1; } public static void main(String a[]) { int[] array1= {66,42,1,99,59,53,16,21}; int searchKey = 99; System.out.println(Key +searchKey+ found at index: +linearSearch(array1, searchKey)); int[] array2= {460,129,128,994,632,807,777}; searchKey = 129; System.out.println(Key +searchKey+ found at index: +linearSearch(array2, searchKey)); } } Output example Why Linear Search? Alinear searchlooks down a list, one item at a time, without skipping. In complexity terms this is an O(n) search where the time taken to search the list gets bigger at the same rate as the list does. Binary searchtree when starts with the middle of a sorted list, and it see whether thats greater than or less than the value it looking for, which determines whether the value is in the first or second half of the list. Skip to the half way through the sub-list, and compare again. In complexity terms this is an O(log n) search where the number of search operations grows more slowly than the list does, because it is halving the search space with each operation. For example, suppose to search for U in an A-Z list of letter where index 0-25 and the target value at index 20. A linear search would ask: list[0] == U? False. list[1] == U? False. list[2] == U? False. list[3] == U? False. . .. †¦ list[20] == U? True. Finished. The binary search would ask: Comparelist[12](M) with U: Smaller, look further on. (Range=13-25) Comparelist[19](T) with U: Smaller, look further on. (Range=20-25) Comparelist[22](W) with U: Bigger, look earlier. (Range=20-21) Comparelist[20](U) with U: Found it. Finished. Comparing the two: Binary search requires the input data to be sorted but linear search doesnt. Binary search requires anorderingcomparison but linear search only requires equality comparisons. Binary search has complexity O(log n) but linear search has complexity O(n). Binary search requires random access to the data but linear search only requires sequential access. (it means a linear search canstreamdata of arbitrary size) Divide and Conquer Algorithm Divide and conquer is a top-down technique for designing algorithms that consists of dividing the problem into smaller sub-problems hoping that the solutions of the sub-problems are easier to find and then composing the partial solutions into the solution of the original problem. Divide and conquer paradigm consists of following major phases: Divide Breaking the probleminto several sub-problems that are similar to the original problem but smaller in size. Conquer Solve the sub-problemrecursively (successively and independently). Combine these solutionsto sub-problems to create a solution to the original problem. The similarity with Binary Search Tree, it is a degenerate divide and conquer search algorithm but with no combine phase. It searches for akeyin asortedvector then returning theindexwhere the key was found or return -1 when not found. It also reduces the problem size by half each recursion. The algorithm definition: Divides sorted vector into 2 halves. The lower halves contain values less or equal the key and the higher half values greater than or equal the key. If the low index exceeds the high index the key is not in the vector. Compute the middle index of the vector. If the key equals the value at the middle of the vector, the index of the middle is returned If the key is less than the value at the middle of the vector, the lower half is searched If the key is greater than the value at the middle of the vector, the higher half is searched Only one of the halves is searched, reducing the problem size by half each time. Recursion Technique Recursionis a technique of solving problems that includes breaking down a problem into smaller and smaller sub-problems until get to a small enough problem that it can be solved trivially. Normally recursion includes a function calling itself. While it may not would appear to be much at first glance, recursion allow to write elegant solutions to problems that may otherwise be extremely hard to program. It is very similar with binary search tree that using divide and conquer technique which is breaking down problem into sub-problems. A binary search or half-interval search algorithm discover the position of a specified value within a sorted array. In each step, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index is returned. Otherwise, if the looked key is less than the middle elements key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special Not found indication is returned. Every repetition eliminates half of the remaining possibilities. This makes binary searches very efficient even for large collections. Binary search requires a sorted collection. Additionally, binary searching can only be applied to a collection that allows random access (indexing). Worst case performance: O(log n) Best case performance: O(1) Recursion is utilized as a part in this algorithm because with each pass a new array is created by cutting the old one in half. The binary search procedure is then called recursively, this time on the new array. Commonly the arrays size is adjusted by manipulating a beginning and ending index. The algorithm exhibits a logarithmic order of growth because it essentially divides the problem domain in half with each pass. Conclusion The conclusion is there is never be the best approach to follow blindly, each of these algorithms has its pros and cons. So, if there is any scenario or problem, it should be analyze first and adopt one of these algorithms to find what’s suit. REFERENCE Implement Binary search in java using divide and conquer technique. Java search algorithm programs. 2014. [ONLINE] Available at:http://java2novice.com/java-search-algorithms/binary-search/. [Accessed 26 October 2014]. Best searching algorithm | java coding algorithms. 2014 [ONLINE] Available at:http://tekmarathon.com/2012/10/05/best-searching-algorithm-2/. [Accessed 26 October 2014]. Linear Search. 2014.Linear Search. [ONLINE] Available at:http://algorithms.openmymind.net/search/linear.html. [Accessed 26 October 2014]. Java Recursion with examples. 2014. [ONLINE] Available at:http://danzig.jct.ac.il/java_class/recursion.html. [Accessed 26 October 2014]. Divide-and-Conquer Algorithms. 2014.Divide-and-Conquer Algorithms. [ONLINE] Available at:http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/divide.htm. [Accessed 26 October 2014]. Binary Search Trees. 2014.Binary Search Trees. [ONLINE] Available at:http://pages.cs.wisc.edu/~vernon/cs367/notes/9.BST.html. [Accessed 27 October 2014]. Binary Trees . 2014.Binary Trees. [ONLINE] Available at:http://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html. [Accessed 27 October 2014]. Data structures Why is Binary Search a divide and conquer algorithm? Stack Overflow. 2014. [ONLINE] Available at:http://stackoverflow.com/questions/8850447/why-is-binary-search-a-divide-and-conquer-algorithm. [Accessed 27 October 2014].