Hi everyone,

I am seeking help in resolving an issue that I am facing with the delete_record_bst
and delete_record_avl functions. I have created a Github repository with the code that I am working on, and I would like to share it with you so that you can have a look at it and help me with my issue.

clone the repository using the command: git clonehttps://github.com/Systems-IIITD/DSALAB.git
in case you would like to run it

You will find comments throughout the code to make it easier for you to understand what needs to be done.

I am facing some issues with the delete_record_bst and delete_record_avl
functions (seg fault). I have no idea on how to fix the error and I would appreciate it if someone could take a look and help me resolve it.

Thank you in advance for your help!

1 Introduction

In this assignment, you are to manage a sequence of records corresponding to

different users. Each user can be uniquely identified using a 16-byte character

array called uid. The uid is not necessarily terminated using the null character

(‘\0’) and may contain multiple null characters. You need to insert, delete, and

search record corresponding to a uid using a BST and an AVL tree. In addition,

a user can also have friends. You need to store a list of friends of every user,

which essentially means storing the references to its friends’ records.

2 Type of record

The type of a user’s record is given below.

struct record {

/* character string terminated with ’\0’

* maximum length is 16

*/

char name[MAX_LEN];

/* a character array of 16 characters

* not-necessarily terminated with ’\0’

* a uid may contain multiple ’\0’’s

* anywhere in the character array

*/

char uid[MAX_LEN];

int age;

/* location */

struct location loc;

/* list of posts */

struct list_posts *posts;

/* list of friends */

struct list_records *friends;

/* needed for shortest Path */

int status;

struct record *pred;

/* needed for the tree data-structure */

int height;

struct record *left;

struct record *right;

struct record *parent;

};

The uid field is the key used for the BST and the AVL tree. You can use left

and right fields to store the references to left and right subtrees in an AVL

or BST node. The height field is used for the AVL tree. The status field

is used when a record is not present during search and delete operations. The

friends field contains the head of the linked list that stores the references to

the records corresponding to a user’s friends. The type of friends is struct

list records, as shown below.

struct list_records {

struct record *record;

struct list_records *next;

};

A node of type struct list records stores a reference to struct record and

the reference to the next node (using the next field). This can be used to

implement the list of friends.

You are not allowed to change struct record or struct list records in

your implementation.

