reorganizeRightRotate

Short summary

rotates right around a specified node, and cares about subtrees and balance

Return: the node that replaced the node that was used to rotate around

• Return type: CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode

Parameters

Name	Type	Comment	Kind
elem	CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode	the node around the rotation should be performed	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 height changed, set to true when rotation rebalanced the tree	inout

Code

Declaration

METHOD PROTECTED reorganizeRightRotate :CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode
VAR_INPUT
	(*the node around the rotation should be performed*)
	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 height changed, set to true when rotation rebalanced the tree*)
	heightNotChanged 	:BOOL;
END_VAR
VAR 
	leftChild 			:CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode;
	rightChild 			:CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode;
END_VAR

Implementation

__QUERYINTERFACE(elem.leftChild,leftChild);
__QUERYINTERFACE(elem.rightChild, rightChild);

CASE leftChild.balance OF 
	CNM_CollectionInterfaces.TreeBalance.LEFTDEEPER: 
		elem := rotateRight(elem:=elem);
		__QUERYINTERFACE(elem.rightChild, rightChild);
		rightChild.balance := CNM_CollectionInterfaces.TreeBalance.EQUALDEEP;
		elem.balance := CNM_CollectionInterfaces.TreeBalance.EQUALDEEP;
		heightNotChanged := NOT removing;
		reorganizeRightRotate := elem;
		RETURN;
	CNM_CollectionInterfaces.TreeBalance.EQUALDEEP: 
		elem := rotateRight(elem:=elem);
		__QUERYINTERFACE(elem.rightChild, rightChild);
		rightChild.balance := CNM_CollectionInterfaces.TreeBalance.LEFTDEEPER;
		elem.balance := CNM_CollectionInterfaces.TreeBalance.RIGHTDEEPER;
		heightNotChanged := removing;
		reorganizeRightRotate := elem;
		RETURN;
	CNM_CollectionInterfaces.TreeBalance.RIGHTDEEPER:
		elem.leftChild := rotateLeft(elem:=leftChild);
		elem := rotateRight(elem:=elem);
		adaptBalanceAfterDoubleRotation(elem:=elem);
		elem.balance := CNM_CollectionInterfaces.TreeBalance.EQUALDEEP;
		heightNotChanged := NOT removing;
		reorganizeRightRotate := elem;
		RETURN;
		
END_CASE