checkRightRotation

Short summary

check if a rightrotation is neccesary (=> is left subtree to deep?), if necessary it is performed

Return: the new root of the subtree, that replaces the node the rotation was checked for

• Return type: CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode

Parameters

Name	Type	Comment	Kind
elem	CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode	The root of the subtree that should be checked for rotation	input
removing	BOOL	indicates if method was called in context of remove (then true) or in context of insert (then false)	input
heightNotChanged	BOOL	signals if the height of any subtree changed	inout

Code

Declaration

METHOD PROTECTED checkRightRotation :CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode
VAR_INPUT
	(*The root of the subtree that should be checked for rotation*)
	elem 				:CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode;
	(*indicates if method was called in context of remove (then true) or in context of insert (then false) *)
	removing				:BOOL	:= FALSE;
END_VAR
VAR_IN_OUT
	(*signals if the height of any subtree changed *)
	heightNotChanged 	:BOOL;
END_VAR

Implementation

IF heightNotChanged THEN 
	checkRightRotation := elem;
	RETURN;
ELSE
	CASE elem.balance OF 
		CNM_CollectionInterfaces.TreeBalance.EQUALDEEP:
			elem.balance := CNM_CollectionInterfaces.TreeBalance.LEFTDEEPER;
			heightNotChanged := removing;
			checkRightRotation := elem;
			RETURN;
		CNM_CollectionInterfaces.TreeBalance.RIGHTDEEPER:
			elem.balance := CNM_CollectionInterfaces.TreeBalance.EQUALDEEP;
			heightNotChanged := NOT removing;
			checkRightRotation := elem;
			RETURN;
		CNM_CollectionInterfaces.TreeBalance.LEFTDEEPER:
			checkRightRotation := THIS^.reorganizeRightRotate(elem := elem, heightNotChanged := heightNotChanged, removing := removing);
			RETURN;
	END_CASE
END_IF