| tree.c |
| /*************************************************************************** * * * Tree Program in C * * * * COSC 242 Assignment 20/09/01 * * * * JAMES LITTLE * * * ***************************************************************************/ #include <stdio.h> #include <stdlib.h> #include "tree.h" #include "mylib.h" /************************** * * * IS_RED * * IS_BLACK * * * ************************** These are obviously not function calls, but they do evaluate in the same manner. These are macros that are pre-processed into the C code and enforce robust coding, through simplification of common statements. In a sense returning a boolean value depending on what the actual colour of the node is. PARAMETERS: x = the tree node to be tested. RETURN VALUE: some boolean value. */ #define IS_BLACK(x) ((NULL == x) || (BLACK == x->colour)) #define IS_RED(x) ((NULL != x) && (RED == x->colour)) typedef enum colour_e { RED, BLACK } colour_t; struct treenode { char *key; colour_t colour; tree left; tree right; }; /************************** * * * tree_new * * * ************************** A better name would be tree_null, since all this function call achieves is the return of a NULL value. RETURN VALUE: NULL. */ tree tree_new(){ return NULL; } /************************** * * * tree_search * * * ************************** Searching a binary tree is a simple exercise. Start at the root and move left or right, depending on whether the value you are seeking is less than or greater than that node. PARAMETERS: b = the root of the tree we are searching. Or the current node to look into. key = the character string to look for. RETURN VALUE: a pointer of type char, or a character string, the one we were looking for hopefully. */ char *tree_search(tree b, char *key){ if(b == NULL) return NULL; /* strcmp(cs,ct) returns 0 if cs==ct strcmp(cs,ct) returns <0 if cs<ct strcmp(cs,ct) returns >0 if cs>ct */ if(!strcmp(key, b->key)) return b->key; else if(strcmp(key, b->key)<0) return tree_search(b->left, key); else return tree_search(b->right, key); } /************************** * * * tree_insert * * * ************************** This function creates the tree. And returns a valid tree, as opposed to the tree_new function that only returns NULL. Every node in a tree is a tree in its own right. This fact allows the function to recursively search for a NULL node and create a tree in its place, hence the same function is required for an empty tree as is required for a non-empty tree. Not if, but when a NULL node is discovered, space from the heap is allocated to the tree-node. The key is copied into the key field of the node and both siblings of the node are initialised to NULL. Initialisation of the siblings to NULL is required so that sibling nodes may be attached at some later stage. Otherwise in true C fashion, both siblings would hold garbage and that wouldn't be fun. Initialising the colour of the newly created node to red is required by RBT insertion. Colour initialisation is not required by BST insertion, but it doesn't hinder program functionality either. The only required difference between RBT and BST insertion is that following RBT insertion, the tree must be checked for compatibility with RBT properties. This requires the use of the rbt_fix function. This function is repeatedly called as the recursion unwinds. PARAMETERS: b = the root of the tree we are searching. Or the current node to look into. key = the character string to look for. rb_insert = indicates if RBT insertion should be used or standard BST insertion. RETURN VALUE: the updated tree. */ tree tree_insert(tree b, char *key, int rb_insert){ if(b == NULL){ b = emalloc(sizeof *b); b->key = emalloc((strlen(key)+1) * sizeof (char)); strcpy(b->key, key); b->colour = RED; b->left = NULL; b->right = NULL; } else if(strcmp(key, b->key)<0) b->left = tree_insert(b->left, key, rb_insert); else if(strcmp(key, b->key)>0) b->right = tree_insert(b->right, key, rb_insert); if(rb_insert) b = tree_fix(b); return b; } /************************** * * * right_rotate * * * ************************** To explain right rotation: We pull the left child of r up, so r is now its left child's right child. A graphical representation: (r) (r->left') / \ ===> / \ (r->left) (r->right) (r->l->l') (r') / \ / \ (r->l->l) (r->l->r) (r->l->r') (r->right') I use a ' to indicate that this is no longer referred to by this name, but that it was previously this node. PARAMETERS: r = the node that will be moved and others will rotate. RETURN VALUE: a rotated tree. */ static tree right_rotate(tree r){ if(r != NULL && r->left != NULL){ tree temp = r; r = r->left; temp->left = r->right; r->right = temp; } return r; } /************************** * * * left_rotate * * * ************************** The opposite of right rotation. PARAMETERS: r = the node that will be moved and others will rotate. RETURN VALUE: a rotated tree. */ static tree left_rotate(tree r){ if(r != NULL && r->right != NULL){ tree temp = r; r = r->right; temp->right = r->left; r->left = temp; } return r; } /************************** * * * tree_fix * * * ************************** It is important that our red black trees conform to the red black tree properties: Black height is equal for all leaves, no red node has red siblings, and perhaps less importantly: a root node is black. Here we make sure that these properties hold. If they are broken, then we fix it up: If a child is red, and has a red child, then the action depends on the color of the lower red child's "uncle" [or aunty]. If the uncle is red, re-colour the initial node red, and its children black. If a left child is red and has a red left child, and the right child is black. Then right rotate self and colour self black and children red. In the opposite case [red right child and has red right child, and the left child is black], left rotate self and colour self black and children red. If the left child and its right child are red, and the right child is black. We left rotate the left child, this puts us into the above situation, so we use the same code and right rotate self and colour self black and children red. Again the opposite situation follows a similar algorithm: If the right child and its left child is red, and the left child is black. We right rotate the right child, left rotate self and colour self black and children red. PARAMETERS: r = the node that should be examined. RETURN VALUE: a correct RBT tree. */ static tree tree_fix(tree r){ if(r == NULL) return NULL; if(IS_RED(r->left) && (IS_RED(r->left->left) || IS_RED(r->left->right))){ if(IS_RED(r->right)){ r->colour = RED; r->left->colour = BLACK; r->right->colour = BLACK; } else { if(IS_RED(r->left->right)) r->left = left_rotate(r->left); r = right_rotate(r); r->colour = BLACK; r->right->colour = RED; } } else if(IS_RED(r->right) && (IS_RED(r->right->left) || IS_RED(r->right->right))){ if(IS_RED(r->left)){ r->colour = RED; r->left->colour = BLACK; r->right->colour = BLACK; } else { if(IS_RED(r->right->left)) r->right = right_rotate(r->right); r = left_rotate(r); r->colour = BLACK; r->left->colour = RED; } } return r; } /************************** * * * black_height * * * ************************** Outputs the black height and height of each leaf. PARAMETERS: t = tree to calculate height of. RETURN VALUE: The average height of the tree. */ int black_height(tree t, int bh, int h){ static int h_sum = 0; static int num = 0; if(t == NULL){ printf("black height :: %d\ttotal height is :: %d\n", bh, h); } else { if(t->left == NULL && t->right == NULL){ num++; h_sum += h; } h++; if(IS_BLACK(t)) bh++; black_height(t->left, bh, h); black_height(t->right, bh, h); } return h_sum/num; } /************************** * * * tree_inorder * * * ************************** Uses the function passed to do something to the tree in order, lowest to highest. PARAMETERS: b = the current node to look into. f = the function that implements some functionality. RETURN VALUE: NONE. */ void tree_inorder(tree b, void f(char *s)){ if(b == NULL) return; tree_inorder(b->left, f); f(b->key); tree_inorder(b->right, f); } /************************** * * * tree_preorder * * * ************************** Prints nodes down the left side of a tree first, then the right side. PARAMETERS: b = the current node to look into. f = the function that implements some functionality. RETURN VALUE: NONE. */ void tree_preorder(tree b, void f(char *s)){ if(b == NULL) return; f(b->key); /* REMOVED FOR ASSIGNMENT printf("%c :: %s\n", (IS_BLACK(b))? 'B' : 'R', b->key); */ tree_preorder(b->left, f); tree_preorder(b->right, f); } /************************** * * * tree_postorder * * * ************************** Moves down the left side of a tree first, then the right side, then starts printing nodes. PARAMETERS: b = the current node to look into. f = the function that implements some functionality. RETURN VALUE: NONE. */ void tree_postorder(tree b, void f(char *s)){ if(b == NULL) return; tree_postorder(b->left, f); tree_postorder(b->right, f); f(b->key); } /************************** * * * tree_delete * * * ************************** Only used for BST tree [have not implemented a tree delete algorithm for RBT] Rather simple algorithm in comparison to RBT insertion. We look for the key in a binary search style down the tree. If we come to a NULL node then it does not exist. If we find it, then we delete it. If it has no children then we can just free its memory space. If it has one child then we free its memory space and make the node point to its child. If it has two children, then we look for the lowest valued node in its right tree and replace it with that. PARAMETERS: b = the root of the tree we are searching. Or the current node to look into. key = what we are looking for. RETURN VALUE: a tree that possibly has one less node. */ tree tree_delete(tree b, char *key){ /* Key does not exist */ if(b == NULL) return NULL; if(strcmp(key, b->key)<0) /* Key may be in the left sub tree */ b->left = tree_delete(b->left, key); else if(strcmp(key, b->key)>0) /* Key may be in the right sub tree */ b->right = tree_delete(b->right, key); else { /* We have found it, now eradicate it! */ tree temp = NULL; if(b->left!=NULL && b->right!=NULL){ temp = b->right; while(temp->left!=NULL) temp = temp->left; free(b->key); b->key = emalloc((strlen(temp->key)+1) * sizeof (char)); strcpy(b->key, temp->key); b->right = tree_delete(b->right, key); } else { if(b->left!=NULL) temp = b->left; else temp = b->right; free(b->key); free(b); b = temp; } } return b; } |
| James Little |