Resorting a binary search tree

[can_surmeli]

Hi.

I've a BST created for an address book application for my term project.

When inserting into the BST, I insert items sorted by their first names in ascending order.

The thing is that the user should be able to display the BST in the ascending form of last names & birthdays as well.

My solution to that is inserting items from the BST into a new BST in the sorted form of last names in ascending order. Besides that I've no idea about how to sort by birthdays.

So I've coded something for sorting by last name. It uses my insert into the BST code with the change of sorting by last names.

//
//  sort_by_last_name.h
//  Project
//
//  Created by Can Sürmeli on 5/12/11.
//  Copyright 2011 __MyCompanyName__. All rights reserved.
//
//  PURPOSE: Sorts according to last names

struct tree_node  *sort_by_last_name(struct tree_node *node, struct tree_node *last_name_node) {
	
	// if there is no root
	if( last_name_node == NULL )
		last_name_node = create_node(NULL, NULL, node->data);
	
	
	// if there is a root & the new entry should be placed before the root
	else if( strcmp(last_name_node->data.last_name, node->data.last_name) < 0 )
		last_name_node->left = sort_by_last_name(node, last_name_node->left);
	
	
	// if there is a root & the new entry should be places after the root
	else if ( strcmp(last_name_node->data.last_name, node->data.last_name) > 0 )
		last_name_node->right = sort_by_last_name(node, last_name_node->right);
	
	
	// if there is a root & the last names are identical
	else {
		// if it should be placed before the root
		if ( strcmp(last_name_node->data.phone, node->data.phone) < 0 )
			last_name_node->left = sort_by_last_name(node, last_name_node->left);
	
		
		// if it should be places after the root
		else if( strcmp(last_name_node->data.phone, node->data.phone) > 0 )
			last_name_node->right = sort_by_last_name(node, last_name_node->right);
	
		
		// if the entries are the same
		else
			return last_name_node;
	}
	
	
	return last_name_node;
	
}

//
//  create_node.h
//  Proje
//
//  Created by Can Sürmeli on 4/29/11.
//  Copyright 2011 __MyCompanyName__. All rights reserved.
//
//  PURPOSE: Creates a node

struct tree_node *create_node(struct tree_node *a, struct tree_node *b, ENTRY contact) {
	
	struct tree_node *newNode;
	
	
	newNode = (struct tree_node *)(malloc(sizeof(struct tree_node)));
	
	newNode->data = contact;
	newNode->left = a;
	newNode->right = b;
	
	return newNode;
	
}

Also here are my structures:

//
//  structure.h
//  Proje
//
//  Created by Can Sürmeli on 4/25/11.
//  Copyright 2011 __MyCompanyName__. All rights reserved.
//
//  PURPOSE: Structures

// The structure of a contact(single entry) in the address book
typedef struct entry{
	
	char first_name[15];
	char last_name[10];
	char date_of_birth[11];
	char e_mail[25];
	char phone[15];
	char address[50];
	char city[15];
	char zipcode[6];
	struct contact *next;
	
}ENTRY;



// The structure of a single node in the tree structure
struct tree_node {
	ENTRY data;
	struct tree_node *left;
	struct tree_node *right;
};

But it's not working! :(( It just takes the first item and stops.

What am I doing wrong here?

Or is there a better solution than sorting again the BST?

Also what is your idea about sorting the records in the address book by birthdays? How can I determine which one is bigger or smaller?

Thanks.

[Narue]

Sorting a binary search tree means rebuilding it completely, because the structure depends on a relational comparison of the key. If your address book isn't large, you'd probably be better off simply using an array and sorting it as necessary, with a binary search (bsearch) to keep lookups snappy.

If you're looking at enough records to make an array-based solution prohibitive, a relational database should start to be considered over in-memory data structures. However, it's not terribly difficult to solve this problem in a simple way. One decent way would have you maintaining a search data structure for each comparison method, with the data structures storing pointers to a base array or list. So for your address book you would have a base list holding the records, then for example, a tree ordered by first name, a tree ordered by last name, and a tree ordered by birthday with pointers to the base list. A search or traversal on a specified key will use the appropriate tree for the key type.

