reorganizeLeftRotate

Short summary

performs a left rotation around a specified node and cares about the subtress and balance

Return: the new root that replaced the one that was used for rotation

• Return type: CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode

Parameters

Name	Type	Comment	Kind
elem	CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode	The element around that should be rotatet	input
removing	BOOL	indicates if method was called in context of remove (then true) or in context of insert (then false)	input
heightNotChanged	BOOL	false if the height of the tree changed	inout

Code

Declaration

METHOD PROTECTED reorganizeLeftRotate :CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode
VAR_INPUT
	(*The element around that should be rotatet*)
	elem				:CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode;
	(*indicates if method was called in context of remove (then true) or in context of insert (then false) *)
	removing				:BOOL;
END_VAR
VAR_IN_OUT
	(*false if the height of the tree changed*)
	heightNotChanged 	:BOOL;
END_VAR
VAR 
	internLeftChild		:CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode;
	internRightChild	:CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode; 
END_VAR

Implementation

__QUERYINTERFACE(elem.rightChild,internRightChild);

CASE internRightChild.balance OF
	CNM_CollectionInterfaces.TreeBalance.RIGHTDEEPER:
		elem := THIS^.rotateLeft(elem);
		__QUERYINTERFACE(elem.leftChild,internLeftChild);
		internLeftChild.balance := CNM_CollectionInterfaces.TreeBalance.EQUALDEEP;
		elem.balance := CNM_CollectionInterfaces.TreeBalance.EQUALDEEP;
		heightNotChanged := NOT removing;
		reorganizeLeftRotate := elem;
	CNM_CollectionInterfaces.TreeBalance.EQUALDEEP: 
		elem := THIS^.rotateLeft(elem);
		__QUERYINTERFACE(elem.leftChild,internLeftChild);
		internLeftChild.balance := CNM_CollectionInterfaces.TreeBalance.RIGHTDEEPER;
		elem.balance := CNM_CollectionInterfaces.TreeBalance.LEFTDEEPER;
		heightNotChanged := removing;
		reorganizeLeftRotate := elem;
	CNM_CollectionInterfaces.TreeBalance.LEFTDEEPER:
		elem.rightChild := THIS^.rotateRight(internRightChild);
		elem := THIS^.rotateLeft(elem);
		THIS^.adaptBalanceAfterDoubleRotation(elem:=elem);
		elem.balance := CNM_CollectionInterfaces.TreeBalance.EQUALDEEP;
		heightNotChanged := removing;
		reorganizeLeftRotate := elem;
END_CASE