Naučíme tě pracovat na home-office.

Zjistit více...

avl.c

#include "dictionary_api.h"
#include <stdlib.h>
#include <string.h>
#define MAX(x,y) ( (x<y) ? y : x)
#define HL(x) ( (x->l ? x->l->h : -1) )
#define HR(x) ( (x->r ? x->r->h : -1) )

typedef int val_t;

typedef struct AVLTree 
{
	void (*avl_insert)(struct AVLTree *avl, char *key, val_t data);
	val_t *(*avl_lookup)(struct AVLTree *tree, char *key);
	void (*avl_delete)(struct AVLTree *avl, char *key);
	void (*avl_destroy)(struct AVLTree *tree);
	void(*avl_inspect)(struct AVLTree *tree);
	struct node *root;
} AVLTree;

Dictionary * Dictionary_new(AVLTree * d)
{
	AVLTree * out = malloc(sizeof(Dictionary));
	*out = *d;
	return out;
}

typedef struct node 
{
	struct node *l; 
	struct node *r; 
	char *k;        
	val_t d;        
	int h;			
} node;

typedef struct munge 
{
	struct node *n;
	char *k;
	val_t d;
} munge;

void update_height(struct node *n)
{
	n->h = MAX(HL(n), HR(n)) + 1;
}

void node_destroy(struct node *n, int recurse)
{
	free(n->k);
	if (recurse && n->l) node_destroy(n->l, 1);
	if (recurse && n->r) node_destroy(n->r, 1);
	free(n);
}

struct node *node_create(char *key, val_t data)
{
	struct node *n = malloc(sizeof(struct node));
	n->l = 0;
	n->r = 0;
	n->k = malloc(strlen(key) + 1);
	strcpy(n->k, key);
	n->d = data;
	n->h = 0;
	return n;
}

struct node *lrot(struct node *n)
{
	struct node *oldright = n->r;
	n->r = n->r->l;
	oldright->l = n;

	update_height(n);
	update_height(oldright);
	return oldright;
}

struct node *rrot(struct node *n)
{
	struct node *oldleft = n->l;
	n->l = n->l->r;
	oldleft->r = n;

	update_height(n);
	update_height(oldleft);
	return oldleft;
}

struct node *rebalance(struct node *n)
{
	if (!n) return n;

	int lh = n->l ? n->l->h : -1;
	int rh = n->r ? n->r->h : -1;

	if (lh == rh + 2)
	{
		if (n->l->l && n->l->l->h == rh + 1)
		{ 
			n = rrot(n);
		}
		else if (n->l->r && n->l->r->h == rh + 1)
		{ 
			n->l = lrot(n->l);
			n = rrot(n);
		}
	}
	else if (rh == lh + 2)
	{
		if (n->r->r && n->r->r->h == lh + 1)
		{ 
			n = lrot(n);
		}
		else if (n->r->l && n->r->l->h == lh + 1)
		{ 
			n->r = rrot(n->r);
			n = lrot(n);
		}
	}

	return n;
}

struct node *node_insert(struct node *n, char *key, val_t data)
{
	int cmp = strcmp(n->k, key);
	if (cmp < 0)
		n->r = n->r ? node_insert(n->r, key, data) : node_create(key, data);
	else if (cmp > 0)
		n->l = n->l ? node_insert(n->l, key, data) : node_create(key, data);
	update_height(n);
	n = rebalance(n);
	return n;
}

val_t *node_lookup(struct node *n, char *key)
{
	if (!n) return 0;
	int cmp = strcmp(n->k, key);
	if (cmp < 0) return node_lookup(n->r, key);
	else if (cmp > 0) return node_lookup(n->l, key);
	else return &(n->d);
}

struct munge get_rightmost(struct node *n)
{
	if (n->r)
	{
		struct munge m = get_rightmost(n->r);
		n->r = m.n;
		update_height(n);
		m.n = rebalance(n);
		return m;
	}
	else
	{
		struct munge m;
		m.n = n->l;
		m.k = n->k;
		m.d = n->d;
		free(n);
		return m;
	}
}

struct node *node_delete(struct node *n, char *key)
{
	if (!n) return 0;
	int cmp = strcmp(n->k, key);
	if (cmp == 0)
	{ 
		if (!n->l)
		{
			struct node *r = n->r;
			node_destroy(n, 0);
			return r;
		}
		else if (!n->r)
		{
			struct node *l = n->l;
			node_destroy(n, 0);
			return l;
		}
		else
		{
			struct munge m = get_rightmost(n->l);
			free(n->k);
			n->l = m.n;
			n->k = m.k;
			n->d = m.d;
			update_height(n);
			return rebalance(n);
		}
	}
	if (cmp < 0) n->r = node_delete(n->r, key);
	if (cmp > 0) n->l = node_delete(n->l, key);
	update_height(n);
	return rebalance(n);
}



struct AVLTree* avl_create()
{
	struct AVLTree *t = malloc(sizeof(struct AVLTree));
	t->root = 0;
	return t;
}

void avl_destroy(struct AVLTree *tree)
{
	node_destroy(tree->root, 1);
	free(tree);
}


void avl_insert(struct AVLTree *avl, char *key, val_t data)
{
	if (avl->root)
	{
		avl->root = node_insert(avl->root, key, data);
	}
	else
	{
		avl->root = node_create(key, data);
	}
}

void avl_delete(struct AVLTree *avl, char *key)
{
	avl->root = node_delete(avl->root, key);
}

val_t *avl_lookup(struct AVLTree *tree, char *key)
{
	
	return node_lookup(tree->root, key);
}

int inorder(struct AVLTree *tree)			
{
	int nodes = 0;
	if (tree->root != NULL)
	{
		inorder(tree->root->l);
		nodes++;
		inorder(tree->root->r);
	}
	return nodes;
}
void avl_inspect(struct AVLTree *tree)
{
	
	int h = 0, nodes = 0;
	if (tree->root == 0xfeeefeee)
	{
		printf("Strom je nulovy/prazdny\n");
	}
	else
	{
		h = tree->root->h + 1;
		printf("Vyska stromu je: %i\n", h);
	}
	
	nodes = inorder(tree);

	printf("Pocet prvku ve stromu je: %i\n", nodes);





}

AVLTree AVLTreeClass =
{
(int(*)(void *, void *))strcmp,
avl_insert,
avl_lookup,
avl_delete,
avl_destroy,
avl_inspect
};

int main(int argc, char ** argv)
{
	int h = 0;
	Dictionary * d = Dictionary_new((Dictionary*)(&AVLTreeClass));
	
	struct AVLTree *t = avl_create();
	
	d->insert(t, "a", 1);
	d->insert(t, "b", 2);
	d->insert(t, "c", 3);
	d->insert(t, "d", 4);
	d->insert(t, "e", 5);
	d->insert(t, "f", 7);
	d->insert(t, "g", 8);
	d->insert(t, "h", 9);
	d->insert(t, "i", 10);
	d->insert(t, "j", 11);
	d->insert(t, "k", 12);

	d->inspect(t);
	
	d->remove(t, "f");
	d->remove(t, "a");
	d->remove(t, "b");
	d->remove(t, "h");
	d->remove(t, "k");

	d->inspect(t);

	d->free(t);
	d->inspect(t);
	system("pause");
	return 0;

}

Neformátovaný

Přidáno: 9.5.2014
Expirace: Neuvedeno

Autor: hurvajs