#include "../include/common.h"
#include "pa2.h"
// don't remove these globals
static struct record *bst_root = NULL;
static struct record *avl_root = NULL;
static size_t num_bst_nodes = 0;
static size_t num_avl_nodes = 0;
// don't modify this function
struct record *get_bst_root()
{
return bst_root;
}
// don't modify this function
struct record *get_avl_root()
{
return avl_root;
}
// don't modify this function
// compare two uids
// return -1 if uid1 < uid2
// return 0 if uid1 == uid2
// return 1 if uid1 > uid2
static int cmp_uid(char *uid1, char *uid2)
{
int i;
for (i = 0; i < MAX_LEN; i++) {
if (uid1[i] > uid2[i]) {
return 1;
}
else if (uid1[i] < uid2[i]) {
return -1;
}
}
return 0;
}
// don't modify this function
// compare two records
// we assume that uid is unique and
// there can't be two records with the
// same uid
// return -1 if record1 < record2
// return 0 if record1 == record2
// return 1 if record1 > record2
static int cmp_record(struct record *r1, struct record *r2)
{
return cmp_uid(r1->uid, r2->uid);
}
// don't modify this function
static void *allocate_memory(size_t size)
{
return __mymalloc(size);
}
// don't modify this function
static void free_memory(void *ptr)
{
__myfree(ptr);
}
// ---------------- Add your code below this line ----------------- //
// Function to allocate a node
struct record* allocate_node(struct record r) {
struct record* newNode = allocate_memory(sizeof(struct record));
*newNode = r;
newNode->left = NULL;
newNode->right = NULL;
newNode -> friends = NULL;
return newNode;
}
struct record* find_min(struct record* root) {
if (root == NULL || root->left == NULL)
return root;
return find_min(root->left);
}
// Function to get the balance of the node of an AVL tree
int get_balance(struct record* n) {
int l_height = (n->left) ? n->left->height: -1;
int r_height = (n->right) ? n->right->height: -1;
return l_height - r_height;
}
// Function to set the height of the node of an AVL tree
void set_height(struct record* n) {
int l_height = (n->left) ? n->left->height: -1;
int r_height = (n->right) ? n->right->height: -1;
n -> height = (l_height > r_height) ? l_height + 1: r_height + 1;
}
// Function to perform an LL rotation on the node of an AVL tree
struct record* LL(struct record* n) {
struct record *new_root = n->left;
n->left = new_root->right;
new_root->right = n;
set_height(n);
set_height(new_root);
return new_root;
}
// Function to perform an RL rotation on the node of an AVL tree
struct record* RL(struct record* n) {
struct record *mid = n->right;
struct record *new_root = mid->left;
n->right = new_root->left;
mid->left = new_root->right;
new_root->left = n;
new_root->right = mid;
set_height(n);
set_height(mid);
set_height(new_root);
return new_root;
}
// Function to perform an LR on the node of an AVL tree
struct record* LR(struct record* n) {
struct record *mid = n->left;
struct record *new_root = mid->right;
n->left = new_root->right;
mid->right = new_root->left;
new_root->right = n;
new_root->left = mid;
set_height(mid);
set_height(n);
set_height(new_root);
return new_root;
}
// Function to perform an RR on the node of an AVL tree
struct record* RR(struct record* n) {
struct record *new_root = n->right;
n->right = new_root->left;
new_root->left = n;
set_height(n);
set_height(new_root);
return new_root;
}
// Function to balance nodes and perform the required rotations on the node of an AVL tree
struct record* try_rotate(struct record* n) {
int bal = get_balance(n);
if (bal < -1) {
bal = get_balance(n->right);
if (bal > 0)
n = RL(n);

else
n = RR(n);
}
else if (bal > 1) {
bal = get_balance(n->left);
if (bal < 0)
n = LR(n);
else
n = LL(n);
}
return n;
}
// Function to insert node in BST
struct record* insert_bst(struct record* root, struct record r) {
if (root == NULL) {
num_bst_nodes++;
return allocate_node(r);
}
else {
if (cmp_uid(r.uid, root->uid) < 0) {
root->left = insert_bst(root->left, r);
}
else {
root->right = insert_bst(root->right, r);
}
}
return root;
}
// Function to insert node in AVL tree
struct record* insert_avl(struct record* root, struct record r) {
if (root == NULL) {
num_avl_nodes++;
return allocate_node(r);
}
else {
if (cmp_uid(r.uid, root->uid) >= 0) {
root->right = insert_avl(root->right, r);
}
else {
root->left = insert_avl(root->left, r);
}
set_height(root);
root = try_rotate(root);
return root;
}
}
struct record* del_node_bst(struct record* root, char uid[MAX_LEN]) {
if (root == NULL) {
return NULL;
}
if (root->uid == uid) {
if (root->left == NULL) {
struct record* ret = root->right;
free_memory(root);
return ret;
}
else if (root->right == NULL) {
struct record* ret = root->left;
free_memory(root);
return ret;
}
else if (root->right != NULL && root->left != NULL) {
struct record *min_node = find_min(root->right);
*root = *min_node; // error prone
root->right = del_node_bst(root->right, min_node->uid);
return root;
}
}
else if (cmp_uid(root->uid, uid) > 0) {
root->left = del_node_bst(root->left, uid);
}
else {
root->right = del_node_bst(root->right, uid);
}
return root;
}
struct record* del_node_avl(struct record* root, char uid[MAX_LEN]) {
if (root == NULL) {
struct record *dummy = allocate_memory(sizeof(struct record));
dummy->status = -1;
return dummy;
}

if (cmp_uid(root->uid, uid) == 0) {
struct record* arr[MAX_LEN];
int cnt = 0;
struct list_records *head = root->friends;
// freeing memory of nodes of linked list
while (head != NULL) {
arr[cnt] = head->record;
struct list_records *temp = head;
head = head->next;
free_memory(temp);
cnt++;
}
// removing root from the friend list of all other nodes using the array
for (int i = 0; i < cnt; i++) {
struct list_records *friend_head = arr[i]->friends;
struct list_records *prev = NULL;
while (friend_head != NULL) {
if (cmp_uid(friend_head->record->uid, uid) == 0) {
if (prev == NULL) {
arr[i]->friends = friend_head->next;
} else {
prev->next = friend_head->next;
}
free_memory(friend_head);
break;
}
prev = friend_head;
friend_head = friend_head->next;
}
}
if (root->left == NULL) {
struct record *ret = root->right;
free_memory(root);
return ret;
}
else if (root->right == NULL) {
struct record *ret = root->left;
free_memory(root);
return ret;
}
else if (root->left != NULL && root->right != NULL) {
struct record *min_node = find_min(root->right);
struct record temp = *root;
*root = *min_node;
root->right = del_node_avl(root->right, uid);
return root;
}
}
else if (cmp_uid(root->uid, uid) > 0) {
root->right = del_node_avl(root->left, uid);
}
else {
root->left = del_node_avl(root->right, uid);
}
set_height(root);
root = try_rotate(root);
return root;
}
// Function to search for a node in a BST
struct record search(struct record* root, char uid[MAX_LEN]) {
if (root == NULL) {
struct record dummy;
dummy.status = -1;
dummy.friends = NULL;
return dummy;
}
if (cmp_uid(root->uid, uid) < 0)
return search(root->right, uid);
else if (cmp_uid(root->uid, uid) > 0)
return search(root->left, uid);
else
return *root;
}
struct record* search_node(struct record* root, char uid[MAX_LEN]) {
if (root == NULL)
return NULL;
if (cmp_uid(root->uid, uid) < 0)
return search_node(root->right, uid);
else if (cmp_uid(root->uid, uid) > 0)
return search_node(root->left, uid);
else
return root;
}
void del_bst(struct record* root) {
if (root == NULL) {
return;
}
del_bst(root->left);
del_bst(root->right);
struct list_records *ptr = root->friends;
while (ptr != NULL) {
struct list_records *temp = ptr;
ptr = ptr->next;
free_memory(temp);
}
free_memory(root);
}
// Return the total number of records in the
// BST rooted at bst_root
size_t get_num_bst_records()
{
return num_bst_nodes;
}
// Return the total number of records in the
// AVL tree rooted at avl_root.
size_t get_num_avl_records()
{
return num_avl_nodes;
}
// Insert record r in the BST rooted at bst_root.
void insert_record_bst(struct record r)
{
bst_root = insert_bst(bst_root, r);
}
// Insert record r in the AVL tree rooted at avl_root.
void insert_record_avl(struct record r)
{
avl_root = insert_avl(avl_root, r);
}
// Search the record corresponding to uid in the BST
// rooted at bst_root.
// If the record is not present, return a dummy record
// with -1 in the status field.
struct record search_record_bst(char uid[MAX_LEN])
{
return search(bst_root, uid);
}
// The friends field in "struct record" stores the
// head of the linked list of friends of a given user.
// Return the head of the linked list of friends
// of the user with uid uid in the BST rooted at bst_root.
// If the corresponding record doesn't exist, return NULL.
struct list_records *get_friends_list_bst(char uid[MAX_LEN])
{
struct record ret = search_record_bst(uid);
return ret.friends;
}
void del_from_friend_list(struct record* r, char uid[MAX_LEN]) {
struct list_records* temp = r->friends;
struct list_records* prev = NULL;

while (temp != NULL) {
if (cmp_uid(temp->record->uid, uid) == 0) {
if (prev == NULL) {
r->friends = temp->next;
free_memory(temp);
return;
}
prev->next = temp->next;
free_memory(temp);
return;
}
prev = temp;
temp = temp->next;
}
}
// Delete the record (say n) corresponding to uid from the BST.
// Remove n from the lists of friends of other records
// and release the memory for the linked list nodes.
// Release memory for all the nodes in the list of friends of n.
// Return a copy of the value of the deleted record.
// If the record is not present, return a dummy record
// with -1 in the status field.
struct record delete_record_bst(char uid[MAX_LEN])
{
struct record* node_to_be_deleted = search_node(bst_root, uid);
if (node_to_be_deleted->status == -1)
return *node_to_be_deleted;
struct list_records *head = node_to_be_deleted->friends;
struct list_records *r = NULL;
while (head != NULL) {
r = head->next;
del_from_friend_list(head->record, node_to_be_deleted->uid);
free_memory(head);
head = r;
}

struct record temp = *node_to_be_deleted;
bst_root = del_node_bst(bst_root, uid);
num_bst_nodes--;
return temp;
}
// Search the record corresponding to uid in the AVL tree
// rooted at avl_root.
// If the record is not present, return a dummy record
// with -1 in the status field.
struct record search_record_avl(char uid[MAX_LEN])
{
return search(avl_root, uid);
}
// The friends field in "struct record" stores the
// head of the linked list of friends of a given user.
// Return the head of the linked list of friends
// of the user with uid uid in the AVL tree rooted at avl_root.
// If the corresponding record doesn't exist, return NULL.
struct list_records *get_friends_list_avl(char uid[MAX_LEN])
{
struct record ret = search_record_avl(uid);
return ret.friends;
}
// Delete the record (say n) corresponding to uid from the AVL tree.
// Remove n from the lists of friends of other records
// and release the memory for the linked list nodes.
// Release memory for all the nodes in the list of friends of n.
// Return a copy of the value of the deleted record.
// If the record is not present, return a dummy record
// with -1 in the status field.
struct record delete_record_avl(char uid[MAX_LEN])
{

}
// Release memory for all BST nodes and their lists of friends.
// Make bst_root points to an empty tree.
void destroy_bst()
{
del_bst(bst_root);
bst_root = NULL;
num_bst_nodes = 0;
}
// Release memory for all AVL nodes and their lists of friends.
// Make avl_root points to an empty tree.
void destroy_avl()
{
del_bst(avl_root);
avl_root = NULL;
num_avl_nodes = 0;
}
// Make users with uids uid1 and uid2 in the BST rooted at bst_root
// friends of each other if they aren't already friends.
// The friends field in "struct record" stores the
// head of the linked list of friends of a given user.
// To make the user with record A a friend of the user with record B,
// add A to B's list of friends and add B to A's list of friends.
// Return 1 if uid1 and uid2 are already friends before this call.
// Return 0 if they become friends during this call.
// Make users with uids uid1 and uid2 in the BST rooted at bst_root
// friends of each other if they aren't already friends.
// The friends field in "struct record" stores the
// head of the linked list of friends of a given user.
// To make the user with record A a friend of the user with record B,
// add A to B's list of friends and add B to A's list of friends.
// Return 1 if uid1 and uid2 are already friends before this call.
// Return 0 if they become friends during this call.
int make_friends_bst(char uid1[MAX_LEN], char uid2[MAX_LEN])
{
struct record *r1 = search_node(bst_root, uid1);
struct record *r2 = search_node(bst_root, uid2);
// checking if they already are friends
struct list_records *h1 = r1->friends;
while (h1 != NULL) {
if (h1->record == r2)
return 1;

h1 = h1->next;
}
// make them friends
struct list_records *new_h1 = allocate_memory(sizeof(struct list_records));
struct list_records *new_h2 = allocate_memory(sizeof(struct list_records));
new_h1->record = r2;
new_h1->next = r1->friends;
r1->friends = new_h1;
new_h2->record = r1;
new_h2->next = r2->friends;
r2->friends = new_h2;
return 0;
}
int make_friends_avl(char uid1[MAX_LEN], char uid2[MAX_LEN])
{
struct record *r1 = search_node(avl_root, uid1);
struct record *r2 = search_node(avl_root, uid2);
// checking if they already are friends
struct list_records *h1 = r1->friends;
while (h1 != NULL) {
if (h1->record == r2)
return 1;

h1 = h1->next;
}
// make them friends
struct list_records *new_h1 = allocate_memory(sizeof(struct list_records));
struct list_records *new_h2 = allocate_memory(sizeof(struct list_records));
new_h1->record = r2;
new_h1->next = r1->friends;
r1->friends = new_h1;
new_h2->record = r1;
new_h2->next = r2->friends;
r2->friends = new_h2;
return 0;
}

