CSC148H1 Lecture Notes - Lecture 24: Binary Search Tree, Binary Tree, Mutation
1
CSC148H1 Full Course Notes
Verified Note
1 document
Document Summary
Csc148: lecture 24: binary search trees and mutations. References: code seen in the pictures can be found on the csc148 website: http://www. teach. cs. toronto. edu/~csc148h/winter. Add ordering conditions to a binary tree: data are comparable, e. g. int, float, etc. 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. 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.
