AVL Trees

Authenticity
By Authenticity in AutoIt Example Scripts,
AVL trees are an efficient way to represent data in memory using tree based structure. The major improvement of AVL trees compared to simple binary trees is that they're balanced, meaning that the insertion, deletion, etc... is promised to be O(Log2 N). In the worst case it'll take Log2 N (where N is the number of nodes in the tree) to search for or insert an item, whereas in a simple binary tree it could take O(N), just like a linked list. This library is written using AVL Trees: Tutorial and C++ Implementation by Brad Appleton. I'd like to thank him for his great resources. As well I'd like to thank to blindwig for writing such a wonderful Binary Trees UDF which I find to be quite efficient and sophisticated. Currently, because of a limitation of facilities, it's not recommended to use this library to handle giant trees because it's dealing with great overhead of array assignments. Example 1: Using user defined callback function #include "BinaryTree.au3" Local $avTree = _BinaryTreeCreate(0, 0, "_ComparisonFunc") Local $vValue Local $sString For $i = 1 To 100 $sString = "" For $j = 1 To 5 $sString &= Chr(Random(65, 90, 1)) Next _BinaryTreeInsert($avTree, $sString, $i) ; Root, Key, Value Next _BinaryTreeInsert($avTree, "VWXYZ", 12345) $vValue = _BinaryTreeSearch($avTree, "VWXYZ") If Not @error Then ConsoleWrite($vValue & @CRLF & @CRLF) ConsoleWrite("====================================================================================================" & @CRLF) _BinaryTreePrint($avTree, $InOrderM) ConsoleWrite("====================================================================================================" & @CRLF) Func _ComparisonFunc($A, $B) Return StringCompare($A, $B) EndFunc Example 2: Persisting AVL tree to and loading an AVL tree from a file #include "BinaryTree.au3" Local $avTree = _BinaryTreeCreate(0, Round(Random(1, 10), 3)), $avTreeFromFile Local Const $sFileName = @ScriptDir & "BinaryTreeText.txt" For $i = 1 To 100 _BinaryTreeInsert($avTree, $i, Round(Random(1, 10), 3)) Next _BinaryTreeSaveToFile($avTree, $sFileName) $avTreeFromFile = _BinaryTreeLoadFromFile($sFileName) ConsoleWrite("====================================================================================================" & @CRLF) _BinaryTreePrint($avTreeFromFile, $InOrderM) ConsoleWrite("====================================================================================================" & @CRLF) ShellExecute($sFileName) ...and BinaryTree.au3: #include-once ; #INDEX# ======================================================================================================================= ; Title .........: AVL Trees (Balanced Binary Trees) ; Description ...: Manipulating AVL trees based data structures. ; =============================================================================================================================== ; #Constants# =================================================================================================================== #Region Constants and Enums Local Const $gConst__iNodeSize = 5 ; Exact size of a valid node which consists of the following structure in any order: [NodeKey, NodeVal, LeftNode, RightNode, NodeBalance] Local Enum $gConst__iKey, $gConst__iVal, $gConst__iLeft, $gConst__iRight, $gConst__iBalance ; The node elements, order doesn't matter. Local Enum $gConst__MIN_CMP = -1, $gConst__EQ_CMP, $gConst__MAX_CMP ; Comparison enumeration: -1 ($A < $B), 0 ($A = $B), 1 ($A > $B). Local Enum $gConst__LEFT_HEAVY = -1, $gConst__BALANCED, $gConst__RIGHT_HEAVY ; Internal, check if the tree is imbalance and rebalance as necessary. Local Enum $InOrder, $InOrderM, $PreOrder, $PostOrder ; _BinaryTreePrint parameter enumeration, read function description. #EndRegion Constants and Enums ; #VARIABLES# =================================================================================================================== #Region Callback Functions Local $__sGlobalCompFunc = "" ; Global comparison callback function, several functions call this function to insert/delete/search items. Local $__sGlobalSaveFunc = "" ; Global dump callback, read _BinaryTreeSaveToFile function description. Local $__sGlobalLoadFunc = "" ; Global load parser callback, read _BinaryTreeLoadFromFile. #EndRegion Callback Functions ; =============================================================================================================================== ; #CURRENT# ===================================================================================================================== ; _BinaryTreeCreate ; _BinaryTreeDelete ; _BinaryTreeInsert ; _BinaryTreeLoadFromFile ; _BinaryTreePrint ; _BinaryTreeSaveToFile ; _BinaryTreeSearch ; _BinaryTreeSetLoadFunc ; _BinaryTreeSetSaveFunc ; =============================================================================================================================== ; #INTERNAL_USE_ONLY / NO_DOC_FUNCTION#========================================================================================== ; __Max ; __Min ; _ArrayAssignArray ; _ArrayAssignValue ; _BinaryTreeCompare ; _BinaryTreeCompareWithFunc ; _BinaryTreeDeleteBal ; _BinaryTreeDeleteBalWithFunc ; _BinaryTreeFromArray ; _BinaryTreeFromArrayWithFunc ; _BinaryTreeGetPreOrder ; _BinaryTreeGetPreOrderWithFunc ; _BinaryTreeInsertBal ; _BinaryTreeInsertBalWithFunc ; _BinaryTreePrintIndent ; _BinaryTreeSearchNorm ; _BinaryTreeSearchWithFunc ; _Eval ; _LeftImbalance ; _ReBalance ; _RightImbalance ; _RotateOnce ; _RotateTwice ;============================================================================================================================== #Region Functions ; #FUNCTION# ==================================================================================================================== ; Name...........: _BinaryTreeCreate ; Description ...: Create a binary tree array and return the root. ; Syntax.........: _BinaryTreeCreate($iNode, $vNodeVal[, $sCompFunc = ""]) ; Parameters ....: $iNodeKey - Value of the node key. ; $vNodeVal - Value of the node value. ; $sCompFunc - User defined function name to call when trying to compare nodes keys, read remarks. ; ; Return values .: The binary tree root. ; ; Modified.......: ; Remarks .......: The global callback comparison function should be defined as _MyCompFunc($A, $B). The return value should be ; + -1 if $A < $B, 0 if $A = $B and 1 if $A>B. Several functions may call this function (if defined) to ; +determine how to traverse the binary tree, when inserting, searching or deleting items. ; Related .......: ; Example .......; No ; =============================================================================================================================== Func _BinaryTreeCreate($iNodeKey, $vNodeVal, $sCompFunc = "") Local $avRoot[$gConst__iNodeSize] $__sGlobalCompFunc = $sCompFunc $avRoot[$gConst__iKey] = $iNodeKey $avRoot[$gConst__iVal] = $vNodeVal $avRoot[$gConst__iBalance] = 0 Return $avRoot EndFunc ;==>_BinaryTreeCreate ; #FUNCTION# ==================================================================================================================== ; Name...........: _BinaryTreeDelete ; Description ...: Delete a node from the binary tree based on the node key. ; Syntax.........: _BinaryTreeDelete(ByRef $avRoot, $iNodeKey) ; Parameters ....: $avRoot - The binary tree root array as returned by _BinaryTreeCreate or _BinaryTreeLoadFromFile. ; $iNodeKey - The key of the node to delete. ; ; Return values .: Success, set @error to 0 and return an array containing the deleted item's key and value. The first index is ; +the key and the second is the value of the deleted node. ; Failure, set @error to 1 and return 0. Typically indicate that a node with key of $iNodeKey was not found. ; ; Modified.......: ; Remarks .......: Currently, @error value doesn't reflect the internal error that occurred, such as whether the value specified ; +by $avRoot is not a binary tree array or it doesn't contain a node with a key matching $iNodeVal. ; Related .......: _BinaryTreeCreate, _BinaryTreeLoadFromFile. ; Example .......; No ; =============================================================================================================================== Func _BinaryTreeDelete(ByRef $avRoot, $iNodeKey) Local $iChange = 0 Local $vReturn If $__sGlobalCompFunc <> "" Then $vReturn = _BinaryTreeDeleteBalWithFunc($avRoot, $iNodeKey, $iChange, $gConst__EQ_CMP) Else $vReturn = _BinaryTreeDeleteBal($avRoot, $iNodeKey, $iChange, $gConst__EQ_CMP) EndIf Return SetError(@error, @extended, $vReturn) EndFunc ;==>_BinaryTreeDelete ; #FUNCTION# ==================================================================================================================== ; Name...........: _BinaryTreeInsert ; Description ...: Insert a new node into the binary tree array. ; Syntax.........: _BinaryTreeInsert(ByRef $avRoot, $iNodeKey, $vNodeVal[, $fOverwrite = False]) ; Parameters ....: $avRoot - The binary tree root array as returned by _BinaryTreeCreate or _BinaryTreeLoadFromFile. ; $iNodeKey - The key of the node to insert or modify. ; $vNodeVal - The new value of the node to insert or modify, read remarks. ; $fOverwrite - If True then set the value of an existing node with a key of $iNodeKey, if exists. ; If False then doesn't set the value of an existing node with a key of $iNodeKey. ; ; Return values .: If $fOverwrite is True and a key with a value of $iNodeKey exists then set @error to 1 and return ; +the previous value of the node that it's value is replaced. If $fOverwrite is False and a key with a value ; +of $iNodeKey exists then set @error to 1 and return 0. The value if the node is not changed if $fOverwrite ; +is False. $fOverwrite doesn't matter if a key with a value of $iNodeKey doesn't exist. ; ; Modified.......: ; Remarks .......: Do not store dll structures pointers (as obtained by DllStructGetPtr) as the value of a node. The reference ; +counter of the structure is not increased by pointers to it and thus the memory address they refer to may not ; +contain a valid dll structure when trying to access it. DllStructCreate variables are valid though. ; Related .......: _BinaryTreeCreate, _BinaryTreeLoadFromFile. ; Example .......; No ; =============================================================================================================================== Func _BinaryTreeInsert(ByRef $avRoot, $iNodeKey, $vNodeVal, $fOverwrite = False) Local $iChange = 0 Local $vReturn If $__sGlobalCompFunc <> "" Then $vReturn = _BinaryTreeInsertBalWithFunc($avRoot, $iNodeKey, $vNodeVal, $fOverwrite, $iChange) Else $vReturn = _BinaryTreeInsertBal($avRoot, $iNodeKey, $vNodeVal, $fOverwrite, $iChange) EndIf Return SetError(@error, @extended, $vReturn) EndFunc ;==>_BinaryTreeInsert ; #FUNCTION# ==================================================================================================================== ; Name...........: _BinaryTreeLoadFromFile ; Description ...: Build a binary tree array from a file content. ; Syntax.........: _BinaryTreeLoadFromFile($sFileName[, $sCompFunc = ""]) ; Parameters ....: $sFileName - The name of the file to create the binary tree array from, read remarks. ; $sCompFunc - User defined function name to call when trying to compare nodes keys, refer To _BinaryTreeCreate ; +for more information about this parameter meaning. ; ; Return values .: Success, return the new binary tree array and set @error to 0. ; Failure, return 0 and set @error to: ; 1) The filename specific was empty, "". ; 2) Could not open the file for reading, either doesn't exist or can't be read. ; 3) File is empty ; 4) File content is malformed. ; ; Modified.......: ; Remarks .......: The file content should be in the form: NodeKey1,NodeVal1|NodeKey2,NodeVal2 ; It's permissible to include the characters "|" and "," as the node key or value as long as they're enclosed ; +within double quotes, e.g "a,b",12|c",d","34|" ; +Call _BinaryTreeSetLoadFunc to set a global callback function to parse the nodes keys and values. ; Related .......: _BinaryTreeCreate, _BinaryTreeSetLoadFunc. ; Example .......; No ; =============================================================================================================================== Func _BinaryTreeLoadFromFile($sFileName, $sCompFunc = "") Local $hFile, $sInput Local $avMatches, $avRoot If $sFileName = "" Then Return SetError(1, 0, 0) $hFile = FileOpen($sFileName, 0) If $hFile = -1 Then Return SetError(2, 0, 0) $sInput = FileRead($hFile) FileClose($hFile) If $sInput = "" Then Return SetError(3, 0, 0) $avMatches = StringRegExp($sInput, "\G(?:^|\|)((?>[^,""]*(?:""[^""]*"")?)+),((?>[^|""]*(?:""[^""]*"")?)+)", 3) If Not IsArray($avMatches) Or Mod(UBound($avMatches), 2) <> 0 Then Return SetError(4, 0, 0) $__sGlobalCompFunc = $sCompFunc If $__sGlobalLoadFunc <> "" Then _BinaryTreeFromArrayWithFunc($avRoot, $avMatches) Else _BinaryTreeFromArray($avRoot, $avMatches) EndIf Return SetError(0, 0, $avRoot) EndFunc ;==>_BinaryTreeLoadFromFile ; #FUNCTION# ==================================================================================================================== ; Name...........: _BinaryTreePrint ; Description ...: Print the binary tree array in a basic indented format using a traverse order. ; Syntax.........: _BinaryTreePrint(ByRef $avRoot, $iOrder) ; ; Parameters ....: $avRoot - The binary tree root array as returned by _BinaryTreeCreate or _BinaryTreeLoadFromFile. ; $iOrder - The order in which to traverse the binary tree array. Valid values are: ; |$InOrder - Traverse the binary tree in a left, root, right order promising an increasing tree output. ; +Topmost output is lesser than the middle which itself is lesser than the bottom output. ; |$InOrderM - Same as $InOrder but topmost output is greater than the middle which itself is greater than ; +the bottom output. ; |$PreOrder - Traverse the binary tree in a root, left, right order. Output is formatted as columns with ; +increasing lines. Within each column, each line is greater than the next line. ; |$PostOrder - Traverse the binary tree in a left, right, root order. Output is formatted as a mirrored ; +format of $PreOrder format but still, each line is greater than the next line. ; ; Return values .: Success, return True and set @error to 0. ; Failure, return False and set @error to 1, typically indicating that $avRoot as not a valid binary tree root. ; ; Modified.......: ; Remarks .......: ; Related .......: _BinaryTreeCreate, _BinaryTreeLoadFromFile. ; Example .......; No ; =============================================================================================================================== Func _BinaryTreePrint(ByRef $avRoot, $iOrder) If UBound($avRoot, 0) <> 1 Or UBound($avRoot) <> $gConst__iNodeSize Then Return SetError(1, 0, False) If $iOrder < $InOrder Or $iOrder > $PostOrder Then $iOrder = $InOrder _BinaryTreePrintIndent($avRoot, $iOrder, 0) Return SetError(0, 0, True) EndFunc ;==>_BinaryTreePrint ; #FUNCTION# ==================================================================================================================== ; Name...........: _BinaryTreeSaveToFile ; Description ...: Persist the binary tree array to a file. ; Syntax.........: _BinaryTreeSaveToFile(ByRef $avRoot, $sFileName) ; Parameters ....: $avRoot - The binary tree root array as returned by _BinaryTreeCreate or _BinaryTreeLoadFromFile. ; $sFileName - The name of the file to persist the binary tree array to. ; ; Return values .: Success, return True and set @error to 0. ; Failure, return False and set @error to: ; 1) The filename specific was empty, "". ; 2) $avRoot is not a valid binary tree root. ; 3) Could not open the file for writing. ; ; Modified.......: ; Remarks .......: Call _BinaryTreeSetSaveFunc to set a global callback function to parse and persist the nodes keys and values. ; Related .......: _BinaryTreeCreate, _BinaryTreeLoadFromFile, _BinaryTreeSetSaveFunc. ; Example .......; No ; =============================================================================================================================== Func _BinaryTreeSaveToFile(ByRef $avRoot, $sFileName) Local $hFile, $sOutput = "" If UBound($avRoot, 0) <> 1 Or UBound($avRoot) <> $gConst__iNodeSize Then Return SetError(2, 0, False) If $sFileName = "" Then Return SetError(1, 0, False) $hFile = FileOpen($sFileName, 2) If $hFile = -1 Then Return SetError(3, 0, False) If $__sGlobalSaveFunc <> "" Then _BinaryTreeGetPreOrderWithFunc($avRoot, $sOutput) Else _BinaryTreeGetPreOrder($avRoot, $sOutput) EndIf FileWrite($hFile, StringTrimRight($sOutput, 1)) FileClose($hFile) Return SetError(0, 0, True) EndFunc ;==>_BinaryTreeSaveToFile ; #FUNCTION# ==================================================================================================================== ; Name...........: _BinaryTreeSearch ; Description ...: Search the binary tree array for a key. ; Syntax.........: _BinaryTreeSearch(ByRef $avRoot, $iNodeKey) ; Parameters ....: $avRoot - The binary tree root array as returned by _BinaryTreeCreate or _BinaryTreeLoadFromFile. ; $iNodeKey - The key of the node to search in the binary tree array. ; ; Return values .: Success, return the value held in a node with a key with a value of $iNodeKey and set @error to 0. ; Failure, return -1 and set @error to 1 indicating either, $avRoot is not a valid binary tree root or a key ; +with a value of $iNodeKey could not be found in the binary tree array. ; ; Modified.......: ; Remarks .......: Currently, @error value doesn't reflect the internal error that occurred, such as whether the value specified ; +by $avRoot is not a binary tree array or it doesn't contain a node with a key matching $iNodeVal. ; Related .......: _BinaryTreeCreate, _BinaryTreeLoadFromFile. ; Example .......; No ; =============================================================================================================================== Func _BinaryTreeSearch(ByRef $avRoot, $iNodeKey) Local $vReturn If $__sGlobalCompFunc <> "" Then $vReturn = _BinaryTreeSearchWithFunc($avRoot, $iNodeKey) Else $vReturn = _BinaryTreeSearchNorm($avRoot, $iNodeKey) EndIf Return SetError(@error, @extended, $vReturn) EndFunc ;==>_BinaryTreeSearch ; #FUNCTION# ==================================================================================================================== ; Name...........: _BinaryTreeSetLoadFunc ; Description ...: Set a global user defined callback function to call when creating the binary tree array from a file. ; Syntax.........: _BinaryTreeSetLoadFunc([$sNewLoadFunc = ""]) ; Parameters ....: $sNewLoadFunc - The new global callback function to call. Default value "" will reset the global function to ; +nothing. The default algorithm when the function is not set is to parse the key and value pairs as they are, ; +i.e. nothing is assumed and they're parsed in string context. ; ; Return values .: The previous global callback load function. ; ; Modified.......: ; Remarks .......: The global callback loading function should be defined as _MyLoadFunc($Key, $Value). The function should ; +return an array with size of 2. The first element is assumed to be the key and the second is assumed to be ; +the value. On function entrance the algorithm can parse the string based elements and return different ; +values as an array. For example dll structs (not pointers) from [X,Y] $Value, as the value of the node. ; Related .......: _BinaryTreeLoadFromFile. ; Example .......; No ; =============================================================================================================================== Func _BinaryTreeSetLoadFunc($sNewLoadFunc = "") Local $sPrevLoadFunc = $__sGlobalLoadFunc $__sGlobalLoadFunc = $sNewLoadFunc Return $sPrevLoadFunc EndFunc ;==>_BinaryTreeSetLoadFunc ; #FUNCTION# ==================================================================================================================== ; Name...........: _BinaryTreeSetSaveFunc ; Description ...: Set a global user defined callback function to call when persisting a binary tree array to a file. ; Syntax.........: _BinaryTreeSetSaveFunc($sNewSaveFunc = "") ; Parameters ....: $sNewSaveFunc - The new global callback function to call. Default value "" will reset the global function to ; +nothing. The default algorithm when the function is not set is to parse the key and value pairs as they are, ; +i.e. nothing is assumed and they're parsed in string context. ; ; Return values .: The previous global callback save function. ; ; Modified.......: ; Remarks .......: The global callback saving function should be defined as _MySaveFunc($Key, $Value). The function should ; +return a string representation of the $Key and $Value elements separated by a comma "," to persist to a file. ; +It's permissible to use the characters "|" and "," in the string as long as they're enclosed within double ; +quotes, e.g "[X,Y]","{Y|X}" ; Related .......: _BinaryTreeLoadFromFile. ; Example .......; No ; =============================================================================================================================== Func _BinaryTreeSetSaveFunc($sNewSaveFunc = "") Local $sPrevSaveFunc = $__sGlobalSaveFunc $__sGlobalSaveFunc = $sNewSaveFunc Return $sPrevSaveFunc EndFunc ;==>_BinaryTreeSetSaveFunc #EndRegion Functions ; =============================================================================================================================== ; #INTERNAL_USE_ONLY / NO_DOC_FUNCTION# ========================================================================================= #Region Internal functions Func __Max($A, $B) If $A > $B Then Return $A Return $B EndFunc ;==>__Max Func __Min($A, $B) If $A < $B Then Return $A Return $B EndFunc ;==>__Min Func _ArrayAssignArray(ByRef $avArr1, $iElement, ByRef $avArr2) $avArr1[$iElement] = $avArr2 EndFunc ;==>_ArrayAssignArray Func _ArrayAssignValue(ByRef $avArr, $iElement, $vValue) $avArr[$iElement] = $vValue EndFunc ;==>_ArrayAssignValue Func _BinaryTreeCompare(ByRef $avRoot, $iNodeKey, $iCmp) Switch $iCmp Case $gConst__EQ_CMP If $iNodeKey = $avRoot[$gConst__iKey] Then Return $gConst__EQ_CMP ElseIf $iNodeKey < $avRoot[$gConst__iKey] Then Return $gConst__MIN_CMP Else Return $gConst__MAX_CMP EndIf Case $gConst__MIN_CMP If IsArray($avRoot[$gConst__iLeft]) Then Return $gConst__MIN_CMP Else Return $gConst__EQ_CMP EndIf Case Else If IsArray($avRoot[$gConst__iRight]) Then Return $gConst__MAX_CMP Else Return $gConst__EQ_CMP EndIf EndSwitch EndFunc ;==>_BinaryTreeCompare Func _BinaryTreeCompareWithFunc(ByRef $avRoot, $iNodeKey, $iCmp) Local $iComp Switch $iCmp Case $gConst__EQ_CMP $iComp = Call($__sGlobalCompFunc, $iNodeKey, $avRoot[$gConst__iKey]) If $iComp = 0 Then Return $gConst__EQ_CMP ElseIf $iComp = -1 Then Return $gConst__MIN_CMP Else Return $gConst__MAX_CMP EndIf Case $gConst__MIN_CMP If IsArray($avRoot[$gConst__iLeft]) Then Return $gConst__MIN_CMP Else Return $gConst__EQ_CMP EndIf Case Else If IsArray($avRoot[$gConst__iRight]) Then Return $gConst__MAX_CMP Else Return $gConst__EQ_CMP EndIf EndSwitch EndFunc ;==>_BinaryTreeCompareWithFunc Func _BinaryTreeDeleteBal(ByRef $avRoot, $iNodeKey, ByRef $iChange, $iCmp) Local $iCmpRes, $iDir = $gConst__iRight, $iDecrease = 0 Local $vReturn[2] Local $fLeftNode, $fRightNode If Not IsArray($avRoot) Then $iChange = 0 Return SetError(1, 0, 0) EndIf $iCmpRes = _BinaryTreeCompare($avRoot, $iNodeKey, $iCmp) If $iCmpRes = $gConst__MIN_CMP Then $iDir = $gConst__iLeft If $iCmpRes <> $gConst__EQ_CMP Then $vReturn = _BinaryTreeDeleteBal($avRoot[$iDir], $iNodeKey, $iChange, $iCmp) If @error Then Return SetError(@error, @extended, 0) $iDecrease = $iCmpRes * $iChange Else $vReturn[0] = $avRoot[$gConst__iKey] $vReturn[1] = $avRoot[$gConst__iVal] $fLeftNode = IsArray($avRoot[$gConst__iLeft]) $fRightNode = IsArray($avRoot[$gConst__iRight]) If $fLeftNode = 0 And $fRightNode = 0 Then $avRoot = 0 $iChange = 1 Return $vReturn ElseIf $fLeftNode = 0 Or $fRightNode = 0 Then If $fLeftNode Then $avRoot = $avRoot[$gConst__iLeft] Else $avRoot = $avRoot[$gConst__iRight] EndIf $iChange = 1 Return $vReturn Else $vReturn = _BinaryTreeDeleteBal($avRoot[$gConst__iLeft], $iNodeKey, $iDecrease, $gConst__MAX_CMP) $avRoot[$gConst__iKey] = $vReturn[$gConst__iKey] $avRoot[$gConst__iVal] = $vReturn[$gConst__iVal] EndIf EndIf $avRoot[$gConst__iBalance] -= $iDecrease If $iDecrease Then If $avRoot[$gConst__iBalance] Then $iChange = _ReBalance($avRoot) Else $iChange = 1 EndIf Else $iChange = 0 EndIf Return $vReturn EndFunc ;==>_BinaryTreeDeleteBal Func _BinaryTreeDeleteBalWithFunc(ByRef $avRoot, $iNodeKey, ByRef $iChange, $iCmp) Local $iCmpRes, $iDir = $gConst__iRight, $iDecrease = 0 Local $vReturn[2] Local $fLeftNode, $fRightNode If Not IsArray($avRoot) Then $iChange = 0 Return SetError(1, 0, 0) EndIf $iCmpRes = _BinaryTreeCompareWithFunc($avRoot, $iNodeKey, $iCmp) If $iCmpRes = $gConst__MIN_CMP Then $iDir = $gConst__iLeft If $iCmpRes <> $gConst__EQ_CMP Then $vReturn = _BinaryTreeDeleteBalWithFunc($avRoot[$iDir], $iNodeKey, $iChange, $iCmp) If @error Then Return SetError(@error, @extended, 0) $iDecrease = $iCmpRes * $iChange Else $vReturn[0] = $avRoot[$gConst__iKey] $vReturn[1] = $avRoot[$gConst__iVal] $fLeftNode = IsArray($avRoot[$gConst__iLeft]) $fRightNode = IsArray($avRoot[$gConst__iRight]) If $fLeftNode = 0 And $fRightNode = 0 Then $avRoot = 0 $iChange = 1 Return $vReturn ElseIf $fLeftNode = 0 Or $fRightNode = 0 Then If $fLeftNode Then $avRoot = $avRoot[$gConst__iLeft] Else $avRoot = $avRoot[$gConst__iRight] EndIf $iChange = 1 Return $vReturn Else $vReturn = _BinaryTreeDeleteBalWithFunc($avRoot[$gConst__iLeft], $iNodeKey, $iDecrease, $gConst__MAX_CMP) $avRoot[$gConst__iKey] = $vReturn[$gConst__iKey] $avRoot[$gConst__iVal] = $vReturn[$gConst__iVal] EndIf EndIf $avRoot[$gConst__iBalance] -= $iDecrease If $iDecrease Then If $avRoot[$gConst__iBalance] Then $iChange = _ReBalance($avRoot) Else $iChange = 1 EndIf Else $iChange = 0 EndIf Return $vReturn EndFunc ;==>_BinaryTreeDeleteBalWithFunc Func _BinaryTreeFromArray(ByRef $avRoot, ByRef $avMatches) For $i = 0 To UBound($avMatches) - 2 Step 2 _BinaryTreeInsert($avRoot, $avMatches[$i], $avMatches[$i + 1]) Next EndFunc ;==>_BinaryTreeFromArray Func _BinaryTreeFromArrayWithFunc(ByRef $avRoot, ByRef $avMatches) Local $avNode For $i = 0 To UBound($avMatches) - 2 Step 2 $avNode = Call($__sGlobalLoadFunc, $avMatches[$i], $avMatches[$i + 1]) If UBound($avNode, 0) = 1 And UBound($avNode) = 2 Then _ _BinaryTreeInsert($avRoot, $avNode[0], $avNode[1]) Next EndFunc ;==>_BinaryTreeFromArrayWithFunc Func _BinaryTreeGetPreOrder(ByRef $avRoot, ByRef $sOutput) If UBound($avRoot, 0) <> 1 Or UBound($avRoot) <> $gConst__iNodeSize Then Return $sOutput &= $avRoot[$gConst__iKey] & "," & $avRoot[$gConst__iVal] & "|" _BinaryTreeGetPreOrder($avRoot[$gConst__iLeft], $sOutput) _BinaryTreeGetPreOrder($avRoot[$gConst__iRight], $sOutput) EndFunc ;==>_BinaryTreeGetPreOrder Func _BinaryTreeGetPreOrderWithFunc(ByRef $avRoot, ByRef $sOutput) If UBound($avRoot, 0) <> 1 Or UBound($avRoot) <> $gConst__iNodeSize Then Return $sOutput &= Call($__sGlobalSaveFunc, $avRoot[$gConst__iKey], $avRoot[$gConst__iVal]) & "|" _BinaryTreeGetPreOrderWithFunc($avRoot[$gConst__iLeft], $sOutput) _BinaryTreeGetPreOrderWithFunc($avRoot[$gConst__iRight], $sOutput) EndFunc ;==>_BinaryTreeGetPreOrderWithFunc Func _BinaryTreeInsertBal(ByRef $avRoot, $iNodeKey, $vNodeVal, $fOverwrite, ByRef $iChange) Local $iIncrease = -1, $iDir = $gConst__iLeft Local $vReturn If UBound($avRoot, 0) <> 1 Or UBound($avRoot) <> $gConst__iNodeSize Then Local $avNode[$gConst__iNodeSize] $avNode[$gConst__iKey] = $iNodeKey $avNode[$gConst__iVal] = $vNodeVal $avNode[$gConst__iBalance] = 0 $iChange = 1 $avRoot = $avNode Return SetError(0, 0, 0) EndIf If $iNodeKey <> $avRoot[$gConst__iKey] Then If $iNodeKey > $avRoot[$gConst__iKey] Then $iDir = $gConst__iRight $iIncrease = 1 EndIf $vReturn = _BinaryTreeInsertBal($avRoot[$iDir], $iNodeKey, $vNodeVal, $fOverwrite, $iChange) If @error Then If $fOverwrite Then Return SetError(0, 0, $vReturn) Return SetError(1, 0, 0) EndIf $iIncrease *= $iChange Else If $fOverwrite Then Local $vTempValue = $avRoot[$gConst__iVal] $avRoot[$gConst__iVal] = $vNodeVal Return SetError(1, 0, $vTempValue) EndIf Return SetError(1, 0, 0) EndIf $avRoot[$gConst__iBalance] += $iIncrease $iChange = 0 If $iIncrease And $avRoot[$gConst__iBalance] Then $iChange = 1 - _ReBalance($avRoot) Return SetError(0, 0, $vReturn) EndFunc ;==>_BinaryTreeInsertBal Func _BinaryTreeInsertBalWithFunc(ByRef $avRoot, $iNodeKey, $vNodeVal, $fOverwrite, ByRef $iChange) Local $iIncrease = -1, $iDir = $gConst__iLeft, $iComp Local $vReturn If UBound($avRoot, 0) <> 1 Or UBound($avRoot) <> $gConst__iNodeSize Then Local $avNode[$gConst__iNodeSize] $avNode[$gConst__iKey] = $iNodeKey $avNode[$gConst__iVal] = $vNodeVal $avNode[$gConst__iBalance] = 0 $iChange = 1 $avRoot = $avNode Return SetError(0, 0, 0) EndIf $iComp = Call($__sGlobalCompFunc, $iNodeKey, $avRoot[$gConst__iKey]) If $iComp <> 0 Then If $iComp = 1 Then $iDir = $gConst__iRight $iIncrease = 1 EndIf $vReturn = _BinaryTreeInsertBalWithFunc($avRoot[$iDir], $iNodeKey, $vNodeVal, $fOverwrite, $iChange) If @error Then If $fOverwrite Then Return SetError(0, 0, $vReturn) Return SetError(1, 0, 0) EndIf $iIncrease *= $iChange Else If $fOverwrite Then Local $vTempValue = $avRoot[$gConst__iVal] $avRoot[$gConst__iVal] = $vNodeVal Return SetError(1, 0, $vTempValue) EndIf Return SetError(1, 0, 0) EndIf $avRoot[$gConst__iBalance] += $iIncrease $iChange = 0 If $iIncrease And $avRoot[$gConst__iBalance] Then $iChange = 1 - _ReBalance($avRoot) Return SetError(0, 0, $vReturn) EndFunc ;==>_BinaryTreeInsertBalWithFunc Func _BinaryTreePrintIndent(ByRef $avRoot, $iOrder, $iDepth) If UBound($avRoot, 0) <> 1 Or UBound($avRoot) <> $gConst__iNodeSize Then Return Local $sOutput = StringFormat("%" & $iDepth & "s[%s,%s]\r\n", " ", $avRoot[$gConst__iKey], $avRoot[$gConst__iVal]) Switch $iOrder Case $InOrder _BinaryTreePrintIndent($avRoot[$gConst__iLeft], $iOrder, StringLen($sOutput)) ConsoleWrite($sOutput) _BinaryTreePrintIndent($avRoot[$gConst__iRight], $iOrder, StringLen($sOutput)) Case $InOrderM _BinaryTreePrintIndent($avRoot[$gConst__iRight], $iOrder, StringLen($sOutput)) ConsoleWrite($sOutput) _BinaryTreePrintIndent($avRoot[$gConst__iLeft], $iOrder, StringLen($sOutput)) Case $PreOrder ConsoleWrite($sOutput) _BinaryTreePrintIndent($avRoot[$gConst__iLeft], $iOrder, StringLen($sOutput)) _BinaryTreePrintIndent($avRoot[$gConst__iRight], $iOrder, StringLen($sOutput)) Case Else _BinaryTreePrintIndent($avRoot[$gConst__iLeft], $iOrder, StringLen($sOutput)) _BinaryTreePrintIndent($avRoot[$gConst__iRight], $iOrder, StringLen($sOutput)) ConsoleWrite($sOutput) EndSwitch EndFunc ;==>_BinaryTreePrintIndent Func _BinaryTreeSearchNorm(ByRef $avRoot, $iNodeKey) Local $avNode = $avRoot While UBound($avNode, 0) = 1 And UBound($avNode, 1) = $gConst__iNodeSize If $iNodeKey < $avNode[$gConst__iKey] Then $avNode = $avNode[$gConst__iLeft] ElseIf $iNodeKey > $avNode[$gConst__iKey] Then $avNode = $avNode[$gConst__iRight] Else Return SetError(0, 0, $avNode[$gConst__iVal]) EndIf WEnd Return SetError(1, 0, -1) EndFunc ;==>_BinaryTreeSearchNorm Func _BinaryTreeSearchWithFunc(ByRef $avRoot, $iNodeKey) Local $avNode = $avRoot Local $iComp While UBound($avNode, 0) = 1 And UBound($avNode, 1) = $gConst__iNodeSize $iComp = Call($__sGlobalCompFunc, $iNodeKey, $avNode[$gConst__iKey]) If $iComp = -1 Then $avNode = $avNode[$gConst__iLeft] ElseIf $iComp = 1 Then $avNode = $avNode[$gConst__iRight] Else Return SetError(0, 0, $avNode[$gConst__iVal]) EndIf WEnd Return SetError(1, 0, -1) EndFunc ;==>_BinaryTreeSearchWithFunc Func _Eval(ByRef $avArr, $iElement) Return $avArr[$iElement] EndFunc ;==>_Eval Func _LeftImbalance($iBal) Return $iBal < $gConst__LEFT_HEAVY EndFunc ;==>_LeftImbalance Func _ReBalance(ByRef $avRoot) Local $iChange = 0 If _LeftImbalance($avRoot[$gConst__iBalance]) Then If _Eval($avRoot[$gConst__iLeft], $gConst__iBalance) = $gConst__RIGHT_HEAVY Then $iChange = _RotateTwice($avRoot, $gConst__iRight) Else $iChange = _RotateOnce($avRoot, $gConst__iRight) EndIf ElseIf _RightImbalance($avRoot[$gConst__iBalance]) Then If _Eval($avRoot[$gConst__iRight], $gConst__iBalance) = $gConst__LEFT_HEAVY Then $iChange = _RotateTwice($avRoot, $gConst__iLeft) Else $iChange = _RotateOnce($avRoot, $gConst__iLeft) EndIf EndIf Return $iChange EndFunc ;==>_ReBalance Func _RightImbalance($iBal) Return $iBal > $gConst__RIGHT_HEAVY EndFunc ;==>_RightImbalance Func _RotateOnce(ByRef $avRoot, $iDir) Local $avOldRoot = $avRoot Local $iOppDir = $gConst__iLeft, $iChange = 0 If $iDir = $gConst__iLeft Then $iOppDir = $gConst__iRight If _Eval($avRoot[$iOppDir], $gConst__iBalance) Then $iChange = 1 $avRoot = $avRoot[$iOppDir] $avOldRoot[$iOppDir] = $avRoot[$iDir] $avRoot[$iDir] = $avOldRoot If $iDir = $gConst__iLeft Then $avRoot[$gConst__iBalance] -= 1 Else $avRoot[$gConst__iBalance] += 1 EndIf _ArrayAssignValue($avRoot[$iDir], $gConst__iBalance, -$avRoot[$gConst__iBalance]) Return $iChange EndFunc ;==>_RotateOnce Func _RotateTwice(ByRef $avRoot, $iDir) Local $avOldRoot = $avRoot, $avSubDir Local $iOppDir = $gConst__iLeft If $iDir = $gConst__iLeft Then $iOppDir = $gConst__iRight $avSubDir = $avRoot[$iOppDir] $avRoot = _Eval($avRoot[$iOppDir], $iDir) $avOldRoot[$iOppDir] = $avRoot[$iDir] $avRoot[$iDir] = $avOldRoot $avSubDir[$iDir] = $avRoot[$iOppDir] $avRoot[$iOppDir] = $avSubDir _ArrayAssignValue($avRoot[$gConst__iLeft], $gConst__iBalance, -__Max($avRoot[$gConst__iBalance], 0)) _ArrayAssignValue($avRoot[$gConst__iRight], $gConst__iBalance, -__Min($avRoot[$gConst__iBalance], 0)) $avRoot[$gConst__iBalance] = 0; Return 1 EndFunc ;==>_RotateTwice #EndRegion Internal functions Forgive me I didn't decorate the internal functions with descriptive remarks, it's still not 100% done. Note: Do not store dll struct pointer (DllStructGetPtr) as the key or the value of a node. As I came to understand by monoceres's explanation, dll pointer to dll structure does not increase the structure's reference counter which means it may already be garbage collected by the time you're trying to reference it using it's pointer.
  • 3 replies