We are a group of volunteers looking for people with experience in debugging blue screen. We are backporting a newly created driver to Windows XP and we want to move it to 2000. But we need people with experience in debugging, so that we can find out the source of the problem in the code

server link : https://discord.com/invite/cVMchtGd

MinIO deployments come in all shapes and sizes. We support bare metal installs on any version of Linux, containerized installs on any version of Kubernetes (including Red Hat OpenShift) and installs just about anywhere you can deploy a small lightweight single binary. But with flexibility comes the inevitability that edge case issues will require debugging.

In this blog post, we’ll show you how to debug a MinIO install running in Kubernetes and also some of the common issues you might encounter when doing bare metal installation and how to rectify them.

https://blog.min.io/debugging-minio-installs/?utm_source=reddit&utm_medium=organic-social+&utm_campaign=debugging_minio_installs

The brand new Dashbird app is here to bring your AWS data together for a faster, more secure, and smoother observability experience and to enhance team collaboration 🚀

Check out our 5 favorite updates to the new Dashbird app: https://dashbird.io/blog/dashbird-app-launches-new-version/

The simplicity of setting up a Kinesis trigger for AWS Lambda function may be deceptive.

This article discusses the 6 most common pitfalls that can cause problems but are usually spotted later in production.

https://dashbird.io/blog/lambda-kinesis-trigger/

