$12\mathrm{.}14$ NVCC Lab: Evaluating the Performance of Binary Search Tree

The major advantage of binary search trees over other data structures is that the related sorting algorithms, search algorithms, insertion, and deletion can be very efficient when balanced. A binary search tree is antappropriate structure for many of the same applications discussed previously in conjunction with other collection structures, especially those providing sorted lists. The special advantage of using a binary search tree is that it facilitates searching while conferring the benefits of linking the elements. It provides the best features of both the sorted array$-$based list and the linked list. Similar to a sorted array$-$based list, it can be searched quickly, using a binary search. Similar to a linked list, it allows insertions and removals without having to move large amounts of data. Thus, a binary search tree is particularly well a linked list, it allows insertions and removals without having to move large amounts of data. Thus, a binary search tree is particularly well sulted for applications in which processing time to insert, add and delete must be minimized. However, all aforementioned advantages a maximum $O(logn)$ comparisons to find a particular node. However, in the worst$-$case scenario, it takes up to $O(n)$ comparisons to find a particular node. The following table summarizes the number of Nodes, height, and the number of comparisons to search a particular node in a balanced tree and the worst case