Wooow, what a huge code

w dziale Test
Zajec napisał(a):

It's huge, isn't it?

#include <stdio.h>
#include <stdlib.h>
#include "bst.struct.h"


void show(ELEM *curr)
{
	if (curr!=NULL && curr->left!=NULL)
	{
		printf("%d [%d,%d]\t--L-> %d [%d,%d]\n",curr->val,curr->a,curr->b,curr->left->val,curr->left->a,curr->left->b);
		show(curr->left);
	}
	if (curr!=NULL && curr->right!=NULL)
	{
		printf("%d [%d,%d]\t--R-> %d [%d,%d]\n",curr->val,curr->a,curr->b,curr->right->val,curr->right->a,curr->right->b);
		show(curr->right);
	}
}


void fix_my_ab(ELEM *curr)
{
	if (curr!=NULL)
	{
		if (curr->right!=NULL)
		curr->b=((curr->right->a>curr->right->b)?curr->right->a:curr->right->b)+1;
		else
		curr->b=0;

		if (curr->left!=NULL)
		curr->a=((curr->left->a>curr->left->b)?curr->left->a:curr->left->b)+1;
		else
		curr->a=0;

		fix_my_ab(curr->parent);
	}
}


ELEM *check_tree_from(ELEM *root, ELEM *curr, int *wywazen)
{
	//printf("wywolane dla %d, roznica: %d\n",curr->val,curr->b-curr->a);
	if (curr->b-curr->a==2)
	{
		*wywazen=*wywazen+1;
		if (curr->right->b-curr->right->a==1 || curr->right->b-curr->right->a==0) //metoda 1
		{
			//printf("metoda 1\n");
			ELEM *a=curr->right;


			curr->right=a->left;
			if (a->left!=NULL)
			a->left->parent=curr;


			a->parent=curr->parent;
			if (curr->parent!=NULL && curr->parent->left==curr)
			curr->parent->left=a;
			else if (curr->parent!=NULL && curr->parent->right==curr)
			curr->parent->right=a;


			a->left=curr;
			curr->parent=a;


			if (curr->right!=NULL) fix_my_ab(curr->right);
			else if (curr->left!=NULL) fix_my_ab(curr->left);
			else fix_my_ab(curr);
			if (a->parent==NULL) root=a;
		}
		else if (curr->right->b-curr->right->a==-1) //metoda 4
		{
			//printf("metoda 4\n");
			ELEM *a=curr->right;
			ELEM *b=a->left;


			b->parent=curr->parent;
			if (curr->parent!=NULL && curr->parent->left==curr)
			curr->parent->left=b;
			else if (curr->parent!=NULL && curr->parent->right==curr)
			curr->parent->right=b;


			curr->right=b->left;
			if (b->left!=NULL) b->left->parent=curr;


			b->left=curr;
			curr->parent=b;


			a->left=b->right;
			if (b->right!=NULL) b->right->parent=a;


			b->right=a;
			a->parent=b;


			if (a->right!=NULL) fix_my_ab(a->right);
			else if (a->left!=NULL) fix_my_ab(a->left);
			else fix_my_ab(a);

			if (curr->right!=NULL) fix_my_ab(curr->right);
			else if (curr->left!=NULL) fix_my_ab(curr->left);
			else fix_my_ab(curr);

			if (b->parent==NULL) root=b;
		}
	}
	else if (curr->b-curr->a==-2)
	{
		*wywazen=*wywazen+1;
		if (curr->left->b-curr->left->a==-1 || curr->left->b-curr->left->a==0) //metoda 2
		{
			//printf("metoda 2\n");
			ELEM *a=curr->left;


			curr->left=a->right;
			if (a->right!=NULL)
			a->right->parent=curr;


			a->parent=curr->parent;
			if (curr->parent!=NULL && curr->parent->left==curr)
			curr->parent->left=a;
			else if (curr->parent!=NULL && curr->parent->right==curr)
			curr->parent->right=a;


			a->right=curr;
			curr->parent=a;


			if (curr->right!=NULL) fix_my_ab(curr->right);
			else if (curr->left!=NULL) fix_my_ab(curr->left);
			else fix_my_ab(curr);
			if (a->parent==NULL) root=a;
		}
		else if (curr->left->b-curr->left->a==-1) //metoda 3
		{
			//printf("metoda 3\n");
			ELEM *a=curr->left;
			ELEM *b=a->right;


			b->parent=curr->parent;
			if (curr->parent!=NULL && curr->parent->left==curr)
			curr->parent->left=b;
			else if (curr->parent!=NULL && curr->parent->right==curr)
			curr->parent->right=b;


			curr->left=b->right;
			if (b->right!=NULL) b->right->parent=curr;


			b->right=curr;
			curr->parent=b;


			a->right=b->left;
			if (b->left!=NULL) b->left->parent=a;


			b->left=a;
			a->parent=b;


			if (a->right!=NULL) fix_my_ab(a->right);
			else if (a->left!=NULL) fix_my_ab(a->left);
			else fix_my_ab(a);

			if (curr->right!=NULL) fix_my_ab(curr->right);
			else if (curr->left!=NULL) fix_my_ab(curr->left);
			else fix_my_ab(curr);

			if (b->parent==NULL) root=b;
		}
	}
	else if (curr->parent!=NULL) root=check_tree_from(root, curr->parent, wywazen);
	return root;
}


