Equal keys pose a problem for the implementation of binarysearch trees. a. What

Question

Equal keys pose a problem for the implementation of binarysearch trees.

a. What is the asymptotic performance of TREE-INSERT when usedto insert n items with identical keys into an initiallempty binary search tree?

   We propose to improve TREE-INSERTby testing before line 5 whether or not key[z] = key[x]and by testing before line 11 whether or not key[z] =key[y]. If equality holds, we implement one of thefollowing strategies. For each strategy, find theasymptomatic performance of inserting n items withidentical keys into an initially empty binary search tree. (The strategies are described for line 5, in which we compare thekeys of z and x. Substitute y forx to arrive at the strategies for line 11.)

b. Keep a boolean flag b[x] at nodex, and set x to either left[x] orright[x]   based on the value ofb[x], which alternates beftween FALSE and TRUE   each time is visited duringinsertion of a node with the same key as x. c. Keep a list of nodes with equal keys atx, and insert z into the list. d. Randomly set x to eitherleft[x] or right[x]. (Give theworst-case     performance and informally derivethe average-case performance.)

Equal keys pose a problem for the implementation of binarysearch trees. a. What is the asymptotic performance of TREE-INSERT when usedto insert n items with identical keys into an initiallempty binary search tree?    We propose to improve TREE-INSERTby testing before line 5 whether or not key[z] = key[x]and by testing before line 11 whether or not key[z] =key[y]. If equality holds, we implement one of thefollowing strategies. For each strategy, find theasymptomatic performance of inserting n items withidentical keys into an initially empty binary search tree. (The strategies are described for line 5, in which we compare thekeys of z and x. Substitute y forx to arrive at the strategies for line 11.) b. Keep a boolean flag b[x] at nodex, and set x to either left[x] orright[x]   based on the value ofb[x], which alternates beftween FALSE and TRUE   each time is visited duringinsertion of a node with the same key as x. c. Keep a list of nodes with equal keys atx, and insert z into the list. d. Randomly set x to eitherleft[x] or right[x]. (Give theworst-case     performance and informally derivethe average-case performance.)

Explanation / Answer

#include<iostream>

using namespace std;

#include<stack>

#include<string>

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

struct node

{struct node *left;

int data;

struct node *right;

};

struct node *temp,*temp1,*temp2;

int main()

{

struct node *root,tree;

int i,j,k,m,x;

root=NULL;

while(1)

{scanf("%d",&m);

if(m==-1)break;

else

root=create_tree(root,m);

}

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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