CSC148H5 Lecture Notes - Lecture 7: Binary Tree, Avl Tree, Binary Search Algorithm
Document Summary
We will use the nodes and references representation. Each node keeping left and right references is not going to work anymore. Instead, each nodes keeps a list of children. Motivating binary search tree binary trees, or generally trees, are good for modelling hierarchical structure in real world. But they could be much more useful than just that, if we add some more feature to the binary tree structure. Binary search trees are a subset of binary. They are binary trees with some extra constraint. Searching efficiently in a bst given a bst, we want to determine whether a value v exists in the bst. Observation: say we are searching for 64, since it is smaller than the root 65, according to the. Bst property, 64 must be in the left subtree. There is no need to check the right subtree. Bst search the algorithm: we compare v to the value r at the root.
