Binary Search Trees

Abstract

Binary Search Trees (BST) are a particular kind of binary tree that allows efficiently finding a specific value in the tree. We will discuss what a BST is and how to find a value in one. The Set abstract data type (ADT) will be introduced, and we will see how to implement one with a Binary Search Tree and with both sorted and unsorted arrays. Finally, we will compare the worst-case complexity (Big-O) of find and insert operations on all three data structures. This lecture is presented for COMP 15 Data Structures, immediately following a lesson about (general) binary trees. Prior knowledge of Big-O notation and structural recursion are also assumed, as well as basic object-oriented programming skills.