recursivInsert

Short summary

recursiv insert function, tries to insert in the Tree and if not on right position call itself again on a subtree, on way out of recursin (re)balance tree

Return: the node that is the new root of the subtree for that the recursiv method is called

• Return type: CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode

Parameters

Name	Type	Comment	Kind
object	CNM_AbstractObject.IObject	the object that shoul be inserted	input
elem	CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode	the root of the tree we try to insert in	input
heightNotChanged	BOOL	is changed to false when insert was successful	inout
insertResult	CNM_ReturnTypes.SingleExecutionResult	SUCCESS if node could be inserted, ERROR if object already in the tree, ABORTED if object was null or empty node found	output

Code

Declaration

METHOD PROTECTED recursivInsert :CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode
VAR_INPUT
	(*the object that shoul be inserted*)
	object 						:CNM_AbstractObject.IObject;
	(*the root of the tree we try to insert in*)
	elem 						:CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode;
END_VAR
VAR_IN_OUT
	(*is changed to false when insert was successful*)
	heightNotChanged 			:BOOL;
END_VAR
VAR 
	rightChild 					:CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode;
	binaryRightChild 			:CNM_CollectionInterfaces.IBinaryTreeNode;
	binaryLeftChild 			:CNM_CollectionInterfaces.IBinaryTreeNode;
	leftChild		  			:CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode;
END_VAR
VAR_OUTPUT
	(*SUCCESS if node could be inserted, ERROR if object already in the tree, ABORTED if object was null or empty node found*)
	insertResult 				:CNM_ReturnTypes.SingleExecutionResult;
END_VAR
VAR CONSTANT
	OBJECT_IS_NOT_REFERENCED	:__XWORD := 0; 
END_VAR

Implementation

IF THIS^.isObjectNull(elem) AND NOT THIS^.isObjectNull(object) THEN
	IF (THIS^.collectionFactory.getNewBBSTreeNode(object := object, node => recursivInsert) <> CNM_ReturnTypes.SingleExecutionResult.SUCCESS) THEN
		insertResult := CNM_ReturnTypes.SingleExecutionResult.ERROR;
	ELSE
		insertResult := CNM_ReturnTypes.SingleExecutionResult.SUCCESS;
	END_IF
	RETURN;
ELSIF  THIS^.isObjectNull(object) OR_ELSE THIS^.isObjectNull(elem.object) THEN
	insertResult := CNM_ReturnTypes.SingleExecutionResult.ABORTED;
	RETURN;
END_IF
	

CASE THIS^.compareNodes(object, elem.object) OF
 	CNM_ReturnTypes.ComparationResult.EQUAL:
		recursivInsert := elem;
		insertResult := CNM_ReturnTypes.SingleExecutionResult.ABORTED;
		RETURN;
 	CNM_ReturnTypes.ComparationResult.SMALLER: 
		IF (THIS^.isObjectNull(elem.leftChild)) THEN
			IF (THIS^.collectionFactory.getNewBBSTreeNode(object := object, node => leftChild) = CNM_ReturnTypes.SingleExecutionResult.SUCCESS) THEN
				__QUERYINTERFACE(leftChild, binaryLeftChild);
				elem.leftChild := binaryLeftChild;
				heightNotChanged := FALSE;
				insertResult := CNM_ReturnTypes.SingleExecutionResult.SUCCESS;
			ELSE
				insertResult := CNM_ReturnTypes.SingleExecutionResult.ERROR;
			END_IF
		ELSE
			__QUERYINTERFACE(elem.leftChild, leftChild);
			leftChild := THIS^.recursivInsert(object := object, elem := leftChild, heightNotChanged := heightNotChanged, insertResult => insertResult);	
			__QUERYINTERFACE(leftChild,binaryLeftChild);
			elem.leftChild := binaryLeftChild;
		END_IF
		recursivInsert := THIS^.checkRightRotation(elem:=elem,heightNotChanged:=heightNotChanged, removing := FALSE);
		RETURN;
	CNM_ReturnTypes.ComparationResult.Greater:
		IF THIS^.isObjectNull(elem.rightChild) THEN 
			IF (THIS^.collectionFactory.getNewBBSTreeNode(object := object, node => rightChild) = CNM_ReturnTypes.SingleExecutionResult.SUCCESS) THEN
				__QUERYINTERFACE(rightChild,binaryRightChild);
				elem.rightChild := binaryRightChild;
				heightNotChanged := FALSE;
				insertResult := CNM_ReturnTypes.SingleExecutionResult.SUCCESS;
			ELSE
				insertResult := CNM_ReturnTypes.SingleExecutionResult.ERROR;
			END_IF
		ELSE
			__QUERYINTERFACE(elem.rightChild,rightChild);
			rightChild := THIS^.recursivInsert(object:=object,elem:=rightChild,heightNotChanged:=heightNotChanged,insertResult=>insertResult);
			__QUERYINTERFACE(rightChild,binaryRightChild);
			elem.rightChild := binaryRightChild;	
		END_IF
		recursivInsert := THIS^.checkLeftRotation(elem:=elem,heightNotChanged:=heightNotChanged,removing := FALSE);
		RETURN;
END_CASE;