ELEM *find(ELEM *root, int liczba)
{
	if (root==NULL) //gdy 0 elementow
	return NULL;
	else //szukanie miejsca
	{
		ELEM *curr=root;
		while (1)
		{
			if (liczba==curr->val)
			return curr;
			else if (liczba > curr->val && curr->right!=NULL) //szukamy wiekszej, czyli na prawo
			curr=curr->right;
			else if (liczba < curr->val && curr->left!=NULL) //szuakamy mniejszej, czyli lewo
			curr=curr->left;
			else //liczby nie ma
			return NULL;
		}
	}
}


ELEM *usun(ELEM *root, int liczba, int *wywazen, int *operacji)
{
	ELEM *del=find(root, liczba);;
	if (del!=NULL)
	{
		*operacji=*operacji+1;
		if (del->right==NULL && del->left==NULL) //element jest liściem
		{
			//printf("met 1\n");
			if (del->parent!=NULL && del->parent->left==del)
			{
			del->parent->left=NULL;
			del->parent->a=0;
			fix_my_ab(del->parent);
			root=check_tree_from(root, del->parent, wywazen);
			}
			else if (del->parent!=NULL && del->parent->right==del)
			{
			del->parent->right=NULL;
			del->parent->b=0;
			fix_my_ab(del->parent);
			root=check_tree_from(root, del->parent, wywazen);
			}
			free(del);
		}
		else if (del->right==NULL) //element ma tylko lewego potomka
		{
			//printf("met 2\n");
			if (del->parent!=NULL && del->parent->left==del)
			{
			del->parent->left=del->left;
			del->left->parent=del->parent;
			fix_my_ab(del->left);
			root=check_tree_from(root, del->left, wywazen);
			}
			else if (del->parent!=NULL && del->parent->right==del)
			{
			del->parent->right=del->left;
			del->left->parent=del->parent;
			fix_my_ab(del->left);
			root=check_tree_from(root, del->left, wywazen);
			}
			free(del);
		}
		else if (del->left==NULL) //element ma tylko prawego potomka
		{
			//printf("met 3\n");
			if (del->parent!=NULL && del->parent->left==del)
			{
			del->parent->left=del->right;
			del->right->parent=del->parent;
			fix_my_ab(del->right);
			root=check_tree_from(root, del->right, wywazen);
			}
			else if (del->parent!=NULL && del->parent->right==del)
			{
			del->parent->right=del->right;
			del->right->parent=del->parent;
			fix_my_ab(del->right);
			root=check_tree_from(root, del->right, wywazen);
			}
			free(del);
		}
		else if (del->b >= del->a && del->right->left==NULL) //jedno zejście w prawo
		{
			//printf("met 4\n");
			if (del->parent!=NULL && del->parent->left==del)
			{
			del->parent->left=del->right;
			del->right->parent=del->parent;
			}
			else if (del->parent!=NULL && del->parent->right==del)
			{
			del->parent->right=del->right;
			del->right->parent=del->parent;
			}


			del->right->left=del->left;
			if (del->left!=NULL) del->left->parent=del->right;


			if (del->right->parent==NULL)
			root=del->right;
			fix_my_ab(del->right);
			root=check_tree_from(root, del->right, wywazen);
			free(del);
		}
		else if (del->b >= del->a && del->left->right==NULL) //jedno zejście w lewo
		{
			//printf("met 5\n");
			if (del->parent!=NULL && del->parent->left==del)
			{
			del->parent->left=del->left;
			del->left->parent=del->parent;
			}
			else if (del->parent!=NULL && del->parent->right==del)
			{
			del->parent->right=del->left;
			del->left->parent=del->parent;
			}


			del->left->right=del->right;
			if (del->right!=NULL) del->right->parent=del->left;


			if (del->left->parent==NULL)
			root=del->left;
			fix_my_ab(del->left);
			root=check_tree_from(root, del->left, wywazen);
			free(del);
		}
		else if (del->b >= del->a && del->right->left!=NULL) //raz w prawo, max w lewo
		{
			//printf("met 6\n");
			ELEM *tmp=del->right;
			while (tmp->left->left!=NULL)
			tmp=tmp->left;
			ELEM *newroot=tmp->left;


			newroot->parent=del->parent;
			if (del->parent!=NULL && del->parent->left==del)
			del->parent->left=newroot;
			else if (del->parent!=NULL && del->parent->right==del)
			del->parent->right=newroot;


			tmp->left=newroot->right;
			if (newroot->right!=NULL) newroot->right->parent=tmp;


			newroot->left=del->left;
			if (del->left!=NULL) del->left->parent=newroot;
			newroot->right=del->right;
			del->right->parent=newroot;


			fix_my_ab(tmp);
			root=check_tree_from(root, tmp, wywazen);
			free(del);


			if (newroot->parent==NULL)
			root=newroot;
		}
		else if (del->b < del->a && del->left->right!=NULL) //raz w lewo, max w prawo
		{
			//printf("met 7\n");
			ELEM *tmp=del->left;
			while (tmp->right->right!=NULL)
			tmp=tmp->right;
			ELEM *newroot=tmp->right;


			newroot->parent=del->parent;
			if (del->parent!=NULL && del->parent->left==del)
			del->parent->left=newroot;
			else if (del->parent!=NULL && del->parent->right==del)
			del->parent->right=newroot;


			tmp->right=newroot->left;
			if (newroot->left!=NULL) newroot->left->parent=tmp;


			newroot->right=del->right;
			if (del->right!=NULL) del->right->parent=newroot;
			newroot->left=del->left;
			del->left->parent=newroot;


			fix_my_ab(tmp);
			root=check_tree_from(root, tmp, wywazen);
			free(del);


			if (newroot->parent==NULL)
			root=newroot;
		}
	}
	return root;
}


