Answered: C++ PROGRAMMING Topic: Binary Search…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

C++ PROGRAMMING
Topic: Binary Search Trees

Explain the c++ code below.: SEE ATTACHED PHOTO FOR THE PROBLEM INSTRUCTIONS

It doesn't have to be long, as long as you explain what the important parts of the code do. (The code is already implemented and correct, only the explanation needed)

EXPLAIN THE CODE BELOW:

int childCount(node* p) {
bool Cright = false;
bool Cleft = false;
if(p->right != NULL){
Cright = true;
}
if(p->left != NULL){
Cleft = true;
}
if(Cleft == true && Cright== true){
return 2;
}
if(Cright){
return 1;
}
if(Cleft){
return -1;
}
return 0;
}

int set(node* p, int e) {
int elem = p->element;
p->element = e;
return elem;
}

node* addSibling(node* p, int e) {
node* P = p->parent;
if(P != NULL){
if(sibling(p) == NULL){
if(sibling(p) == left(P)){
return addLeft(P,e);
}
return addRight(P,e);
}
}
cout<<"Error"<<endl;
return NULL;
}

void clear() {
clear_postorder(root);
}

void attach(node* p, BTree* t1, BTree* t2) {
if(p->right == NULL && p->left == NULL){
if(t1->root != NULL){
t1->root->parent = p;
p->left = t1->root;
}
if(t2->root != NULL){
t2->root->parent = p;
p->right = t2->root;
}
return;
}
cout<<"Error"<<endl;
}

int remove(node* p) {
if(left(p) == NULL || right(p) == NULL){
node* P = NULL;
node* childNode = NULL;
if(p->parent != NULL){
P = p->parent;
}
else{
P = p;
if(left(P) != NULL){
childNode = P->left;
childNode->parent = NULL;
root = childNode;
}
else{
childNode = P->right;
childNode->parent = NULL;
root = childNode;
}
int elem = P->element;
free(P);
size--;
return elem;
}
if(left(P) == p){
if(left(p) != NULL){
P->left = childNode;
childNode = p->left;
if(p->left != NULL || p->right != NULL){
childNode->parent = P;
}
}
else{
childNode = p->right;
P->left = childNode;
if(p->left != NULL || p->right != NULL){
childNode->parent = P;
}
}
}
else{
if(left(p) != NULL){
childNode = p->left;
P->right = childNode;
if(p->left != NULL || p->right != NULL){
childNode->parent = P;
}
}
else{
childNode = p->right;
P->right = childNode;
if(p->left != NULL || p->right != NULL){
childNode->parent = P;
}
}
}
int elem = p->element;
free(p);
return elem;
size--;
}
cout<<"Error"<<endl;
return 0;
}

ADDITIONAL METHODS: Complete some of the methods in addition to the bare minimum
methods
•int childCount(node* p): Returns O if the position p has no children, -1 if p has only a left
child, 1 if p has only a right child, and 2 if p has two children.
• int set(node* p, int e): Replaces the element stored at position p with element e, and
returns the previously stored element.
•node* addSibling(node* p, int e): Creates a child of the parent of position p to make the
node a sibling of p and returns the position of the new node; an error occurs if p already has
a sibling or p has no parent.
•void clear(): Clears and frees up all of the nodes in the tree. This should be done
recursively where you can call a helper method that is recursive. You can only decrement the
value of your size (i.e. size--) and not directly set it to some other value (e.g. size=0,
size=size-size) in your code that is used by this method.
•void attach(node* p, BTree* T1, BTree* T2): Attaches the internal structure of trees T1 and
T2 as the respective left and right subtrees of leaf position p and optionally resets T1 and T2
to empty trees; an error condition occurs if p is not a leaf.
•int remove(node* p): Removes the node at position p, replacing it with its child (if any), and
returns the element that had been stored at p. An error occurs if p has two children and this
is the case since the tree is not ordered.

Expert Solution

Step by step

Solved in 7 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions