Create an AVL Tree as a C++ class called AVLTree. Implement smart pointers weak_
ID: 3727467 • Letter: C
Question
Create an AVL Tree as a C++ class called AVLTree. Implement smart pointers weak_ptr and shared_ptr, which are built to help to manage memory.
Abide by the following rules if you wish to modify my BST tree to implement your AVL tree in C++:
If v is a parent of u, then u has a std::weak_ptr that points to v.
If w is a child of u, then u has a std::shared_ptr that points to w.
Use std::shared_ptr to modify what is being pointed to. In order to do this for a parent, you must convert a std::weak_ptr to a std::shared_ptr using lock.
To check for an empty smart pointer, compare a std::shared_ptr to nullptr.
A std::weak_ptr may not be assigned nullptr; instead, use reset to have a std::weak_ptr "point to null".
Implement the following as well:
- Insert Implement an Insert function that utilizes the rotations as described at Geeks- ForGeeks: https://www.geeksforgeeks.org/?p=17679
- Deletion Implement a Delete function as described at GeeksForGeeks: https://www.geeksforgeeks.org/avl-tree-set-2-deletion/
Note that the article links to BST deletion: https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/
When a node is deleted in a BST, if it has two children, either the inorder successor or the inorder predecessor is copied. Either choice is fine for this programming assignment.
- DeleteMin Implement a DeleteMin function which deletes the minimum key in the AVL tree. Any implementation that runs in O(log n) time is acceptable.
The input will be in the form of a JSON file, and output should be printed to the screen.
Explanation / Answer
#include <iostream>
using namespace std;
struct Root
{
int val;
struct Root *l;
struct Root *r;
int h;
};
int max(int a, int b)
{
if(a>b)
{
return a;
}
else
{
return b;
}
}
int h(struct Root *N)
{
if (N == NULL)
return 0;
return N->h;
}
struct Root* newRoot(int val)
{
struct Root* Root = (struct Root*)malloc(sizeof(struct Root));
Root->val = val;
Root->l = NULL;
Root->r = NULL;
Root->h = 1;
return(Root);
}
struct Root *rRotate(struct Root *y)
{
struct Root *x = y->l;
struct Root *T2 = x->r;
x->r = y;
y->l = T2;
y->h = max(h(y->l), h(y->r))+1;
x->h = max(h(x->l), h(x->r))+1;
return x;
}
struct Root *lRotate(struct Root *x)
{
struct Root *y = x->r;
struct Root *T2 = y->l;
y->l = x;
x->r = T2;
x->h = max(h(x->l), h(x->r))+1;
y->h = max(h(y->l), h(y->r))+1;
return y;
}
int getBalance(struct Root *N)
{
if (N == NULL)
return 0;
return h(N->l) - h(N->r);
}
struct Root* insert(struct Root* Root, int val)
{
if (Root == NULL)
return(newRoot(val));
if (val < Root->val)
Root->l = insert(Root->l, val);
else if (val > Root->val)
Root->r = insert(Root->r, val);
else
return Root;
Root->h = 1 + max(h(Root->l),
h(Root->r));
int balance = getBalance(Root);
if (balance > 1 && val < Root->l->val)
return rRotate(Root);
if (balance < -1 && val > Root->r->val)
return lRotate(Root);
if (balance > 1 && val > Root->l->val)
{
Root->l = lRotate(Root->l);
return rRotate(Root);
}
if (balance < -1 && val < Root->r->val)
{
Root->r = rRotate(Root->r);
return lRotate(Root);
}
return Root;
}
struct Root * minValueRoot(struct Root* Root)
{
struct Root* current = Root;
while (current->l != NULL)
current = current->l;
return current;
}
struct Root* deleteRoot(struct Root* root, int val)
{
if (root == NULL)
return root;
if ( val < root->val )
root->l = deleteRoot(root->l, val);
else if( val > root->val )
root->r = deleteRoot(root->r, val);
else
{
if( (root->l == NULL) || (root->r == NULL) )
{
struct Root *temp = root->l ? root->l :
root->r;
if (temp == NULL)
{
temp = root;
root = NULL;
}
else
*root = *temp;
free(temp);
}
else
{
struct Root* temp = minValueRoot(root->r);
root->val = temp->val;
root->r = deleteRoot(root->r, temp->val);
}
}
if (root == NULL)
return root;
root->h = 1 + max(h(root->l),
h(root->r));
int balance = getBalance(root);
if (balance > 1 && getBalance(root->l) >= 0)
return rRotate(root);
if (balance > 1 && getBalance(root->l) < 0)
{
root->l = lRotate(root->l);
return rRotate(root);
}
if (balance < -1 && getBalance(root->r) <= 0)
return lRotate(root);
if (balance < -1 && getBalance(root->r) > 0)
{
root->r = rRotate(root->r);
return lRotate(root);
}
return root;
}
void preOrder(struct Root *root)
{
if(root != NULL)
{
printf("%d ", root->val);
preOrder(root->l);
preOrder(root->r);
}
}
struct Root* DeleteMin(struct Root* root)
{
int min;
struct Root* temp = root;
while(temp->l!=NULL)
{
temp = temp->l;
min = temp->val;
}
printf("Deleting %d node ",min);
root = deleteRoot(root, min);
}
int main()
{
struct Root *root = NULL;
root = insert(root, 9);
root = insert(root, 5);
root = insert(root, 10);
root = insert(root, 0);
root = insert(root, 6);
root = insert(root, 11);
root = insert(root, -1);
root = insert(root, 1);
root = insert(root, 2);
printf("Preorder traversal of AVL tree ");
preOrder(root);
printf(" ");
root = DeleteMin(root);
printf(" Preorder traversal after DeleteMin ");
preOrder(root);
printf(" ");
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.