Question

I also don't quite understand the meaning of N.size, is N.size (the sum of nodes) (a node and its sub trees) has? please also explain that, thank you.

modify the standard definition of a binary search tree to add a field N.size at each Suppose that we node, which records the size of the subtree under N'Tincluding N itself). A. Explain how to modify the procedure for adding both the case where X is not yet in the tree and is added, and the case where X is already in the tree, and the tree remains unchanged. element X to a tree. Be sure to consider an You only need to describe the changes that are made to the standard algorithm; you do not have to repeat the standard algorithm. B. Explain how to modify the procedure for deleting an element. As in (A), consider both cases. C. Describe a procedure for finding the kth largest element in the tree. D. Describe a procedure for finding the number of elements in the tree less than X All of these procedures should run in time proportional to the height of the tree.

Answer 1

A binary search tree is a binary tree (i.e. a finite set of data items which is either empty or consists of a single item called the root and two disjoint binary trees called the left sub-tree and right sub-tree)which is either empty or satisfies the following rules:

1) The value of left sub-tree is less than the value of root.

2) Value of right sub-tree is more than or equal to the values of root.

3) All the sub-trees of left and right sub-trees observe the two rules.

N.size is as same as given in second line of the image. Thus,here N.size record the size of sub-tree under N(including N)

A)Procedure / Algorithm of adding X element with both cases

1. Struct record * insert(struct *tree, long digit, long N)repeat steps 2 to 14
2. If (tree==NULL)step 3 to 6
3. Tree =(struct record*)malloc(sizeof(struct record));
4. Tree->left=tree->right=NULL
5. Tree->num=digit;
6. N++;
7. Else step 7
8. If(digit<tree->num)tree->left=insert(tree->left, digit,N)
9. N=Nl++;
10. Else step 9
11. If(digit>tree->num)tree->right=insert(tree->right, digit,N)
12. N=Nr++;
13. Else step 11
14. If(digit==tree->num)tree->right=insert(tree->right, digit, N)
15. N=Nr++;
16. //for duplicate nodes
17. Exit (0);
18. Return (tree);
19. end

B) Procedure / Algorithm of deleting X element with both cases

1. Struct record * delnum (int digit, struct record *r, long N)
2. {
3. struct record *
4. If (r->!=NULL)del num(digit, r->right ,N)
5. Else
6. q->num=r->num;
7. q=r;
8. r= r->left;
9. }
10. Struct record * deletnode (int digit, struct record *tree, long N)
11. {
12. Struct recird *r,*q;
13. If(tree==NULL)
14. {
15. Exit(0);
16. }
17. If(digit<tree->num)
18. deletenode(digit,tree->left, N)
19. N=Nl--;
20. else
21. If(digit>tree->num)
22. deletenode(digit,tree->right, N)
23. N=Nr--;
24. q=NULL;
25. else
26. if(q->right==NULL)tree=q->left;
27. else
28. if(q->left==NULL)tree=tree=q->right;
29. else
30. delnum(digit, q->left,N)
31. free(q);
32. end

C) Procedure / Algorithm for finding kth element

for search

1. void search(struct record *tree, long digit,int N)steps 2 to 9
2. if(tree==NULL)step 3
3. puts(“no number”);
4. else if(digit==tree->num)step 5
5. printf(“%d”,digit);
6. else if(digit<tree->num)step 7
7. search(tree->left, digit,N);
8. else search(tree->left, digit,N);
9. end

D) For finding number less than X

For this, same procedure will be applied like as in C.procedure,but only left of tree function will be called for search.