Matematika Diskrit : Relasi, Sifat Relasi, dan Contoh Soal

Struktur Diskret : Dasar-dasar Pohon, Pohon Berakar, dan Implementasinya

Introduction to Trees

A Tree

A tree is a connected undirected graph with no simple circuit. An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.

THEOREM: A tree with n vertices has n – 1 edges.

Example :

A Rooted Tree

A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root. Different choice of root produce different rooted tree.

Example :

Properties of Rooted Trees

• Parent – A vertex other than root is a parent if it has one or more children
• The parent of c is b

• Children – If A is a vertex with successors B and C, then B and C are the children of A.
• The children of a is b, f and g

• Siblings – Children with the same parent vertex.
• h, i and j are siblings

• Level – the length of the unique path from the root to a vertex
• Vertex a is at level 0
• Vertices d and e is at level 3

• Height – The maximum level of all the vertices
• The height of this tree is 3.

• Ancestor of a vertex (v) – the vertices in the path from the root to this vertex excluding this vertex.
• The ancestors of e are c, b and a

• Descendent of a vertex (v) – vertices that have v as ancestor.
• The descendants of b are c, d and e

• Leaf – A vertex with no children
• The leaves are d, e, f, i, k, l and m

• Internal Vertices – vertices that have children
• The internal vertices are a, b, c, g, h and j

• Subtree – A subgraph of the tree consisting of a root and its descendent and all edges incident to these descendent.

m-ary Tree

A rooted tree is called an m-ary tree if every vertex has no more than m children. The tree is called a full m-ary tree if every internal vertex has exactly m children.

An m-ary tree with m = 2 is called a binary tree. A rooted m-ary tree is balanced if all leaves are at levels h or h-1.

Examples :

An ordered rooted Tree

An ordered rooted tree is a rooted tree where the children of each internal vertex are ordered. Ordered rooted trees are drawn so that the children of each internal vertex are shown in order from left to right.

In an ordered binary tree (usually called just a binary tree), if an internal vertex has two children, the first child is called the left child and the second child is called the right child. The tree rooted at the left child of a vertex is called the left subtree of this vertex, and the tree rooted at the right child of a vertex is called the right subtree of the vertex.

Examples :

Example: m-ary tree

Suppose that someone starts a chain letter. Each person who receives the letter is asked to send it on to four other people. Some people do this, but others do not send any letters.

How many people have seen the letter, including the first person, if no one receives more than one letter and if the chain letter ends after there have been 100 people, who read it but did not send it out ?

Solution :

Applications of Trees

Binary Search Trees

A binary tree in which each child of a vertex is designated as a right or left child. No vertex has more than one right child or left child. Each vertex is labeled with a key

Vertices are assigned keys so that the key of a vertex is both larger than the keys of all vertices in its left subtree and smaller than the keys of all vertices in its right subtree.

Decision Trees

A rooted tree in which each internal vertex corresponds to a decision, with a subtree at these vertices for each possible outcome of decision.

The possible solutions of the problem correspond to the paths to the leaves of this rooted tree.

Prefix Codes

A prefix code is a type of code system (typically a variable-length code) distinguished by its possession of the “prefix property”, which requires that there is no whole code word in the system that is a prefix (initial segment) of any other code word in the system.

A prefix code can be represented using a binary tree, where the characters are the labels of the leaves in the tree. The edges of the tree are labeled so that an edge leading to a left child is assigned a 0 and an edge leading to a right child is assigned a 1. The bit string used to encode a character is the sequence of labels of the edges in the unique path from the root to the leaf that has this character as its label.

Example: the tree represents the encoding of e by 0, a by 10, t by 110, n by 1110, and s by 1111.

Huffman Coding

Use Huffman coding to encode the following symbols with the frequencies listed:

A: 0.08,
B: 0.10,
C: 0.12,
D: 0.15,
E: 0.20,
F: 0.35.

What is the average number of bits used to encode a character?

Game Trees

Use trees to analyze certain types of games. Vertices represent the positions can be in as it progresses. Edges represent legal moves between this position

Games tree is infinite if the games they represent never end

Sumber

Slide StrukDis : Pohon

http://informatika.unpar.ac.id/