Question 12.1.8: Assume that we want to find the k-th element of a set (accor......

Algorithms and Programming: Problems and Solutions [1518855]

Assume that we want to find the k-th element of a set (according to the ordering on T) in time limited by C . (tree height). What additional information do we need to store at the tree vertices?

Step-by-Step

The 'Blue Check Mark' means that this solution was answered by an expert.
Learn more on how do we answer questions.

At each vertex, we store the number of its descendants. When a vertex is added or deleted, this information must be updated along a path from the root to the new/deleted vertex. While searching for the k-th vertex, we maintain the following invariant: the vertex in question is the s-th vertex (according to the T-ordering) of a subtree rooted at x (here s and x are variables).

Related Answered Questions

Question: 12.2.4

A leaf is added to or deleted from a balanced tree. Prove that it is possible to make the tree balanced again using several rotations and that the number of rotations does not exceed the tree height. ...

Verified Answer:

We prove the more general statement: Lemma. If a s...

Question: 12.2.5

Write addition and deletion procedures that keep the tree balanced. The running time should not exceed C. (tree height). It is allowed to store additional information (needed for balancing) at the vertices of the tree. ...

Verified Answer:

For each vertex we keep the difference between the...

Question: 12.2.3

Suppose a tree is balanced everywhere except at the root where the difference of heights between the left and right subtrees equals 2 (that is, the left and right subtrees are balanced and their heights differs by 2). Prove that this tree may be transformed into a balanced tree using one of the ...

Verified Answer:

Assume, for example, that the left subtree has sma...

Question: 12.2.2

Prove that a balanced tree with n > 1 vertices has height at most C log n for some constant C that does not depend on n. ...

Verified Answer:

By induction over n, we prove that

Φ_{n+2} ...

Question: 12.2.1

Find the minimal and maximal number of vertices in a balanced tree of height n. ...

Verified Answer:

The maximal number of vertices is equal to

...

Question: 12.1.7

Use an ordered tree to store a function whose domain is a finite subset of T and whose range is some set U. The operations are: find the value of the function for a given argument; change this value; delete an element from the domain; and add an element to the domain (the value is also provided). ...

Verified Answer:

We represent the domain using an ordered tree and ...

Question: 12.1.5

Write a procedure that deletes an element t from a set represented as an ordered tree. (If the element is not in the set, nothing should be done.) ...

Verified Answer:

if root = null then begin {the tree is empty, ther...

Question: 12.1.4

Write a procedure that adds an element t to a set represented as an (ordered) T-tree. (If t is already present, nothing should be done.) ...

Verified Answer:

The procedure get_free (var i : integer) produces ...

Question: 12.1.3

Simplify the procedure using the following trick. Extend the array val, adding a cell with index null. Let val [null] be t. ...

Verified Answer:

val [null] := t; x := root ; while t <> val...

Question: 12.1.2

Write a procedure that checks if an element t : Tis present in an ordered tree (as described above). ...

Verified Answer:

if root = null then begin ..t is not in the tree e...