CPSC 110 Lecture Notes - Lecture 12: Binary Search Tree, Binary Tree, Insert Key
CPSC 110 verified notes
12/26View all
Document Summary
(require 2htdp/image) (require spd/tags) (define text-size 14) (define text-color black) Complete the design of the data definition below to represent a binary search tree (bst). A binary tree is empty or is rooted at a node that is represented by fields for a key, name, left binary tree, and right binary tree. A binary *search* tree is a binary tree with an ordering property such that for every node in the tree: All keys in the left subtree are less than the key in that node. All keys in the right subtree are greater than the key in that node. Here"s an example of a bst where each node represents an account having a unique number or account id (the key) and a name for the account: For each node at every level of the tree: All accounts in the left sub-tree have account numbers less than the node.