Demo entry 6350086

aaa

   

Submitted by anonymous on Mar 04, 2017 at 14:54
Language: C. Code size: 2.4 kB.

/* To insert a node in the search tree  */
int Height(Position P)
{
	if (P == NULL)
		return -1;
	else
		return P->height;
}

AVLTree AVL_Insert(ElementType X, AVLTree T)
{
	if (T == NULL) { /* Create and return a one-node tree */
		T = (AVLTree)malloc(sizeof(struct AVLTreeNode));
		if (T == NULL)
			FatalError("Out of space!!!\n");
		else {
			T->Element = X;
			T->Left = T->Right = NULL;
			T->height = 0;
		}
	}  		/* End creating a one-node tree */
			/* If there is a tree */
	else {
		if (X < T->Element) {
			T->Left = AVL_Insert(X, T->Left);
			if (Height(T->Left) - Height(T->Right) == 2) {
				if (X < T->Left->Element)
					T = LL(T);
				else
					T = LR(T);
			}
		}
			
		else if (X > T->Element) {
			T->Right = AVL_Insert(X, T->Right);
			if (Height(T->Right) - Height(T->Left) == 2) {
				if (X > T->Right->Element)
					T = RR(T);
				else
					T = RL(T);
			}
		}
		/* Else X is in the tree already; we'll do nothing */
	}
	
	T->height = max(Height(T->Left), Height(T->Right)) + 1;
 	return T;   /* Do not forget this line!! */
}

AVLTree LL(AVLTree A)
{
	AVLTree B = A->Left;
	A->Left = B->Right;
	B->Right = A;
	
	//update the heights of A and B(A before B).
	A->height = max(Height(A->Left), Height(A->Right)) + 1;
	B->height = max(Height(B->Left), Height(B->Right)) + 1;
	return B;
}

AVLTree LR(AVLTree A)
{
	AVLTree B = A->Left;
	AVLTree C = B->Right;
	B->Right = C->Left;
	A->Left = C->Right;
	C->Left = B;
	C->Right = A;
	
	//update the heights of A and B(A before B).
	A->height = max(Height(A->Left), Height(A->Right)) + 1;
	B->height = max(Height(B->Left), Height(B->Right)) + 1;
	C->height = max(Height(B->Left), Height(C->Right)) + 1;
	return C;
}

AVLTree RR(AVLTree A)
{
	AVLTree B = A->Right;
	A->Right = B->Left;
	B->Left = A;
	
	//update the heights of A and B(A before B).
	A->height = max(Height(A->Left), Height(A->Right)) + 1;
	B->height = max(Height(B->Left), Height(B->Right)) + 1;
	return B;
}

AVLTree RL(AVLTree A)
{
	AVLTree B = A->Right;
	AVLTree C = B->Left;
	B->Left = C->Right;
	A->Right = C->Left;
	C->Left = A;
	C->Right = B;
	
	//update the heights of A and B(A before B).
	A->height = max(Height(A->Left), Height(A->Right)) + 1;
	B->height = max(Height(B->Left), Height(B->Right)) + 1;
	C->height = max(Height(C->Left), Height(C->Right)) + 1;
	return C;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).