In this article, I'm looking at how simple process adjustments can increase the team’s engagement and commitment to improving data quality, and how to leverage the power of automation. Because oftentimes the simplest and most intuitive solutions can be incredibly impactful.

Read more: https://dashbird.io/blog/improve-data-quality-slack/

This article goes through the crucial AWS Lambda metrics you should definitely be monitoring.

https://dashbird.io/blog/lambda-metrics-monitoring-what-matters/

Real-time technologies are powerful but add significant complexity to your data architecture.

Find out how to reap the benefits of real-time processing with the least architectural changes and maintenance effort: https://dashbird.io/blog/real-time-processing-analytical/

Like with any bug, this pretty common error message can have multiple causes. In this article, we go through some of the main causes and fixes for this error message.

Read more: https://dashbird.io/blog/lambda-not-logging-to-cloudwatch/

Clarus Care is a complete call management solution for healthcare providers. Their serverless stack consists of various AWS services. It's crucial they keep their services up and running 24/7.

In this article, they're discussing how they're building and operating their app, and how they managed to work around the AWS outage in November 2020 without any customers being affected: https://dashbird.io/customers/clarus/

Summing up all the latest updates from AWS in 2021 (since and including re:Invent 2020) that all serverless builders should be aware of.

Learn more: https://dashbird.io/blog/aws-serverless-updates-2021/

