recursivSearchSuccessor

Short summary

gets the successor of a node and removes it from the tree so it can be inserted at another place (used when remove) and rebalances tree

Return: The successor node of the elem node

• Return type: CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode

Parameters

Name	Type	Comment	Kind
elem	CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode	the element a successor should be searched for	input
heightNotChanged	BOOL	True if the successor was removed	inout
newRoot	CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode	returns the new root, bc root can be changed bc of rotation	output

Code

Declaration

METHOD PROTECTED recursivSearchSuccessor :CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode
VAR_INPUT
	(*the element a successor should be searched for*)
	elem 				:CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode;
END_VAR
VAR_IN_OUT
	(*True if the successor was removed*)
	heightNotChanged 	:BOOL;
END_VAR
VAR_OUTPUT
	(*returns the new root, bc root can be changed bc of rotation*)
	newRoot				:CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode;
END_VAR
VAR
	leftChild			:CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode;
END_VAR

Implementation

IF NOT THIS^.isObjectNull(elem.leftChild.leftChild) THEN
	__QUERYINTERFACE(elem.leftChild,leftChild);
	recursivSearchSuccessor := THIS^.recursivSearchSuccessor(elem:=leftChild,heightNotChanged := heightNotChanged,newRoot => newRoot);
	elem.leftChild := newRoot;
	newRoot := checkLeftRotation(elem:=elem,heightNotChanged:=heightNotChanged,removing:=TRUE);
	RETURN;
ELSE
	__QUERYINTERFACE(elem.leftChild,leftChild);
	recursivSearchSuccessor := leftChild;
	elem.leftChild := elem.leftChild.rightChild;
	newRoot := checkLeftRotation(elem:=elem,heightNotChanged:=heightNotChanged,removing:=TRUE);
	RETURN;
END_IF