checkLeftRotation

Short summary

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

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

• Return type: CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode

Parameters

Name	Type	Comment	Kind
elem	CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode	The element for that the rotation should be checked	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 has changed	inout

Code

Declaration

METHOD PROTECTED checkLeftRotation :CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode
VAR_INPUT
	(*The element for that the rotation should be checked*)
	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 has changed*)
	heightNotChanged	:BOOL;
END_VAR

Implementation

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