COMPSCI 61A Lecture Notes - Lecture 21: Binary Search Tree, Binary Tree, Binary Search Algorithm
27 Jan 2018
School
Department
Course
Professor
22
COMPSCI 61A Full Course Notes
Verified Note
22 documents
Document Summary
Binary tree is a tree that has a left branch, and a right branch. Need to distinguish between left and right: fill the place of a missing left branch with an empty tree. Empty = tree(none: an instance of btree always has exactly two branches. Type of tree that supports binary search. 20 in [1, 2, 4, 8, 16, 32], check middle (8), eliminate bottom half. For sorted list of n, theta expression o(log n ) Binary search tree is a binary tree where labels are. Larger than all entries in left branch. Smaller than all entries in its right branch. Construct a binary search tree from . How to find the largest value of a binary search tree? def largest(t): def second(t): return t. label if t. right is btree. empty: else: return largest(t. right) return t. label. If t. is_leaf(): return none elif t. right. is_leaf(): elif t. right is btree. empty:
