recursivRemove

Short summary

recursiv remove an element tries to remove element from tree, if not possible calls itself on 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 should be removed	input
elem	CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode	The root of the tree we try to delete the object from	input
heightNotChanged	BOOL	changed to false when node is removed	inout
removeResult	CNM_ReturnTypes.SingleExecutionResult	SUCCESS, if remove was successful	output

Code

Declaration

METHOD PROTECTED recursivRemove :CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode
VAR_INPUT
	(*The object that should be removed*)
	object 						:CNM_AbstractObject.IObject;
	(*The root of the tree we try to delete the object from *)
	elem 						:CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode;
END_VAR
VAR_IN_OUT
	(*changed to false when node is removed*)
	heightNotChanged 			:BOOL;
END_VAR
VAR 
	leftChild					:CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode;
	binaryLeftChild 			:CNM_CollectionInterfaces.IBinaryTreeNode;
	binaryRightChild 			:CNM_CollectionInterfaces.IBinaryTreeNode;
	rightChild 					:CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode;
	testrightChild 				:CNM_CollectionInterfaces.IBinaryTreeNode;
END_VAR
VAR_OUTPUT
	(*SUCCESS, if remove was successful*)
	removeResult 				:CNM_ReturnTypes.SingleExecutionResult;
END_VAR
VAR CONSTANT
	OBJECT_IS_NOT_REFERENCED	:__XWORD := 0;
END_VAR

Implementation

IF THIS^.isObjectNull(elem) THEN
	recursivRemove := OBJECT_IS_NOT_REFERENCED;
	removeResult := CNM_ReturnTypes.SingleExecutionResult.ABORTED;
	RETURN;
ELSIF THIS^.isObjectNull(object) OR_ELSE THIS^.isObjectNull(elem.object) THEN
	removeResult := CNM_ReturnTypes.SingleExecutionResult.ERROR;
	RETURN;
END_IF;

CASE THIS^.compareNodes(object,elem.object) OF
	CNM_AbstractObject.CNM_ReturnTypes.ComparationResult.SMALLER:
		__QUERYINTERFACE(elem.leftChild,leftChild);
		leftChild := THIS^.recursivRemove(object:=object,elem:=leftChild, heightNotChanged := heightNotChanged,removeResult=>removeResult);
		__QUERYINTERFACE(leftChild,binaryLeftChild);
		elem.leftChild := binaryLeftChild;
		recursivRemove := checkLeftRotation(elem := elem, heightNotChanged := heightNotChanged,removing := TRUE);
		RETURN;
	CNM_AbstractObject.CNM_ReturnTypes.ComparationResult.GREATER:
		__QUERYINTERFACE(elem.rightChild,rightChild);
		rightChild := THIS^.recursivRemove(object := object, elem := rightChild, heightNotChanged := heightNotChanged,removeResult=>removeResult);
		__QUERYINTERFACE(rightChild,binaryRightChild);
		elem.rightChild := binaryRightChild;
		recursivRemove := checkRightRotation(elem := elem, heightNotChanged := heightNotChanged,removing := TRUE);
		RETURN;
	CNM_AbstractObject.CNM_ReturnTypes.ComparationResult.EQUAL:
		IF THIS^.isObjectNull(elem.leftChild) THEN
			heightNotChanged := FALSE;
			__QUERYINTERFACE(elem.rightChild,recursivRemove);
			
		ELSIF THIS^.isObjectNull(elem.rightChild) THEN
			heightNotChanged:=FALSE;
			__QUERYINTERFACE(elem.leftChild,recursivRemove);
		ELSE
			recursivRemove := searchSuccessor(elem:=elem,heightNotChanged:=heightNotChanged);
			recursivRemove.balance := elem.balance;
			recursivRemove.leftChild := elem.leftChild;
			recursivRemove.rightChild := elem.rightChild;
			recursivRemove := checkRightRotation(elem := recursivRemove,heightNotChanged:=heightNotChanged,removing := TRUE);
		END_IF
		removeResult := CNM_ReturnTypes.SingleExecutionResult.SUCCESS;
		elem.leftChild := OBJECT_IS_NOT_REFERENCED;
		elem.rightChild := OBJECT_IS_NOT_REFERENCED;
		elem.destruct();
		RETURN;
END_CASE