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.
1 Properties of Trees
Property 1. A tree on more than one vertex has a “leaf” (vertex
of degree 1).
Property 2. A tree T on n vertices has exactly n ▯ 1 edges.
Q. What proof technique might we use?
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.
5 16 35 40
3 8 12 39 45
2 4 6 42 50
Exercise. Complete the binary search tree by ﬁlling in appropri-
Q. Where do binary trees appear in computer sciences?
A. Nearly everywhere!!
3 Applications of Binary Trees
▯ 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-
4 ▯ GGM Trees - Used in cryptographic applications to gener-
ate a tree of pseudo-random numbers.
▯ Syntax Tree