CSC148H1 Study Guide - Final Guide: Binary Search Tree, Quadratic Probing, Big O Notation
1
CSC148H1 Full Course Notes
Verified Note
1 document
Document Summary
Add ordering conditions to a binary tree: data are comparable. Item in binary search tree satisfies binary search tree property: data in left subtree are less than node. data, data in right subtree are more than node. data. A binary tree is only a bst if every item satisfies bst property. Any subtree of a bst is also a bst. If bst is balanced , we can check whether an element is present in about log n node accesses. In bst: initial comparison to root tells you which subtree to check, only 1 recursive call needs to be made instead of 2. Insert must ensure bst condition holds: left subtree of node < node. data, right subtree of node > node. data. This method doesn"t return anything: when recursive call is made, don"t reply on it to report back value. Preserve existing structure of tree by putting new item at bottom of tree by making it a leaf.
