CSC148H5 Lecture Notes - Lecture 19: Binary Search Tree, University Of Toronto Mississauga, Binary Search Algorithm
28 Feb 2017
School
Department
Course
Professor
Document Summary
Csc148h5s - introduction to computer science (winter 2017) We"ve seen examples of where a tree structure is more appropriate than a linear structure. E. g. directory hierarchy, representing relationships between items. We will use binary search trees to allow for efficient searching of a collection of data. Don"t confuse binary trees and binary search trees! Binary tree: branching factor at most 2. Binary search trees: binary tree with extra constraint. A binary search tree (bst) is a binary tree in which. Greater than the values of all nodes in its left subtree. Less than the values of all nodes in its right subtree. The right subtree must be bigger than its parent node. All right subtrees is greater than its parent. Suppose we want to know whether value v exists in a bst. We compare v to the value r at the root. If v = r, then the value is found and we are done.