ELEM *dodaj(ELEM *root, int liczba, int *wywazen, int *operacji)
{
//printf("dodaje %d\n",liczba);
//printf("wyw: %d\t",wywazen);
	if (root==NULL) //gdy jeszcze 0 elementow
	{
		root = (ELEM *) malloc(sizeof(ELEM));
		root->parent=NULL;
		root->left=NULL;
		root->right=NULL;
		root->val=liczba;
		root->a=0;
		root->b=0;
		*operacji=*operacji+1;
	}
	else //szukanie miejsca
	{
		ELEM *new;
		new = (ELEM *) malloc(sizeof(ELEM));
		new->val=liczba;
		new->a=0;
		new->b=0;
		new->left=NULL;
		new->right=NULL;
		new->parent=NULL;

		ELEM *curr=root;
		while (1)
		{
			if (curr->val > new->val && curr->left==NULL) //wstawiamy na lewo
			{
				curr->left=new;
				new->parent=curr;
				curr->a=1;
				*operacji=*operacji+1;
				fix_my_ab(curr->parent);
				root=check_tree_from(root, new, wywazen);
				break;
			}
			else if (curr->val > new->val) //przechodzimy w lewo
			curr=curr->left;
			else if (curr->val < new->val && curr->right==NULL) //wstawiamy na prawo
			{
				curr->right=new;
				new->parent=curr;
				curr->b=1;
				*operacji=*operacji+1;
				fix_my_ab(curr->parent);
				root=check_tree_from(root, new, wywazen);
				break;
			}
			else if (curr->val < new->val) //przechodzimy w prawo
			curr=curr->right;
			else //element juz istnieje
			break;
		}
	}
	return root;
}


void wywal(ELEM *curr)
{
	if (curr!=NULL && curr->left!=NULL)
	wywal(curr->left);
	if (curr!=NULL && curr->right!=NULL)
	wywal(curr->right);
	if (curr!=NULL) free(curr);
}

golew napisał(a):

A spróbuj dłuuugi w dół ale nie przekraczający szerokości.