AVL Trees

Authenticity · November 16, 2009

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.

UEZ · November 16, 2009

This reminds me of my days at the University!

Nice implementation.

UEZ

Dolemite50 · November 17, 2009

OK, this is the return I got from Example 1:

[ZSDXH,85]
                                                                        [ZMECS,89]
                                                [YKJGR,58]
                                                            [YESBW,16]
                                    [YCZGJ,31]
                                                            [XZZRP,46]
                                                [XONUA,67]
                                                            [XNZYX,11]
                        [XNHQO,15]
                                                                        [XMRFI,76]
                                                            [XHQRE,39]
                                                [XGPRY,36]
                                                                        [XGLQG,90]
                                                            [WZCNO,65]
                                                                        [WNRJF,49]
                                    [WIWLF,21]
                                                                        [WGZVR,38]
                                                                                    [VWXYZ,12345]
                                                            [VQKRM,43]
                                                                        [VPXJF,18]
                                                [VPPYB,45]
                                                                        [VOWDI,70]
                                                            [VDOHL,63]
                                                                        [UZWIT,83]
            [UVIWF,10]
                                                                                  [UUVRP,100]
                                                                      [UUMYC,93]
                                                          [UPZOZ,99]
                                                                                  [UIIPW,91]
                                                                      [TLFCK,23]
                                                                                  [TBPAR,35]
                                               [SYUDY,4]
                                                                      [SWYSB,80]
                                                          [SSPDF,52]
                                                                      [SSHTR,98]
                                   [SQWNT,61]
                                                           [SCLJX,72]
                                               [RVMBY,57]
                                                                       [RMQQN,37]
                                                           [RKARZ,19]
                                                                       [RIRPD,42]
                        [RIQHP,5]
                                                                      [QNJFP,75]
                                                          [QHEAD,69]
                                                                      [QBGCC,86]
                                              [PPFIU,53]
                                                                      [PDCAO,84]
                                                          [OXPEW,12]
                                                                      [OXNLR,27]
                                   [OICRC,8]
                                                                      [OCANU,13]
                                                          [NGCXO,77]
                                                                      [NDRDQ,51]
                                              [NCPMS,40]
                                                                      [NBTUN,74]
                                                          [MWPQG,28]
                                                                                  [MHINH,78]
                                                                      [MCVKG,22]
                                                                                  [LZCNE,96]
 [LYLZF,3]
                                                                       [LGNHH,94]
                                                            [KYCFT,7]
                                                [KQYFJ,47]
                                                                        [KEZSU,87]
                                                            [KBXXF,33]
                                    [KBCGW,24]
                                                            [JARMO,48]
                                                [JAHFQ,41]
                                                            [IXMZF,54]
                                                                        [IIVET,66]
                        [IHVEW,32]
                                                                        [IHEDR,20]
                                                                                    [IGYFO,95]
                                                            [IBJHF,81]
                                                                                    [HUCWX,97]
                                                                        [GYPIU,55]
                                                [GTFGR,14]
                                                                        [GQHEH,73]
                                                            [GNFOY,68]
                                    [GKOMS,62]
                                                                        [GKMTQ,82]
                                                            [GIMKQ,17]
                                                [FYRDZ,26]
                                                                        [FXHPV,56]
                                                            [EZGJC,34]
            [EKIGU,25]
                                                         [EEZVP,44]
                                              [DYLUW,9]
                                   [DYCHO,6]
                                                          [DKPOQ,60]
                                                                      [DEWJX,64]
                                              [DELQY,30]
                                                                      [CKKKD,29]
                                                          [CARHK,92]
                                                                      [BTJQZ,79]
                        [BRSOO,1]
                                                           [BRGCE,88]
                                               [BHELZ,71]
                                                           [AXIUE,2]
                                   [ANSUL,50]
                                                      [AGFEM,59]
                                               [0,0]

Yep! Just as expected! That crazy function of yours sure knows how to do some good ol' binary treein'!

Vlasssov · October 7, 2010

When I have started a program that have received a error

C:\Program Files\AutoIt3\Include\_BinaryTrEE.au3 (85) : ==> Unable to parse line.:
Local $avRoot[$gConst__iNodeSize]
^ ERROR

What is it?

oops... It`s my problem... All rights!!

Edited October 7, 2010 by Vlasssov

Sign In

AVL Trees

Recommended Posts

Authenticity

Link to comment

Share on other sites

UEZ

Link to comment

Share on other sites

Dolemite50

Link to comment

Share on other sites

Vlasssov

Link to comment

Share on other sites

Create an account or sign in to comment

Create an account

Sign in

Recently Browsing 0 members

Browse

AutoIt Resources

Release

Beta