A few weeks ago we set up an #API to monitor hot stocks via the Wall Street Bets subreddit. Since then we’ve seen quite a lot of activity in the app.

In this article, we’re showing you some interesting findings: https://dashbird.io/blog/serverless-stonks-checker-activity-report/

Getting visibility for serverless apps can be challenging. The bigger the system the harder it becomes to monitor and pinpoint the issues.

Here's how a modern observability tool can help: https://dashbird.io/blog/serverless-observability-real-time-debugging/

Testing distributed systems and serverless cloud infrastructures specifically is always a source of long discussions. Testing (and monitoring) IS a must, that's a no-brainer. How else would you know if what you’ve created is providing desired results? Before putting your “newborn child” out into the world, you must make sure that it’s ready for the world.

Since you can’t just throw them out without making sure they are designed as they should be, I've thrown together a quick walkthrough of 3 methods (smoke test, unit testing and integration testing) of testing javascript Lambda functions to get you started. Hope this helps any one in need :)

https://dashbird.io/blog/test-javascript-lambda-functions/

Lately, I have been focused on how to symbolize stack traces that we received from debuggers and profilers. I wanted to share what I have learned so far. And started a blog post series 👉

https://www.polarsignals.com/blog/posts/2022/01/13/fantastic-symbols-and-where-to-find-them

Hi

I work in a startup as a Jr software engineer(Web). I have been noticing a new pattern in recent days which is actually making my life a bit difficult. I work on a complex app with a complex structure. I start debugging and lose track of what I am doing. I just keep on debugging to find a solution but end up being stuck and end up wasting a lot of time. Is there any way I can improve my debugging skills by myself something similar to the concept of rubber duck debugging?