11.2 Applications of Trees Flashcards
Binary Search Trees:
Each vertex will have a left child and a right child.
Vertex is labelled with key, which is the item of the list.
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.
To add a new item, start with the root. If the new item is less then its left child or move in the left direction and repeat the process, if greater then its right child…..
ALGORITHM 1 Locating an Item in or Adding an Item to a Binary Search Tree.
procedure insertion(T: binary search tree,
x: item)
v := root of T
{a vertex not present in T has the value null }
while v ≠ null and label(v) ≠ x
if x < label(v) then
if left child of v ≠ null then v := left child of v
else add new vertex as a left child of v and set v
:= null
else
if right child of v ≠ null then v := right child of v
else add new vertex as a right child of v and set v
:= null
if root of T = null then add a vertex v to the tree and label it with x
else if v is null or label(v) ≠ x then label new vertex with x and let v be this new vertex
return v {v = location of x}
The complexity of Locating or Adding Item in Binary Search Tree:
Suppose we have
a binary search tree T for a list of n items.
Form U, full binary tree, from T by adding unlabelled vertices when needed so every vertex with a key has 2 children.
Now we can add a new item as a key wout creating new vertex.
A full binary tree with n internal vertices, leaves = n + 1.
Comparisons depend on h of tree, more h more comparisons.
h>=ceiling(log base 2 (n+1) )
So at least h comparisons.
If its balanced then no more than ceiling(log base 2 (n+1) ) comparisons.
Decision Tree:
A rooted tree in which each internal vertex corresponds to a decision,
with a subtree at these vertices for each possible outcome of the decision, is called a decision
tree.
The possible solutions of the problem correspond to the paths to the leaves of this rooted
tree.
Each possible outcome must be represented by at least one
leaf.
THE COMPLEXITY OF COMPARISON-BASED SORTING ALGORITHMS
To decide whether a particular sorting algorithm
is efficient, its complexity is determined. Using decision trees as models, a lower bound for the
worst-case complexity of sorting algorithms that are based on binary comparisons can be found.
Note that given n elements, there are n! possible
orderings of these elements, because each of the n! permutations of these elements can be the
correct order
{binary comparisons, that is, the comparison of two elements at a time}
The result of each such comparison narrows down the set of possible orderings. Thus, a sorting
algorithm based on binary comparisons can be represented by a binary decision tree in which
each internal vertex represents a comparison of two elements. Each leaf represents one of the n!
permutations of n elements.
Thm 1
no of comparisons needed?
A sorting algorithm based on binary comparisons requires at least x comparisons. x is?
and give a reason.
A sorting algorithm based on binary comparisons requires at least ⌈log2 n!⌉ comparisons.
(log with base 2)
(longest path) the largest number of comparisons ever needed is equal to the height of the decision
tree. Because the height of a binary tree with n! leaves is at least ⌈log2 n!⌉ (using Corollary 1
in Section 11.1), at least ⌈log2 n!⌉ comparisons are needed
Corollary 1
Big Omega
for
The number of comparisons used by a sorting algorithm to sort n elements based on binary
comparisons
The number of comparisons used by a sorting algorithm to sort n elements based on binary
comparisons is Ω(n log n).
We can use Theorem 1 to provide a big-Omega estimate for the number of comparisons used
by a sorting algorithm based on binary comparison. We need only note that by Exercise 74 in
Section 3.2 we know that ⌈log n!⌉ is Θ(n log n), one of the commonly used reference functions
for the computational complexity of algorithms. Corollary 1 is a consequence of this estimate.
THM 2:
Avg # comparisons to sort n elements based on binary comparison.
The average number of comparisons used by a sorting algorithm to sort n elements based on
binary comparisons is Ω(n log n).
The average number of comparisons used by a sorting algorithm based on binary comparisons
is the average depth of a leaf in the decision tree representing the sorting algorithm. By Exercise 48 in Section 11.1 we know that the average depth of a leaf in a binary tree with N vertices
is Ω(log N). We obtain the following estimate when we let N = n! and note that a function that
is Ω(log n!) is also Ω(n log n) because log n! is Θ(n log n).
Prefix Codes :
Consider the problem of using bit strings to encode the letters of the English alphabet (where
no distinction is made between lowercase and uppercase letters).
Consider using bit strings of different lengths to encode letters. Letters that occur more
frequently should be encoded using short bit strings. Some
method must be used to determine where the bits for each character start and end. For instance,
if e = 0, a =1, and t =01, then the bit string 0101 could correspond to
eat, tea, eaea, or tt.
One way to ensure that no bit string corresponds to more than one sequence of letters is to
encode letters so that the bit string for a letter never occurs as the first part of the bit string for
another letter. Codes with this property are called prefix codes
Represent a prefic code way:
he 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.
whats Huffman coding:
We now introduce an algorithm that takes as input the frequencies
(which are the probabilities of occurrences) of symbols in a string and produces as output a
prefix code that encodes the string using the fewest possible bits, among all possible binary
prefix codes for these symbols. This algorithm, known as Huffman coding,
Huffman coding is a fundamental algorithm in data compression,
Algorithm : Huffman Coding:
Expalin logic behind it:
ALGORITHM 2 Huffman Coding.
procedure Huffman(C: symbols ai with frequencies wi
, i = 1, … , n)
F := forest of n rooted trees, each consisting of the single vertex ai and assigned weight wi
while F is not a tree
Replace the rooted trees T and T′ of least weights from F with w(T) ≥ w(T′
) with a tree
having a new root that has T as its left subtree and T′ as its right subtree. Label the new
edge to T with 0 and the new edge to T′ with 1.
Assign w(T) + w(T′
) as the weight of the new tree.
{the Huffman coding for the symbol ai is the concatenation of the labels of the edges in the
unique path from the root to the vertex ai
}
Game trees:
visit later.
Trees can be used to analyze certain types of games such as tic-tac-toe, nim, checkers, and chess. In each of these games, two players take turns making moves. Each player knows the moves made by the other player and no element of chance enters into the game. We model such
games using game trees;
Representation of Game trees:
Vertices: Represent position that a game can be in as it progresses; edges represent legal moves between these postion.
, we simplify game trees by representing all symmetric positions of a game by
the same vertex. However, the same position of a game may be represented by different vertices
if different sequences of moves lead to this position.
Root: starting point.
vertices at even levels by boxes and odd by circles.
Leaves : Final position.
We assign a value to each
leaf indicating the payoff to the first player if the game terminates in the position represented by
this leaf. For games that are win–lose, we label a terminal vertex represented by a circle with
a 1 to indicate a win by the first player and we label a terminal vertex represented by a box with a -1 to indicate 2nd player win. For draw we use 0.
Note that for win–lose games, we
have assigned values to terminal vertices so that the larger the value, the better the outcome for
the first player.
