naveed08st

Author Archives: naveed08st

Program to implement a splay tree.

#include <stdio.h> #include <stdlib.h> typedef int key_t; typedef int object_t; typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; object_t *object; /* possibly other information */ } tree_node_t; #define BLOCKSIZE 256 tree_node_t *currentblock = NULL; int size_left; tree_node_t *free_list = NULL; int nodes_taken = 0; int nodes_returned = 0; tree_node_t *get_node() { […]

Continue reading

Program to implement a red-black tree with top-down rebalancing.

#include <stdio.h> #include <stdlib.h> #define BLOCKSIZE 256 typedef int object_t; typedef int key_t; typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; enum {red, black} color; /* possibly other information */ } tree_node_t; tree_node_t *currentblock = NULL; int size_left; tree_node_t *free_list = NULL; tree_node_t *get_node() { tree_node_t *tmp; if( free_list != NULL […]

Continue reading

Program to implement a red-black search tree.

#include <stdio.h> #include <stdlib.h> #define BLOCKSIZE 256 typedef int object_t; typedef int key_t; typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; int height; } tree_node_t; tree_node_t *currentblock = NULL; int size_left; tree_node_t *free_list = NULL; tree_node_t *get_node() { tree_node_t *tmp; if( free_list != NULL ) { tmp = free_list; free_list = […]

Continue reading

Program to implement a weight-balanced search tree.

#include <stdio.h> #include <stdlib.h> #define BLOCKSIZE 256 typedef int object_t; typedef int key_t; typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; int height; } tree_node_t; tree_node_t *currentblock = NULL; int size_left; tree_node_t *free_list = NULL; tree_node_t *get_node() { tree_node_t *tmp; if( free_list != NULL ) { tmp = free_list; free_list = […]

Continue reading

Program to implement a height-balanced search tree.

#include <stdio.h> #include <stdlib.h> #define BLOCKSIZE 256 typedef int object_t; typedef int key_t; typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; int height; } tree_node_t; tree_node_t *currentblock = NULL; int size_left; tree_node_t *free_list = NULL; tree_node_t *get_node() { tree_node_t *tmp; if( free_list != NULL ) { tmp = free_list; free_list = […]

Continue reading

Program to implement a bottom-up optimal search tree.

#include <stdio.h> #include <stdlib.h> #define BLOCKSIZE 256 typedef int object_t; typedef int key_t; typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; } tree_node_t; tree_node_t *currentblock = NULL; int size_left; tree_node_t *free_list = NULL; tree_node_t *get_node() { tree_node_t *tmp; if( free_list != NULL ) { tmp = free_list; free_list = free_list -> […]

Continue reading

Program to implement a top-down optimal search tree.

#include <stdio.h> #include <stdlib.h> #define BLOCKSIZE 256 typedef int object_t; typedef int key_t; typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; } tree_node_t; tree_node_t *currentblock = NULL; int size_left; tree_node_t *free_list = NULL; tree_node_t *get_node() { tree_node_t *tmp; if( free_list != NULL ) { tmp = free_list; free_list = free_list -> […]

Continue reading

Program to implement a trivial search tree, without rebalancing.

#include <stdio.h> #include <stdlib.h> typedef int key_t; typedef int object_t; typedef struct tr_n_t {key_t key; struct tr_n_t *left; struct tr_n_t *right; /* possibly additional information */ } tree_node_t; #define BLOCKSIZE 256 tree_node_t *currentblock = NULL; int size_left; tree_node_t *free_list = NULL; int nodes_taken = 0; int nodes_returned = 0; tree_node_t *get_node() { tree_node_t *tmp; nodes_taken […]

Continue reading

Program to implement an array-based stack with shadow copy.

#include <stdio.h> #include <stdlib.h> typedef int item_t; typedef struct { item_t *base; int size; int max_size; item_t *copy; int copy_size; }stack_t; stack_t *create_stack(int size) { stack_t *st; st = (stack_t *) malloc( sizeof(stack_t) ); st->base = (item_t *) malloc( size * sizeof(item_t) ); st->max_size = size; st->size = 0; st->copy = NULL; st->copy_size = 0; […]

Continue reading

Program to implement a doubly linked list-based queue.

#include <stdio.h> #include <stdlib.h> typedef int item_t; typedef struct qu_t { item_t item; struct qu_t *next; struct qu_t *previous; } queue_t; typedef queue_t node_t; #define BLOCKSIZE 256 node_t *currentblock = NULL; int size_left; node_t *free_list = NULL; node_t *get_node() { node_t *tmp; if( free_list != NULL ) { tmp = free_list; free_list = free_list -> […]

Continue reading