Welcome to Lesson 10! Learning Objectives By the end of today's class, you should know...
1. The Binary Search Tree ADT 1.1. Defining a BST
The BST Property: 1. Every element in node n's left subtree is less than or equal to the element in n. 2. Every element in n's right subtree is greater than the element in node n. (From the Michael Main textbook)
1.2. BST: A Recursive Structure
1.3. BST Operations: Insertion
1.4. Reflection Activity
1.5. Insertion Pseudocode
public void insert(T data) { if (root == null) { root = new Node(data); } else { insert(data, root); } }
Pseudocode for insert(node, value) 1. Check if the value to insert is smaller than or equal to the data stored at node. 1a. If this is true 1aa. Check if node's left is null 1aaa. If this is true, insert the value at node's left 1b. If the node's left is not NULL 1bb.recursively call the insert method passing it node's left and value 2. Otherwise 2a. Check if the node's right is null 2aa. If this is true, insert the value at node's right 2b. If the node's right is not null 2bb. recursively call the insert method passing it node's right and value 2. Analyzing the Efficiency of BST Operations 2.1. Introduction to Runtime Analysis on Binary Search Tree Operations
BST Operations Worst Case: O(n)
BST Operations Average Case: O(log_{2} n)
n > n / 2 > n / 4 > n/ 8... > n/ 2^{k} = 1
n = 2^{k}
log_{2} (n) = k
2.2. Comparison of Arrays, Linked Lists and Binary Search Trees
Array Linked List Binary Search Tree Search O(log n) O(n) O(log n) Insertion O(n) O(n) O(log n) Deletion O(n) O(n) O(log n) 2.3. Animated BST Efficiency compared to a Linked List (although it says array) Wrap Up
Upcoming Assignments
