I&C SCI 46 Lecture Notes - Lecture 10: Binary Search Tree, Binary Search Algorithm, Binary Tree

• School: UC-Irvine
• Department: Information and Computer Science
• Course: I&C SCI 46
• Professor: Richard Pattis

Document Summary

This lecture will cover a specific kind of binary tree: a binary search tree (bst). We can use these trees, if they are well balanced, to insert, search, and remove values with complexity of o(log n). Such a data structure would be an improvement for implementing sets, maps, and priority queues, where some of these operations are o(n) for array and linked list implementations. We will discuss the ordering property of binary search trees, along with iterative and recursive versions of the insert, search, and remove functions, and finally illustrate four kinds of tree traversal orders and how to create iterators for bsts. This property is trivially true for empty trees and leaves (because they have no subtrees that might contain nodes that have incorrect values). Note that this property applies between a parent and all its descendants (all the nodes in its left and right subtree), not just its children.