CISC 235 Lecture Notes - Lecture 7: Binary Tree, Search Algorithm, Binary Search Algorithm
14 May 2016
School
Department
Course
Professor
Document Summary
Binary search tree: a binary tree is used to store data. Each vertex contains an element of the data set. The vertices are arranged to satisfy the following additional property: at each vertex, the value stored is >= all values stored in the vertex"s left subtree, and < all values stored in the vertex"s right subtree. Binary search trees are wildly popular as data structures - we will spend the next couple of weeks looking at their properties in some detail. Suppose we are creating an application that requires 3 operations on the data set: We already have data structures that supports these operations: one-dimensional arrays and lists. Because of the ordering of the values in the vertices, searching a bst works just like binary search on a sorted array. We start at the root - if it contains the value we want, we are done. If not, we go to the left or right child, as appropriate.
