CISC 235 Lecture Notes - Lecture 9: Binary Search Tree, Search Algorithm, Binary Tree

• School: Queen's University
• Department: Computing
• Course: CISC 235
• Professor: Robin W Dawes

Document Summary

Binary search trees aka lexically ordered binary trees. When we store information in a binary tree there is no rule that says the information must be stored according to a specific pattern or rule. However, the most popular use of binary trees involves enforcing a simple rule for the placement of the values in the tree: small values go to the left and large values go to the right. Binary search tree: a binary search tree is a binary tree in which 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. Note that we use