Class Notes (835,312)
CSCA67H3 (56)
Lecture 5

# Week 5 - Complete Induction and Trees.pdf

10 Pages
445 Views

Department
Computer Science
Course
CSCA67H3
Professor
Anna Bretscher
Semester
Fall

Description
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 Deﬁnition A binary tree is a rooted tree in which each internal vertex has two children and one parent. Deﬁnition 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 ﬁlling 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 veriﬁed, but the whole ﬁle is not available. ▯ Heaps - Used in heap-sort; fast implementations of Dijk- stra’s algorithm; and in implementing efﬁcient priority-queues, which are used in scheduling processes in many operating systems, Quality-of-Service in routers, and A* (path-ﬁnding 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 ﬁle- formats. *http://stackoverﬂow.com/questions/2130416/what-are-the-applications-of-binary- 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
Me

OR

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.