Class Notes (835,312)
Canada (509,091)
CSCA67H3 (56)
Lecture 5

Week 5 - Complete Induction and Trees.pdf

10 Pages
Unlock Document

Computer Science
Anna Bretscher

Trees Defn. A tree is a connected graph without cycles or loops. Trees are important data structures in computer science. You’ve already seen a rooted tree. The Family Tree is a rooted tree. The top of the tree is the root and the nodes follow a parent-child relationship. Similar to a Family Tree, rooted trees in graph theory also have the root at the top and follow parent-child relationships. root ancestors parent(x) x decendents child(x) grandchild(x) 1 Properties of Trees Property 1. A tree on more than one vertex has a “leaf” (vertex of degree 1). Proof. Property 2. A tree T on n vertices has exactly n ▯ 1 edges. Proof. Q. What proof technique might we use? A. 2 Binary Trees Definition A binary tree is a rooted tree in which each internal vertex has two children and one parent. Definition A binary search tree is a binary tree in which each vertex contains a value and the vertices or nodes of the tree are ordered according to their values. 20 10 5 16 35 40 3 8 12 39 45 25 2 4 6 42 50 Exercise. Complete the binary search tree by filling in appropri- ate values. Q. Where do binary trees appear in computer sciences? A. Nearly everywhere!! 3 Applications of Binary Trees Examples*. ▯ Binary Search Tree - Used in many search applications where data is constantly entering/leaving, such as the map and set objects in many languages’ libraries. ▯ Binary Space Partition - Used in almost every 3D video game to determine what objects need to be rendered. ▯ Binary Tries - Used in almost every high-bandwidth router for storing router-tables. ▯ Hash Trees - used in p2p programs and specialized image- signatures in which a hash needs to be verified, but the whole file is not available. ▯ Heaps - Used in heap-sort; fast implementations of Dijk- stra’s algorithm; and in implementing efficient priority-queues, which are used in scheduling processes in many operating systems, Quality-of-Service in routers, and A* (path-finding algorithm used in AI applications, including video games). ▯ Huffman Coding Tree (Chip Uni) - used in compression al- gorithms, such as those used by the .jpeg and .mp3 file- formats. * trees 4 ▯ GGM Trees - Used in cryptographic applications to gener- ate a tree of pseudo-random numbers. ▯ Syntax Tree
More Less

Related notes for CSCA67H3

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.