Answer the following questions about the Ternary Search Tree (TST) data structur
ID: 3587102 • Letter: A
Question
Answer the following questions about the Ternary Search Tree (TST) data structure. The TST is a linked data structure similar to a BST, but with a few differences. Each node of the TST has 6 fields hasTo: Boolean indicating whether this node contains two elements (true) or just one (false) lo: data element (integer) that this node contains . hi : another integer, that this node contains; must be greater than or equal nodes of the left subtree must . right: pointer to another TST node; all nodes of the right subtree must nodes of the middle subtree must to lo; may be uninitialized if hasTwo is false left: pointer to another TST ode contain values less than or equal to lo contain values greater than or equal to hi mid: pointer to another TST node; contain values between lo and hi Additionally, all TST nodes will have at least one data element (lo), and no TST node can have children (all 3 pointers NIL) until it contains two data elements (lo and hi) 1. Give pseudocode for a Insert method for the TSTNode class (i.e., TSTNode.Insert) that accepts an integer r and either adds it to a node in the subtree rooted t this node or adds a new node to the subtree, so that all TST proper- ties are maintained. This method should not return anything. You may assume that TSTNode has a valid one-element constructor, TSTNode(r) 2. How does the worst-case complexity of this method compare to inserting an element into a BST with n elements? Justify your answer.Explanation / Answer
struct Node
{
int lo;
int hi;
bool hasTwo;
struct Node *left, *mid, *right;
};
// Function to insert a new word in a Ternary Search Tree
void insert(struct Node** root, int x)
{
// Base Case: Tree is empty
if root is null then
*root -> TSTNode(x)
// If current integer is smaller than root's low,
// then insert this word in left subtree of root
if (x < (*root)->lo) then
insert(&( (*root)->left ), x);
// If current integer is greater than root's hi,
// then insert this word in right subtree of root
else if (x > (*root)->hi) then
insert(&( (*root)->right ), x);
// If current integer is in between lo and hi then add in mid node
else
{
insert(&( (*root)->mid ), x);
}
}
2.The worst case time complexity of ternary search tree is same as BST.
The insertion operations take time proportional to the height of the ternary search tree. which is same as BST
T(n) = O(logn)