The most obvious problem with this approach is that it's not scalable. The more keys you add, the more search data structures you're forced to maintain. If that's a problem you need to start getting creative, which probably isn't appropriate for a school project. ;)

One creative option is swapping out your trees for a multi-dimensional data structure such as a kd-tree. These can be used for multiple indexing. One issue here is that multi-dimensional data structures tend to be focused on homogeneous data like points in 2D or 3D space, so you'd be using them from a higher level of abstraction which might be beyond your current skill level.

My personal opinion is that relational database is the easiest and most scalable solution to this problem. But since it's a school project, you probably don't need to worry about achieving any kind of production quality performance or scalability and can use the simplest approach (a sorted array).

[can_surmeli]

This is the term project of CSE 211. In other words: Data Structures.

It's only a basic introduction to the data structures. We haven't seen all of the data structures here. So we don't know kd-trees. Therefore I cannot use it in my project.

More than that. A relational database, even though it sounds lovely because it would be a whole lot easier, is impossible because we haven't ever seen it in this lecture. It's for the databases lesson.

The size of my BST changes. It's not static. Our instructor expects us to build a program that is efficient. So I can't choose a method depends on record size. If he wants me to demo it to him with a lot of records and if the project is not efficient I might lose points because of that.

Anyway. Couldn't I just insert my data stored in the BST into a new BST to be sorted by their last name as I've mentioned before? If so my only problem remains inserting only one value to the new BST since my current code only reads the first node of the tree? How can I make it go on?

[Narue]

Couldn't I just insert my data stored in the BST into a new BST to be sorted by their last name as I've mentioned before?

Yes, you could. This is the option where you maintain a tree for each separate key.

If so my only problem remains inserting only one value to the new BST since my current code only reads the first node of the tree?

You're making a copy of all nodes in the tree, and using a different key for comparison. That means unless you're inserting each record into multiple trees as they come, you'll need to traverse the tree and actually make a copy when it's needed:

void copy_by_last_name(struct tree_node *root, struct tree_node **new_tree)
{
    if (root != NULL) {
        copy_by_last_name(root->left, new_tree);
        *new_tree = insert_by_last_name(*new_tree, root->data);
        copy_by_last_name(root->right, new_tree);
    }
}

[TrustyTony]

It would pay to separate your data pay load from node as in that case you could have pointer to same info and do not need only have three pointers twice instead of two pointers and much string data. So I think you should use pointer to entry not entry in node. This I was thinking already reading your old question, but I had not clear reason for my opinion, now I have.

Remember to update the whole "forest" after you have many trees. If you had freedom to choose, I think Narue is correct about sorting array in different orders. Binary search can be incredibly fast with current machines. Same thing of pointers to entrys does apply there also. You could change my array version to user dynamic data allocation and quick sort it ready. If you would feel the speed of sorting, you could probably insert sort faster than user notice repeatedly after adding of new data (removing do not need resort).

[can_surmeli]

WOOOOHOOOO.

I succeeded. I finally achieved what I wanted.

Thank you guys. You're great.

One more thing since I'm clueless in this as well: How can I do the sorting by birthdays? I mean how can I determine which birthday is bigger or smaller? Is there a function for that? Or should I code something?

[Narue]

The standard time.h library is what you want. First convert the date from whatever format it's in to a tm struct, then convert the tm struct to a time_t value, and from there you can use difftime() to compare the dates.

[TrustyTony]

Also if you have date in format "yyyymmdd" it sorts OK as string.

[can_surmeli]

Also if you have date in format "yyyymmdd" it sorts OK as string.

Is it okay to have separators in between?

[TrustyTony]

If you can quarantee exactly same format, including no spaces. Always four numbers year and two numbers for month and day.