Skip to main content

BalancedBinarySearchTree

Short summary​

Interface for a balanced, binary, search tree

  • balanced means that every node has a balanced (see Tree_Balance)
  • binary means that every node has two childs (they can be null)
  • search means it is a set, every object can be only contained once

Attention: search not only means you can't store an object with the same hash only once, instead it means you can only one element with this comparevalue. So if you compare elements by size and you have five diffrent objects with the same size, only one of them can be stored

Warning: Calling __DELETE directly on a Collection will bypass the destruct Context and therefore also delete the contained elements. Do not change the compare value of objects while they are in the tree, doing so will destroy your tree which can lead to not finding elements, hurt of search and balanced properties and os on. If you have to alter the value the correct way is: remove from tree, alter, insert. Same applies for foreach / iterate do not perform any operations changing the comparevalue

AccessAbstractFinalExtendsImplements
-NoNoAbstractCollectionCNM_CollectionInterfaces.IBalancedBinarySearchTree, ISetHelper, ITreeHelper

UML Diagram​

Parameters

none

Properties​

className​

Type: CNM_AbstractObject.ClassName

This abstract property returns the class name of the concrete object, …

maxCycleCompares​

Type: UDINT

This property defines the maximum amount of compares that should be done per Cycle. Is optional as default should be set by class.…

root​

Type: CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode

This property points to the root of a tree…

set​

Type: CNM_CollectionInterfaces.ISetStrategy

This property returns a fluent interface to set operations, e.g. intersect() and subtract().…

size​

Type: UDINT

This property allows to change the collection size without using insert / remove etc.…

tree​

Type: CNM_CollectionInterfaces.ITreeStrategy

This property returns a fluent interface to tree operations, e.g. insert() and remove().…

treeHeight​

Type: USINT

Function to calculate the height of a tree, as its a balanced binary tree, is defined as …

Methods​

adaptBalanceAfterDoubleRotation​

after a double rotation balance have to be adopted…

announceChange​

  • Return type: VOID

called every time the tree changes, can be used to notify components…

checkLeftRotation​

check if a leftrotation is neccesary (=> is right subtree to deep?), if necessary it is performed…

checkRightRotation​

check if a rightrotation is neccesary (=> is left subtree to deep?), if necessary it is performed…

clear​

  • Return type: VOID

This method clears/deletes all clearable data from this object.…

clearContents​

  • Return type: VOID

This method is called in the destruct method and is intended to zero all references and interfaces that should not be destructed. …

clone​

This method is used to create a new instance…

compareNodes​

compares two objects (should be nodevalues, or values to be inserted), uses the comparator set with method setNodeComparator…

compareTo​

This method compares a foreign object with the own one, this is needed for sort orders.…

containsEqualObject​

  • Parameters:
  • Return type: BOOL

True if the tree contains any object where either the injected comparator or, if no comparator is used, the object.compareTo …

containsObject​

This method checks if a given object is contained in the collection.…

createNewIterator​

This method returns a NEW Iterator instance which can iterate the collection.…

dec​

  • Parameters:
    • value (__XWORD): value to decrease
  • Return type: VOID

Method to decrease __XWORD without overflow…

decrementSize​

  • Return type: VOID

decrements the size of the collection…

deepClone​

This method is used to create a new instance…

destructNodeAndAllChilds​

  • Parameters:
    • node (CNM_CollectionInterfaces.IBinaryTreeNode): the node that should be destructed with all it's childs
    • destructNodeContents (BOOL): if true also the node contents will be destructed, if false only the nodes will be destructed
  • Return type: VOID

destructs / deepdestructs all nodes in the subtrees of a specified node and this node…

FB_Exit​

  • Parameters:
    • bInCopyCode (BOOL): TRUE: the exit method is called in order to leave the instance which will be copied afterwards (online change).
  • Return type: BOOL

Mark the object as deleted, as it stays in the memory.…

FB_init​

  • Parameters:
    • bInitRetains (BOOL): if TRUE, the retain variables are initialized (warm start / cold start)
    • bInCopyCode (BOOL): if TRUE, the instance afterwards gets moved into the copy code (online change)
    • nodeComparator (CNM_AbstractObject.IComparator): Optional comparator
  • Return type: BOOL

The constructor FB_init is needed to create an unique hash code.…

getClonedComparator​

prepares a new Comparator (if set)…

getClonedEmptyTree​

prepares a new empty tree object with the same internal state as THIS^…

getEqualObject​

Searches an Object, that is equal to the provided object in terms of the compareTo Method (or an provided comparator from the parentstructure). …

getInorderSuccessor​

finds the next greater node (inorder successor) of a specified node…

getSmallestNode​

finds the smallest node in a specified (sub)tree…

inc​

  • Parameters:
    • value (__XWORD)
  • Return type: VOID

method to increase __xword without overflow…

incrementSize​

  • Return type: VOID

increments the size of the collection…

insert​

This method can be used to insert a single element into the tree.…

insertCollection​

This method inserts all elements of a collection into the tree.…

instantInsertCollection​

This method inserts all elements of a collection into the tree…

instantIntersect​

overwrites the content of this set with the intersection of this set and the given set…

instantMerge​

overwrites the content of this set with the union of this set and the given set…

instantSubtract​

overwrites the content of this set with the set difference of this set and the given set…

intersect​

overwrites the content of this set with the intersection of this set and the given set…

iterate​

This method returns the next object in the iteration and returns an execution state.…

merge​

overwrites the content of this set with the union of this set and the given set…

recursivInsert​

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…

recursivRemove​

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…

recursivSearchSuccessor​

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…

remove​

Method to remove an object from the tree.…

reorganizeLeftRotate​

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

reorganizeRightRotate​

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

rotateLeft​

rotates a tree around a node…

rotateRight​

rotates right around a specified node, doesnt care about balance and stuff, this is done in method reorganizeRightRotate…

searchSuccessor​

searches a successor and removes it from the tree so it can be used to replace another (deleted) node…

setNodeComparator​

Sets a comparator, that is used to compare two nodes of this tree.…

subtract​

overwrites the content of this set with the set difference of this set and the given set…

Code​

Declaration​

{attribute 'enable_dynamic_creation'}
FUNCTION_BLOCK BalancedBinarySearchTree EXTENDS AbstractCollection IMPLEMENTS CNM_CollectionInterfaces.IBalancedBinarySearchTree, ISetHelper, ITreeHelper
VAR
	rootNode 			:CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode;
	nodeComparator		:CNM_AbstractObject.IComparator;
	(*nodestack used for iterate, placed in instance to be able to destroy it on destruct*)
	nodestack			:POINTER TO CNM_CollectionInterfaces.IBalancedBinarySearchTreeNode;
	(* set iterator for subtract *)
	subtractIterator	:CNM_CollectionInterfaces.IIterator;
	(* collection iterator for insertCollection *)
	insertIterator		:CNM_CollectionInterfaces.IIterator;
	(* set iterator for intersect *)
	intersectIterator 	:CNM_CollectionInterfaces.IIterator;
	(* the amount of compare operations per cycle *)
	upperCompareBound :UDINT := GeneralParameters.DEFAULT_OPERATIONS_PER_CYCLE;
	(* insert buffer to roll back inserted Objects in error case *)
	insertBuffer :POINTER TO CNM_AbstractObject.IObject;
	(* intersect tree *)
	intersectedTree :POINTER TO BalancedBinarySearchTree;
END_VAR