DMA_10.1-2.ppt

§10.1: Introduction to Trees A tree is a connected undirected graph with no simple circuits. Theorem: There is a unique simple path between any two of its nodes. An undirected graph without simple circuits is called a forest. You can think of it as a set of trees having disjoint sets of nodes. Rooted Trees A rooted tree is a tree in which one node has been designated the root. Every edge is (implicitly or explicitly) directed away from the root. You should know the following terms about rooted trees: Parent, child, siblings, ancestors, descendents, leaf, internal node, subtree. n-ary trees A rooted tree is called n-ary if every internal vertex has no more than n children. It is full if every internal vertex has exactly n children. A 2-ary tree is called a binary tree. Ordered Rooted Tree A rooted tree where the children of each internal node are ordered. In ordered binary trees, we can define: left child, right child left subtree, right subtree For n-ary trees with n2, can use terms like “leftmost”, “rightmost,” etc. Trees as Models Can use trees to model the following: Saturated hydrocarbons Organizational structures Computer file systems In each case, would you use a rooted or a non-rooted tree? Training Dataset Output: A Decision Tree for “buys_computer” Presentation of Classification Results Visualization of a Decision Tree in SGI/MineSet 3.0 Some Tree Theorems A tree with n nodes has n?1 edges. A full m-ary tree with i internal nodes has n=mi+1 nodes, and ?=(m?1)i+1 leaves. Proof: There are mi children of internal nodes, plus the root. And, ? = n?i = (m?1)i+1. □ Thus, given m, we can compute any of i, n, and ? from any of the others. More Theorems Definition: The level of a node is the length of the simple path from the root to the node. The height of a tree is maximum node level. A rooted m-ary tree with height h is balanced if all leaves are at levels h or h?1. Theorem: There are at most mh leaves in an m-ary tree of height h. Corollary: An m-ary tree w