Tango Tree Multiple Choice Questions and Answers (MCQs)

Uncategorized

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Tango Tree”.

1. Which type of binary search tree is imitated for construction of tango tree?
A) Complete Binary Search Tree
B) Perfect Binary Search Tree
C) Balanced Binary Search Tree
D) Degenerate Binary Search Tree

Explanation: Tango trees are created by simulating a binary search tree in its entirety. This tree is also known as the Reference tree because it includes all of the tree’s elements. In addition, in actual implementation, the reference tree is never seen.

2. Which special balanced binary search tree is used to store the nodes of auxiliary tree?
A) Red – Black Tree
B) Red – Brown Tree
C) Red – Yellow Tree
D) Red – Tango Tree

Explanation: The preferred path is the path that runs from the root to the end of the leaf node, following the path of the preferred child node. For the representation of the preferred direction, nodes are stored in a Red – Black tree.

3. Is tango tree represented as a tree of trees.
A) True
B) False

Explanation: Tango tree uses the partitioning process, which divides a binary search tree into small sets of paths and stores them in auxiliary trees. As a result, the tango tree is depicted as a forest of trees.

4. Which operation is used to combine two auxiliary trees?
A) Join
B) Combinatorial
C) Add
D) Concatenation

Explanation: The join operation can be used to join the two auxiliary trees if the top node of one of the reference trees is a child of the bottom node of the other reference tree.

15. Is partitioning method used by Tango Tree.
A) True
B) False

Explanation: Tango tree uses the partitioning process, which divides a binary search tree into small sets of paths and stores them in auxiliary trees. As a result, the tango tree is depicted as a forest of trees.

6. Which operation is used to break a preferred path into two sets of parts at a particular node?
A) Differentiate
B) Cut
C) Integrate
D) Join

Explanation: The preferred path is divided into two parts. One is referred to as the top half, while the other is referred to as the bottom part. At a specific node, the cut operation is used to split a desired path into two sets.

7. What is the upper bound for a tango tree if k is a number of interleaves?
A) k+2 O (log (log n))
B) k O (log n)
C) K2 O (log n)
D) k+1 O (log (log n))

Explanation: To evaluate the work performed by a tango tree on a given set of sequences, an upper bound is discovered. The upper bound for connecting to the tango tree is found to be k+1 O (log (log n)).

8. What is the time complexity for searching k+1 auxiliary trees?
A) k+2 O (log (log n))
B) k+1 O (log n)
C) K+2 O (log n)
D) k+1 O (log (log n))

Explanation: Since the auxiliary tree size is bounded by the height of the reference tree, which is log n, each search operation in the auxiliary tree takes O (log (log n)) time. As a result, the cumulative search time for k+1 auxiliary trees is k+1 O (log (log n)).

9. What is the time complexity for the update cost on auxiliary trees?
A) O (log (log n))
B) k-1 O (log n)
C) K2 O (log n)
D) k+1 O (log (log n))

Explanation: The upper bound also applies to the upgrade cost. For the auxiliary tree, we perform one cut and one join operation, resulting in a total update cost of k+1 O (log (log n) for the auxiliary tree.

10. Which of the following is the self-adjusting binary search tree?
A) AVL Tree
B) Splay Tree
C) Top Tree
D) Ternary Tree

Explanation: Splay tree is a binary search tree that adjusts itself. It performs simple tree operations such as addition, deletion, and looping, and it does so in O (log n) time.

11. Who developed the concept of tango tree?
A) Erik Demaine
B) Mihai Patrascu
C) John Lacono
D) All of the mentioned

Explanation: Erik Demaine is a well-known MIT Computer Science professor. Mihai Patrascu was a Romanian-American computer scientist who specialised in data structures and algorithms, while John Lacono was an American computer scientist who specialised in data structures and algorithms. Tango tree was created by all of them working together.

12. Which type of tree is tango tree?
A) Ternary Tree
B) AVL Tree
C) Binary Search Tree
D) K-ary Tree

Explanation: Tango tree is a binary search tree that was created in 2004 by four well-known scientists Erik Demaine, Mihai Patrascu, John Lacono, and Harmon.

13. After which city is tango tree named?
A) Vatican City
B) Buenos Aires
C) New York
D) California

Explanation: Tango is a common partner or couple dance that began in the 1880s somewhere between Argentina and Uruguay. Buenos Aires is Argentina’s capital city. As a result, they were given the name Buenos Aires.

14. Which type of binary search tree or algorithm does tango tree use?
A) Online
B) Offline
C) Static
D) Dynamic

Explanation: As compared to the time complexity of the offline binary search tree model, the Tango tree is an online binary search tree with a time complexity of O (log (log n)). A piece-by-piece online algorithm processes the input or data generated.

15. What is the time complexity of for achieving competitive ratio by tango tree?
A) O (log n)
B) O (n2)
C) O (n!)
D) O (log (log n))

Explanation: As compared to the time complexity of the offline binary search tree model, the Tango tree is an online binary search tree with a time complexity of O (log (log n)). A piece-by-piece online algorithm processes the input or data generated.

In 2004, Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Pătrașcu proposed the tango tree, a type of binary search tree named after Buenos Aires, of which the tango is emblematic. It is an online binary search tree that achieves a competitive ratio of displaystyle O(log log n)O(log log n) as compared to the offline optimal binary search tree, while only using displaystyle O(log log n)O(log log n) extra bits of memory per node. This was an improvement over the previous best known competitive ratio, displaystyle O(log n)O. (\log n).

Leave a Reply

Your email address will not be published. Required fields are marked *