CMPT 115 Lecture Notes - Lecture 14: Binary Search Tree, Tree Traversal, Binary Search Algorithm
Document Summary
Notes written by michael horsch, mark eramian, ian mcquillan, lingling jin, and dmytro dyachuk. 1: searching an unsorted list requires that we traverse each element until we nd the element searched for. Searching in sorted lists: with the list adt, we could have used either a linked list or an array for data structure. Sorted linked list: slow insertion and deletion - o(n), slow searching - o(n). Sorted arrays: slow insertion and deletion - o(n), fast searching - o(log n) (recall: binary search). Binary search is not easy to apply to linked lists because we cannot jump to the middle in one step. The list adt had several operations to insert new data. Pre: rlist :: reference to a list target :: the key of an element in rlist el :: an element. The binary tree adt had several operations to insert new data. Pre: rparent is a reference to a tree rnew is a reference to a tree.
