Based of of this code, can you show how to insert new nodes into the tree and ke

Question

Based of of this code, can you show how to insert new nodes into the tree and keep it balanced?

class TwoThreeTree

{

private:
TwoThreeNode root;
public:

TwoThreeTree(TwoThreeNode root); // This is the constructor of the Tree class to which root node will be passed
void addNode(Node n); // This function will add a node to this tree

// Similarly we can add all the operations of a tree

}

class TwoThreeNode
{
   private:
  
   int data1,data2; // Two data elements
   TwoThreeNode parent; // Parent node (for root node it will be null)
   TwoThreeNode firstChild, secondChild, thirdChild; // Three child nodes
  
  
   public:
  
   // Here we can have constructor
   TwoThreeNode(); // overloaded constructor can be used to intialize the Node to set its parent etc
  
}

int main()
{
   // In main we simply create Nodes and then add to 2-3Tree
   TwoThreeNode root; // Create a root node
   TwoThreeTree t(root); // Create 2-3 tree and set with root as root of this tree
  
   TwoThreeNode node1; // Create three more nodes and then add them to 2-3 tree
   TwoThreeNode node2;
   TwoThreeNode node3;
  
   t.add(node1);
   t.add(node2);
   t.add(node3);
  
}

You can add all the operation on this tree as done in BST

Explanation / Answer

working code for the function.

void addNode(Node n);
{
if(!root)
{
root = n;
}
else if(root->Data >= n->Data)
{
n->Parent = root;
AddNode(n, root->Left);
}
else if(root->Data < n->Data)
{
n->Parent = root;
AddNode(n, root->Right);
}
}

Basically insertion in bst can be made a recursive function. we check here with respect to the root node in the tree. If root node is not there then we make the input node as root node otherwise we follow the behaviour of BST where values less than root goes to left side and greater goes to right hand side.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.