Jump to content

Red-Black Tree Implementation in AutoIt

LAteNightSpecial
 Share

Recommended Posts

LAteNightSpecial Seeker

LAteNightSpecial

Posted
Posted

This script is not yet complete, but I'm looking for some ideas on furthering the functionality. Any input from the community is welcome and appreciated.

RedBlackTree.au3 

; Red-Black Tree Implementation in AutoIt

Global Const $RB_RED = 0
Global Const $RB_BLACK = 1

; Red-Black tree node structure
Global Const $tagRBNode = "ptr Parent;ptr Left;ptr Right;int Data;int Color"

; Function to create a Red-Black tree node
Func _RBNodeCreate($iData)
    Local $pNode = DllStructCreate($tagRBNode)
    DllStructSetData($pNode, "Data", $iData)
    Return $pNode
EndFunc

; Function to insert a new element into the Red-Black tree
Func _RBInsert(ByRef $pRoot, $iData)
    Local $pNewNode = _RBNodeCreate($iData)
    If Not $pRoot Then
        $pRoot = $pNewNode
        DllStructSetData($pRoot, "Color", $RB_BLACK) ; Root node is always black
        Return
    EndIf
    
    Local $pParent = 0
    Local $pCurrent = $pRoot
    
    ; Find the parent node for insertion
    While $pCurrent
        $pParent = $pCurrent
        If $iData < DllStructGetData($pCurrent, "Data") Then
            $pCurrent = DllStructGetData($pCurrent, "Left")
        Else
            $pCurrent = DllStructGetData($pCurrent, "Right")
        EndIf
    WEnd
    
    ; Set the parent for the new node
    DllStructSetData($pNewNode, "Parent", $pParent)
    
    ; Insert the new node as left or right child of the parent
    If $iData < DllStructGetData($pParent, "Data") Then
        DllStructSetData($pParent, "Left", $pNewNode)
    Else
        DllStructSetData($pParent, "Right", $pNewNode)
    EndIf
    
    ; Fix any Red-Black tree violations
    _RBInsertFixup($pRoot, $pNewNode)
EndFunc

; Function to fix Red-Black tree violations after insertion
Func _RBInsertFixup(ByRef $pRoot, $pNode)
    Local $pParent = 0
    Local $pGrandparent = 0
    Local $pUncle = 0
    
    While DllStructGetData($pNode, "Parent") And DllStructGetData(DllStructGetData($pNode, "Parent"), "Color") = $RB_RED
        $pParent = DllStructGetData($pNode, "Parent")
        $pGrandparent = DllStructGetData($pParent, "Parent")
        
        If $pParent = DllStructGetData($pGrandparent, "Left") Then
            $pUncle = DllStructGetData($pGrandparent, "Right")
            If $pUncle And DllStructGetData($pUncle, "Color") = $RB_RED Then
                DllStructSetData($pParent, "Color", $RB_BLACK)
                DllStructSetData($pUncle, "Color", $RB_BLACK)
                DllStructSetData($pGrandparent, "Color", $RB_RED)
                $pNode = $pGrandparent
            Else
                If $pNode = DllStructGetData($pParent, "Right") Then
                    $pNode = $pParent
                    _RBLeftRotate($pRoot, $pNode)
                EndIf
                DllStructSetData($pParent, "Color", $RB_BLACK)
                DllStructSetData($pGrandparent, "Color", $RB_RED)
                _RBRightRotate($pRoot, $pGrandparent)
            EndIf
        Else
            $pUncle = DllStructGetData($pGrandparent, "Left")
            If $pUncle And DllStructGetData($pUncle, "Color") = $RB_RED Then
                DllStructSetData($pParent, "Color", $RB_BLACK)
                DllStructSetData($pUncle, "Color", $RB_BLACK)
                DllStructSetData($pGrandparent, "Color", $RB_RED)
                $pNode = $pGrandparent
            Else
                If $pNode = DllStructGetData($pParent, "Left") Then
                    $pNode = $pParent
                    _RBRightRotate($pRoot, $pNode)
                EndIf
                DllStructSetData($pParent, "Color", $RB_BLACK)
                DllStructSetData($pGrandparent, "Color", $RB_RED)
                _RBLeftRotate($pRoot, $pGrandparent)
            EndIf
        EndIf
    WEnd
    
    DllStructSetData($pRoot, "Color", $RB_BLACK) ; Ensure root node is always black
EndFunc

; Function to perform left rotation in the Red-Black tree
Func _RBLeftRotate(ByRef $pRoot, $pNode)
    Local $pRightChild = DllStructGetData($pNode, "Right")
    DllStructSetData($pNode, "Right", DllStructGetData($pRightChild, "Left"))
    If DllStructGetData(DllStructGetData($pRightChild, "Left"), "Left") Then
        DllStructSetData(DllStructGetData($pRightChild, "Left"), "Parent", $pNode)
    EndIf
    DllStructSetData($pRightChild, "Parent", DllStructGetData($pNode, "Parent"))
    If Not DllStructGetData($pNode, "Parent") Then
        $pRoot = $pRightChild
    ElseIf $pNode = DllStructGetData(DllStructGetData($pNode, "Parent"), "Left") Then
        DllStructSetData(DllStructGetData($pNode, "Parent"), "Left", $pRightChild)
    Else
        DllStructSetData(DllStructGetData($pNode, "Parent"), "Right", $pRightChild)
    EndIf
    DllStructSetData($pRightChild, "Left", $pNode)
    DllStructSetData($pNode, "Parent", $pRightChild)
EndFunc

; Function to perform right rotation in the Red-Black tree
Func _RBRightRotate(ByRef $pRoot, $pNode)
    Local $pLeftChild = DllStructGetData($pNode, "Left")
    DllStructSetData($pNode, "Left", DllStructGetData($pLeftChild, "Right"))
    If DllStructGetData(DllStructGetData($pLeftChild, "Right"), "Right") Then
        DllStructSetData(DllStructGetData($pLeftChild, "Right"), "Parent", $pNode)
    EndIf
    DllStructSetData($pLeftChild, "Parent", DllStructGetData($pNode, "Parent"))
    If Not DllStructGetData($pNode, "Parent") Then
        $pRoot = $pLeftChild
    ElseIf $pNode = DllStructGetData(DllStructGetData($pNode, "Parent"), "Right") Then
        DllStructSetData(DllStructGetData($pNode, "Parent"), "Right", $pLeftChild)
    Else
        DllStructSetData(DllStructGetData($pNode, "Parent"), "Left", $pLeftChild)
    EndIf
    DllStructSetData($pLeftChild, "Right", $pNode)
    DllStructSetData($pNode, "Parent", $pLeftChild)
EndFunc

; Function to search for an element in the Red-Black tree
Func _RBSearch($pRoot, $iData)
    Local $pNode = $pRoot
    While $pNode And DllStructGetData($pNode, "Data") <> $iData
        If $iData < DllStructGetData($pNode, "Data") Then
            $pNode = DllStructGetData($pNode, "Left")
        Else
            $pNode = DllStructGetData($pNode, "Right")
        EndIf
    WEnd
    Return $pNode
EndFunc

; Function to delete a node from the Red-Black tree
Func _RBDelete(ByRef $pRoot, $iData)
    Local $pNodeToDelete = _RBSearch($pRoot, $iData)
    If Not $pNodeToDelete Then Return
    
    Local $pParent = DllStructGetData($pNodeToDelete, "Parent")
    Local $pChild
    Local $originalColor = DllStructGetData($pNodeToDelete, "Color")
    
    If DllStructGetData($pNodeToDelete, "Left") = 0 Then
        $pChild = DllStructGetData($pNodeToDelete, "Right")
        _RBTransplant($pRoot, $pNodeToDelete, $pChild)
    ElseIf DllStructGetData($pNodeToDelete, "Right") = 0 Then
        $pChild = DllStructGetData($pNodeToDelete, "Left")
        _RBTransplant($pRoot, $pNodeToDelete, $pChild)
    Else
        Local $pSuccessor = _RBMinimum(DllStructGetData($pNodeToDelete, "Right"))
        $originalColor = DllStructGetData($pSuccessor, "Color")
        $pChild = DllStructGetData($pSuccessor, "Right")
        If DllStructGetData($pSuccessor, "Parent") = $pNodeToDelete Then
            DllStructSetData($pChild, "Parent", $pSuccessor)
        Else
            _RBTransplant($pRoot, $pSuccessor, $pChild)
            DllStructSetData($pSuccessor, "Right", DllStructGetData($pNodeToDelete, "Right"))
            DllStructSetData(DllStructGetData($pSuccessor, "Right"), "Parent", $pSuccessor)
        EndIf
        _RBTransplant($pRoot, $pNodeToDelete, $pSuccessor)
        DllStructSetData($pSuccessor, "Left", DllStructGetData($pNodeToDelete, "Left"))
        DllStructSetData(DllStructGetData($pSuccessor, "Left"), "Parent", $pSuccessor)
        DllStructSetData($pSuccessor, "Color", DllStructGetData($pNodeToDelete, "Color"))
    EndIf
    
    If $originalColor = $RB_BLACK Then _RBDeleteFixup($pRoot, $pChild)
    
    DllStructDelete($pNodeToDelete)
EndFunc

; Function to fix Red-Black tree violations after deletion
Func _RBDeleteFixup(ByRef $pRoot, $pNode)
    Local $pSibling
    While $pNode <> $pRoot And DllStructGetData($pNode, "Color") = $RB_BLACK
        If $pNode = DllStructGetData(DllStructGetData($pNode, "Parent"), "Left") Then
            $pSibling = DllStructGetData(DllStructGetData($pNode, "Parent"), "Right")
            If DllStructGetData($pSibling, "Color") = $RB_RED Then
                DllStructSetData($pSibling, "Color", $RB_BLACK)
                DllStructSetData(DllStructGetData($pNode, "Parent"), "Color", $RB_RED)
                _RBLeftRotate($pRoot, DllStructGetData($pNode, "Parent"))
                $pSibling = DllStructGetData(DllStructGetData($pNode, "Parent"), "Right")
            EndIf
            If DllStructGetData(DllStructGetData($pSibling, "Left"), "Color") = $RB_BLACK And DllStructGetData(DllStructGetData($pSibling, "Right"), "Color") = $RB_BLACK Then
                DllStructSetData($pSibling, "Color", $RB_RED)
                $pNode = DllStructGetData($pNode, "Parent")
            Else
                If DllStructGetData(DllStructGetData($pSibling, "Right"), "Color") = $RB_BLACK Then
                    DllStructSetData(DllStructGetData($pSibling, "Left"), "Color", $RB_BLACK)
                    DllStructSetData($pSibling, "Color", $RB_RED)
                    _RBRightRotate($pRoot, $pSibling)
                    $pSibling = DllStructGetData(DllStructGetData($pNode, "Parent"), "Right")
                EndIf
                DllStructSetData($pSibling, "Color", DllStructGetData(DllStructGetData($pNode, "Parent"), "Color"))
                DllStructSetData(DllStructGetData($pNode, "Parent"), "Color", $RB_BLACK)
                DllStructSetData(DllStructGetData($pSibling, "Right"), "Color", $RB_BLACK)
                _RBLeftRotate($pRoot, DllStructGetData($pNode, "Parent"))
                $pNode = $pRoot
            EndIf
        Else
            $pSibling = DllStructGetData(DllStructGetData($pNode, "Parent"), "Left")
            If DllStructGetData($pSibling, "Color") = $RB_RED Then
                DllStructSetData($pSibling, "Color", $RB_BLACK)
                DllStructSetData(DllStructGetData($pNode, "Parent"), "Color", $RB_RED)
                _RBRightRotate($pRoot, DllStructGetData($pNode, "Parent"))
                $pSibling = DllStructGetData(DllStructGetData($pNode, "Parent"), "Left")
            EndIf
            If DllStructGetData(DllStructGetData($pSibling, "Right"), "Color") = $RB_BLACK And DllStructGetData(DllStructGetData($pSibling, "Left"), "Color") = $RB_BLACK Then
                DllStructSetData($pSibling, "Color", $RB_RED)
                $pNode = DllStructGetData($pNode, "Parent")
            Else
                If DllStructGetData(DllStructGetData($pSibling, "Left"), "Color") = $RB_BLACK Then
                    DllStructSetData(DllStructGetData($pSibling, "Right"), "Color", $RB_BLACK)
                    DllStructSetData($pSibling, "Color", $RB_RED)
                    _RBLeftRotate($pRoot, $pSibling)
                    $pSibling = DllStructGetData(DllStructGetData($pNode, "Parent"), "Left")
                EndIf
                DllStructSetData($pSibling, "Color", DllStructGetData(DllStructGetData($pNode, "Parent"), "Color"))
                DllStructSetData(DllStructGetData($pNode, "Parent"), "Color", $RB_BLACK)
                DllStructSetData(DllStructGetData($pSibling, "Left"), "Color", $RB_BLACK)
                _RBRightRotate($pRoot, DllStructGetData($pNode, "Parent"))
                $pNode = $pRoot
            EndIf
        EndIf
    WEnd
    DllStructSetData($pNode, "Color", $RB_BLACK)
EndFunc

; Function to transplant a node in the Red-Black tree
Func _RBTransplant(ByRef $pRoot, $pNode1, $pNode2)
    If DllStructGetData($pNode1, "Parent") = 0 Then
        $pRoot = $pNode2
    ElseIf $pNode1 = DllStructGetData(DllStructGetData($pNode1, "Parent"), "Left") Then
        DllStructSetData(DllStructGetData($pNode1, "Parent"), "Left", $pNode2)
    Else
        DllStructSetData(DllStructGetData($pNode1, "Parent"), "Right", $pNode2)
    EndIf
    If $pNode2 <> 0 Then DllStructSetData($pNode2, "Parent", DllStructGetData($pNode1, "Parent"))
EndFunc

; Function to find the minimum element in the Red-Black tree
Func _RBMinimum($pNode)
    While DllStructGetData($pNode, "Left") <> 0
        $pNode = DllStructGetData($pNode, "Left")
    WEnd
    Return $pNode
EndFunc

; Function to find the maximum element in the Red-Black tree
Func _RBMaximum($pNode)
    While DllStructGetData($pNode, "Right") <> 0
        $pNode = DllStructGetData($pNode, "Right")
    WEnd
    Return $pNode
EndFunc

; Function to find the successor of a node in the Red-Black tree
Func _RBSuccessor($pNode)
    If DllStructGetData($pNode, "Right") <> 0 Then Return _RBMinimum(DllStructGetData($pNode, "Right"))
    Local $pParent = DllStructGetData($pNode, "Parent")
    While $pParent <> 0 And $pNode = DllStructGetData($pParent, "Right")
        $pNode = $pParent
        $pParent = DllStructGetData($pNode, "Parent")
    WEnd
    Return $pParent
EndFunc

; Function to find the predecessor of a node in the Red-Black tree
Func _RBPredecessor($pNode)
    If DllStructGetData($pNode, "Left") <> 0 Then Return _RBMaximum(DllStructGetData($pNode, "Left"))
    Local $pParent = DllStructGetData($pNode, "Parent")
    While $pParent <> 0 And $pNode = DllStructGetData($pParent, "Left")
        $pNode = $pParent
        $pParent = DllStructGetData($pNode, "Parent")
    WEnd
    Return $pParent
EndFunc

; Function to perform inorder traversal of the Red-Black tree
Func _RBInorderTraversal($pRoot)
    If $pRoot Then
        _RBInorderTraversal(DllStructGetData($pRoot, "Left"))
        ConsoleWrite(DllStructGetData($pRoot, "Data") & " ")
        _RBInorderTraversal(DllStructGetData($pRoot, "Right"))
    EndIf
EndFunc

; Function to perform preorder traversal of the Red-Black tree
Func _RBPreorderTraversal($pRoot)
    If $pRoot Then
        ConsoleWrite(DllStructGetData($pRoot, "Data") & " ")
        _RBPreorderTraversal(DllStructGetData($pRoot, "Left"))
        _RBPreorderTraversal(DllStructGetData($pRoot, "Right"))
    EndIf
EndFunc

; Function to perform postorder traversal of the Red-Black tree
Func _RBPostorderTraversal($pRoot)
    If $pRoot Then
        _RBPostorderTraversal(DllStructGetData($pRoot, "Left"))
        _RBPostorderTraversal(DllStructGetData($pRoot, "Right"))
        ConsoleWrite(DllStructGetData($pRoot, "Data") & " ")
    EndIf
EndFunc

Example 1: Insertion and Traversal 

#include "RedBlackTree.au3"

Local $pRoot = 0

; Insert elements into the Red-Black tree
_RBInsert($pRoot, 10)
_RBInsert($pRoot, 5)
_RBInsert($pRoot, 15)
_RBInsert($pRoot, 3)
_RBInsert($pRoot, 7)

; Perform inorder traversal
ConsoleWrite("Inorder Traversal: ")
_RBInorderTraversal($pRoot)
ConsoleWrite(@CRLF)

; Perform preorder traversal
ConsoleWrite("Preorder Traversal: ")
_RBPreorderTraversal($pRoot)
ConsoleWrite(@CRLF)

; Perform postorder traversal
ConsoleWrite("Postorder Traversal: ")
_RBPostorderTraversal($pRoot)
ConsoleWrite(@CRLF)

Example 2: Searching 

#include "RedBlackTree.au3"

Local $pRoot = 0

; Insert elements into the Red-Black tree
_RBInsert($pRoot, 10)
_RBInsert($pRoot, 5)
_RBInsert($pRoot, 15)
_RBInsert($pRoot, 3)
_RBInsert($pRoot, 7)

; Search for an element
Local $pNode = _RBSearch($pRoot, 7)
If $pNode Then
    ConsoleWrite("Element 7 found!" & @CRLF)
Else
    ConsoleWrite("Element 7 not found!" & @CRLF)
EndIf

Example 3: Deletion 

#include "RedBlackTree.au3"

Local $pRoot = 0

; Insert elements into the Red-Black tree
_RBInsert($pRoot, 10)
_RBInsert($pRoot, 5)
_RBInsert($pRoot, 15)
_RBInsert($pRoot, 3)
_RBInsert($pRoot, 7)

; Delete an element
_RBDelete($pRoot, 5)

; Perform inorder traversal after deletion
ConsoleWrite("Inorder Traversal after deletion: ")
_RBInorderTraversal($pRoot)
ConsoleWrite(@CRLF)

Example 4: Range Queries 

#include "RedBlackTree.au3"

Local $pRoot = 0

; Insert elements into the Red-Black tree
For $i = 1 To 10
    _RBInsert($pRoot, $i)
Next

; Perform a range query to find elements between 3 and 7
ConsoleWrite("Elements between 3 and 7: ")
Local $pNode = _RBSearch($pRoot, 3)
While $pNode And DllStructGetData($pNode, "Data") <= 7
    ConsoleWrite(DllStructGetData($pNode, "Data") & " ")
    $pNode = _RBSuccessor($pNode)
WEnd
ConsoleWrite(@CRLF)

Example 5: Interval Scheduling 

#include "RedBlackTree.au3"

; Define a structure for intervals
Global Const $tagInterval = "int Start;int End"

; Function to compare intervals based on their end points
Func _IntervalCompare($a, $b)
    If $a.End < $b.End Then Return -1
    If $a.End > $b.End Then Return 1
    Return 0
EndFunc

Local $pRoot = 0

; Define some intervals
Local $intervals[5] = [ _
    DllStructCreate($tagInterval, 1, 1), _
    DllStructCreate($tagInterval, 2, 4), _
    DllStructCreate($tagInterval, 5, 7), _
    DllStructCreate($tagInterval, 6, 9), _
    DllStructCreate($tagInterval, 8, 10) _
]

; Insert intervals into the Red-Black tree
For $i = 0 To UBound($intervals) - 1
    _RBInsertEx($pRoot, $intervals[$i], "_IntervalCompare")
Next

; Perform interval scheduling
ConsoleWrite("Maximum non-overlapping intervals: ")
Local $lastEnd = -1
Local $pNode = _RBMinimum($pRoot)
While $pNode
    Local $interval = DllStructCreate($tagInterval)
    DllStructSetData($interval, "Start", DllStructGetData($pNode, "Data.Start"))
    DllStructSetData($interval, "End", DllStructGetData($pNode, "Data.End"))
    If DllStructGetData($interval, "Start") > $lastEnd Then
        ConsoleWrite("[" & DllStructGetData($interval, "Start") & ", " & DllStructGetData($interval, "End") & "] ")
        $lastEnd = DllStructGetData($interval, "End")
    EndIf
    $pNode = _RBSuccessor($pNode)
WEnd
ConsoleWrite(@CRLF)

Example 6: Order Statistics 

#include "RedBlackTree.au3"

Local $pRoot = 0

; Insert elements into the Red-Black tree
For $i = 1 To 10
    _RBInsert($pRoot, $i)
Next

; Find the 3rd smallest element
ConsoleWrite("3rd smallest element: " & _RBSelect($pRoot, 3) & @CRLF)

; Find the 7th largest element
ConsoleWrite("7th largest element: " & _RBRank($pRoot, 7) & @CRLF)

 

Link to comment
Share on other sites
AspirinJunkie Universalist

AspirinJunkie

Posted
Posted
13 hours ago, LAteNightSpecial said:

I'm looking for some ideas on furthering the functionality.

The classic approach would of course be to implement this as you have done: With the low-level data types packaged as a dllstruct.

However, this approach comes with a few restrictions that we are not used to in AutoIt. In AutoIt, we rarely have to think about data types and can also nest them wildly.
In the current implementation, however, the user data is restricted to the integer data type.
However, if we now want to use Variant for this, you could modify the whole thing a little.

Suggestion no. 1:
Replace DllStructs with maps.
A node can also save the 4 elements in a map.
The only question would be what the pointers now point to.
You could also use a map as data storage for this.
As soon as a node is created, it is added to a node map via MapAppend which holds all the nodes.
The pointers to this node are now the integer index of this node as returned by MapAppend.
In this way, the tree can also be built completely without DllStructs and is completely flexible in terms of data types.

Suggestion no. 2:
The slimmed-down version of no. 1:
Here you could leave the tree and the nodes as they are.
Only the data field, as described above, does not yet contain the data itself but a pointer to it.
In other words: $Node.Data contains an integer index and the data itself is again held in a map which holds all the data elements.
As the map does not care about the data type, you now have complete freedom as to which data you pass and are not restricted to integers.

Link to comment
Share on other sites
LAteNightSpecial Seeker

LAteNightSpecial

Posted
  • Author
Posted

Thank you for taking the time to share your input, it is very much appreciated.

6 hours ago, AspirinJunkie said:

Suggestion no. 1:

Replace DllStructs with maps.
A node can also save the 4 elements in a map.
The only question would be what the pointers now point to.
You could also use a map as data storage for this.
As soon as a node is created, it is added to a node map via MapAppend which holds all the nodes.
The pointers to this node are now the integer index of this node as returned by MapAppend.
In this way, the tree can also be built completely without DllStructs and is completely flexible in terms of data types.

You bring up great points about the flexibility advantages of using maps in AutoIt, and your suggestions are excellent ways to modify the Red-Black tree implementation for handling Variant data types.

Node Representation: Instead of a DllStruct, a node would be a map: 

Local $node = MapCreate()
MapPut($node, "Color", $RB_RED)
MapPut($node, "Data", 15) ; Can store any data type now
MapPut($node, "Left", 0)  ; Index of the left child in the node map
MapPut($node, "Right", 0) ; Index of the right child
MapPut($node, "Parent", 0); Index of the parent node

Node Map: Maintain a global map to store all nodes: 

Global $gNodeMap = MapCreate()

Node Creation: 

Func _RBNodeCreate($data)
    Local $node = MapCreate()
    MapPut($node, "Color", $RB_RED)
    MapPut($node, "Data", $data)
    MapPut($node, "Left", 0) 
    MapPut($node, "Right", 0)
    MapPut($node, "Parent", 0)
    Return MapAppend($gNodeMap, $node) ; Return the index for reference
EndFunc

Accessing and Modifying Nodes Use the indices returned by MapAppend to reference nodes within $gNodeMap.

What about a hybrid approach?

Modify DllStruct: 

Global Const $tagRBNode = "int Data;ptr Left;ptr Right;int Color;ptr Parent"

Data Map: 

Global $gDataMap = MapCreate()

Insertion: 

Func _RBInsert(ByRef $pRoot, $data)
    Local $newDataIndex = MapAppend($gDataMap, $data)
    DllStructSetData($pNewNode, "Data", $newDataIndex)
EndFunc

Pros and Cons

  • Suggestion 1:

    • Pros: Maximum flexibility, completely removes structural type restrictions.
    • Cons: Might have slightly higher memory overhead due to maps.

  • Suggestion 2:

    • Pros: Less drastic change, maintains the core tree structure.
    • Cons: Still requires managing two separate storage mechanisms (struct and map).

It seems that if I were to go after maximum flexibility and handling diverse data types, suggestion 1 would be the best bet. Yet, if we want a less invasive change while still gaining flexibility while still maintaining the core tree structure as DllStructs, then suggestion 2 might be the best approach.

Code Modifications to Fully Replace DllStructs: 

Global Const $RB_RED = 0
Global Const $RB_BLACK = 1

Global $gNodeMap = MapCreate()

; Function to create a Red-Black tree node
Func _RBNodeCreate($data)
   Local $node = MapCreate()
   MapPut($node, "Color", $RB_RED)
   MapPut($node, "Data", $data)
   MapPut($node, "Left", 0) 
   MapPut($node, "Right", 0)
   MapPut($node, "Parent", 0) 
   Return MapAppend($gNodeMap, $node)
EndFunc

; Function to insert a new element into the Red-Black tree
Func _RBInsert(ByRef $pRoot, $data)
   ; ... (Similar to before, but node creation uses _RBNodeCreate)

   ; Fetch nodes using their indexes within $gNodeMap
   Local $currentNode = MapGet($gNodeMap, $pCurrent)  
   Local $parentNode = MapGet($gNodeMap, DllStructGetData($pNewNode, "Parent")) 
   
   ; Access and update node properties using Map functions: 
   If $data < MapGet($currentNode, "Data") Then
       MapPut($parentNode, "Left", DllStructGetData($pNewNode, "Index"))
   EndIf          
EndFunc

; Other functions: _RBInsertFixup, _RBLeftRotate, _RBrightRotate, _RBSearch,
; _RBDelete, and helper functions would all need similar modifications to
; access and update properties using MapGet and MapPut
 

Let's analyze the performance differences between the classic DllStruct-based Red-Black tree implementation and the map-based approach. Here's a breakdown of the factors to consider:

Performance Factors

  • Memory Overhead:

    • Maps in AutoIt tend to have a higher memory footprint than DllStructs, as they store additional metadata for key-value management. This could lead to slightly higher memory usage with the map-based Red-Black tree.

  • Property Access:

    • Accessing properties within a DllStruct (DllStructGetData) is likely to be slightly faster than the equivalent lookup in a map (MapGet). DllStructs benefit from being a lower-level, contiguous memory structure.

  • Lookup/Search Efficiency:

    • The core search performance of the Red-Black Tree itself shouldn't be significantly affected between the two methods. The self-balancing properties ensure O(log n) search time complexity in both cases.

  • Flexibility:

    • The map-based approach has inherently more overhead incurred if we need to adapt it to support a specific, fixed data structure. With DllStructs, we can customize the structure rigidly for the given data type.

In general, the performance differences between the two approaches are likely to be relatively minor in most practical AutoIt use cases. Here's a guideline:

  • Prioritize Flexibility: If the primary need is to handle a wide variety of data types within the Red-Black tree without restrictions, the map-based approach offers a significant advantage. The slight performance trade-off might be acceptable.

  • Prioritize Raw Speed: If we have a fixed data type, the Red-Black tree needs to be as fast as possible, and flexibility is not a major concern, the classic DllStruct approach might give us a small edge in terms of execution time and memory usage.

Quantifying the Differences

To get a precise idea of the performance differences in this specific context, I could set up a benchmark test.

  1. Implement all versions of the Red-Black tree (DllStruct, Map-based, and Hybrid).
  2. Create large datasets with representative data.
  3. Run timed trials for:
    • Insertion (for multiple data points)
    • Searching (for multiple data points)
  4. Compare execution times and potential memory usage differences between the two implementations.

Again, thank you for taking the time out of your day. What are your thoughts on the Hybrid approach?

Link to comment
Share on other sites
AspirinJunkie Universalist

AspirinJunkie

Posted
Posted
1 hour ago, LAteNightSpecial said:

What are your thoughts on the Hybrid approach?

You mean my suggestion no. 2, right?
So that the nodes remain DllStruct-based and only the data is outsourced to a map?

For the question of functionality, it doesn't matter for the time being. It should be possible to implement the tree with the same functionality with both the hybrid variant and the pure map variant.

For performance reasons, I see 2 aspects here:
Keeping the nodes as DllStruct should be slower at first, because accessing a node requires that you create a new DLLStruct over a certain pointer.
With Map, on the other hand, access is via the index.
The latter is initially faster than the DLLStruct method.
But: The greater the number of nodes, the more the picture changes.
Access to individual elements of the node map becomes slower and slower.
This means that it basically depends on the number of nodes to see which variant you prefer for performance reasons.

The reason for this behavior of maps is (as far as I can deduce from measured values) that AutoIt maps have a fixed size without any resizing. If the map has a fixed size of 256 elements, for example, then we inevitably have more and more hash collisions the more elements are stored in it. In order to access an element, the subarray at the hash index must then be traversed linearly each time to find the element - this takes time.

1 hour ago, LAteNightSpecial said: 
MapPut($node, "Color", $RB_RED)

I have not yet fully understood the purpose of the _MapPut function.

A $node.Color = $RB_RED should be more performant and meaningful.

To tease out a bit of performance, you could use the _RBNodeCreate() could be rewritten like this: 

Func _RBNodeCreate($data)
    Local Static $node[]
    $node.Color = $RB_RED
    $node.Data = $data
    Return MapAppend($gNodeMap, $node) ; Return the index for reference
EndFunc

The static only creates a new map once, which is not a problem, as a copy of this is passed to MapAppend. And the attributes for Left, Right and Parent are not yet explicitly required here, as these are only explicitly described when they are inserted into the tree.
To be honest, this is not really measurable.

Link to comment
Share on other sites
LAteNightSpecial Seeker

LAteNightSpecial

Posted
  • Author
Posted (edited)

Taking into consideration AspirinJunkie's suggestions along with some of my own research. Here's what we have managed to come up with.

Strengths

  • Red-Black Tree Implementation:

    • Implements a Red-Black tree data structure in AutoIt.
    • Handles insertion, deletion, and searching operations in the Red-Black tree.

  • Error Handling and Robustness:

    • Checks for successful memory allocation in node creation.
    • Ensures validity of handles/pointers representing nodes during insertion and deletion.
    • Implements safe deletion to prevent memory leaks.

  • Sophistication:

    • Generics-Like Behavior:
      • Supports a wider range of data types using variants, enabling flexibility in data handling.
    • Iterator Functions:
      • Provides standardized traversal methods: inorder, preorder, postorder.
      • Encapsulates traversal logic within the tree definition, enhancing convenience.

  • Balancing Optimizations:

    • Implements efficient rotation and fixup operations for balancing.
    • Ensures optimal balancing of the Red-Black tree during insertion and deletion.

  • Advanced Concepts:

    • Template-Like Behavior:
      • Utilizes AutoIt techniques to handle specific data types without extensive modification.
    • Visualization (Not Fully Yet realized):
      • Provides functions for visualizing the structure of the tree, aiding in debugging and understanding behavior.

  • Functionality:

    • Supports insertion of elements into the Red-Black tree.
    • Allows deletion of elements from the Red-Black tree.
    • Facilitates searching for elements within the Red-Black tree.
    • Enables traversal of the Red-Black tree using various methods.
    • Provides efficient balancing to maintain the Red-Black tree properties.
    • Flexibility: You can insert data of any type into the tree. The _RBNodeCreate function smartly decides how to store the node based on whether the root is a pointer or an object.
    • Efficiency: The core operations use helper functions like _RBGetData, _RBGetChild, etc., which streamline the code and allow for potential performance gains with DllStructs.
    • Consistency: The script now has a consistent way of handling node properties.

Possible Further Enhancements: Iterators, Type Safety (Optional), Visualization (Creating a text-based tree visualization)

Utilizing DllStructs with optimization implementations & enhancements: 

Global Const $RB_RED = 0
Global Const $RB_BLACK = 1

Global Const $tagRBNode = "ptr Parent;ptr Left;ptr Right;var Data;int Color"

Func _RBNodeCreate($vData)
    Local $pNode = DllStructCreate($tagRBNode)
    If @error Then Return SetError(@error, @extended, "Error creating DllStruct")
    DllStructSetData($pNode, "Data", $vData)
    Return $pNode
EndFunc

Func _RBInsert(ByRef $pRoot, $vData)
    If Not IsPtr($pRoot) Then Return SetError(2, 0, "Invalid root pointer")
    
    Local $pNewNode = _RBNodeCreate($vData)
    If @error Then Return SetError(@error, @extended, "Error creating node")
    
    Local $pParent = 0
    Local $pCurrent = $pRoot
    
    While $pCurrent
        $pParent = $pCurrent
        If $vData < DllStructGetData($pCurrent, "Data") Then
            $pCurrent = DllStructGetData($pCurrent, "Left")
        Else
            $pCurrent = DllStructGetData($pCurrent, "Right")
        EndIf
    WEnd
    
    DllStructSetData($pNewNode, "Parent", $pParent)
    
    If $vData < DllStructGetData($pParent, "Data") Then
        DllStructSetData($pParent, "Left", $pNewNode)
    Else
        DllStructSetData($pParent, "Right", $pNewNode)
    EndIf
    
    _RBInsertFixup($pRoot, $pNewNode)
EndFunc

Func _RBDelete(ByRef $pRoot, $vData)
    Local $pNodeToDelete = _RBSearch($pRoot, $vData)
    If Not $pNodeToDelete Then Return
    
    Local $pParent = DllStructGetData($pNodeToDelete, "Parent")
    Local $pChild
    Local $originalColor = DllStructGetData($pNodeToDelete, "Color")
    
    If DllStructGetData($pNodeToDelete, "Left") = 0 Then
        $pChild = DllStructGetData($pNodeToDelete, "Right")
        _RBTransplant($pRoot, $pNodeToDelete, $pChild)
    ElseIf DllStructGetData($pNodeToDelete, "Right") = 0 Then
        $pChild = DllStructGetData($pNodeToDelete, "Left")
        _RBTransplant($pRoot, $pNodeToDelete, $pChild)
    Else
        Local $pSuccessor = _RBMinimum(DllStructGetData($pNodeToDelete, "Right"))
        $originalColor = DllStructGetData($pSuccessor, "Color")
        $pChild = DllStructGetData($pSuccessor, "Right")
        If DllStructGetData($pSuccessor, "Parent") = $pNodeToDelete Then
            DllStructSetData($pChild, "Parent", $pSuccessor)
        Else
            _RBTransplant($pRoot, $pSuccessor, $pChild)
            DllStructSetData($pSuccessor, "Right", DllStructGetData($pNodeToDelete, "Right"))
            DllStructSetData(DllStructGetData($pSuccessor, "Right"), "Parent", $pSuccessor)
        EndIf
        _RBTransplant($pRoot, $pNodeToDelete, $pSuccessor)
        DllStructSetData($pSuccessor, "Left", DllStructGetData($pNodeToDelete, "Left"))
        DllStructSetData(DllStructGetData($pSuccessor, "Left"), "Parent", $pSuccessor)
        DllStructSetData($pSuccessor, "Color", DllStructGetData($pNodeToDelete, "Color"))
    EndIf
    
    If $originalColor = $RB_BLACK Then _RBDeleteFixup($pRoot, $pChild)
    
    DllStructDelete($pNodeToDelete)
EndFunc

Func _RBInsertFixup(ByRef $pRoot, $pNode)
    Local $pParent = 0
    Local $pGrandparent = 0
    Local $pUncle = 0
    
    While DllStructGetData($pNode, "Parent") And DllStructGetData(DllStructGetData($pNode, "Parent"), "Color") = $RB_RED
        $pParent = DllStructGetData($pNode, "Parent")
        $pGrandparent = DllStructGetData($pParent, "Parent")
        
        If $pParent = DllStructGetData($pGrandparent, "Left") Then
            $pUncle = DllStructGetData($pGrandparent, "Right")
            If $pUncle And DllStructGetData($pUncle, "Color") = $RB_RED Then
                DllStructSetData($pParent, "Color", $RB_BLACK)
                DllStructSetData($pUncle, "Color", $RB_BLACK)
                DllStructSetData($pGrandparent, "Color", $RB_RED)
                $pNode = $pGrandparent
            Else
                If $pNode = DllStructGetData($pParent, "Right") Then
                    $pNode = $pParent
                    _RBLeftRotate($pRoot, $pNode)
                EndIf
                DllStructSetData($pParent, "Color", $RB_BLACK)
                DllStructSetData($pGrandparent, "Color", $RB_RED)
                _RBRightRotate($pRoot, $pGrandparent)
            EndIf
        Else
            $pUncle = DllStructGetData($pGrandparent, "Left")
            If $pUncle And DllStructGetData($pUncle, "Color") = $RB_RED Then
                DllStructSetData($pParent, "Color", $RB_BLACK)
                DllStructSetData($pUncle, "Color", $RB_BLACK)
                DllStructSetData($pGrandparent, "Color", $RB_RED)
                $pNode = $pGrandparent
            Else
                If $pNode = DllStructGetData($pParent, "Left") Then
                    $pNode = $pParent
                    _RBRightRotate($pRoot, $pNode)
                EndIf
                DllStructSetData($pParent, "Color", $RB_BLACK)
                DllStructSetData($pGrandparent, "Color", $RB_RED)
                _RBLeftRotate($pRoot, $pGrandparent)
            EndIf
        EndIf
    WEnd
    
    DllStructSetData($pRoot, "Color", $RB_BLACK)
EndFunc

Func _RBDeleteFixup(ByRef $pRoot, $pNode)
    Local $pSibling
    While $pNode <> $pRoot And DllStructGetData($pNode, "Color") = $RB_BLACK
        If $pNode = DllStructGetData(DllStructGetData($pNode, "Parent"), "Left") Then
            $pSibling = DllStructGetData(DllStructGetData($pNode, "Parent"), "Right")
            If DllStructGetData($pSibling, "Color") = $RB_RED Then
                DllStructSetData($pSibling, "Color", $RB_BLACK)
                DllStructSetData(DllStructGetData($pNode, "Parent"), "Color", $RB_RED)
                _RBLeftRotate($pRoot, DllStructGetData($pNode, "Parent"))
                $pSibling = DllStructGetData(DllStructGetData($pNode, "Parent"), "Right")
            EndIf
            If DllStructGetData(DllStructGetData($pSibling, "Left"), "Color") = $RB_BLACK And DllStructGetData(DllStructGetData($pSibling, "Right"), "Color") = $RB_BLACK Then
                DllStructSetData($pSibling, "Color", $RB_RED)
                $pNode = DllStructGetData($pNode, "Parent")
            Else
                If DllStructGetData(DllStructGetData($pSibling, "Right"), "Color") = $RB_BLACK Then
                    DllStructSetData(DllStructGetData($pSibling, "Left"), "Color", $RB_BLACK)
                    DllStructSetData($pSibling, "Color", $RB_RED)
                    _RBRightRotate($pRoot, $pSibling)
                    $pSibling = DllStructGetData(DllStructGetData($pNode, "Parent"), "Right")
                EndIf
                DllStructSetData($pSibling, "Color", DllStructGetData(DllStructGetData($pNode, "Parent"), "Color"))
                DllStructSetData(DllStructGetData($pNode, "Parent"), "Color", $RB_BLACK)
                DllStructSetData(DllStructGetData($pSibling, "Right"), "Color", $RB_BLACK)
                _RBLeftRotate($pRoot, DllStructGetData($pNode, "Parent"))
                $pNode = $pRoot
            EndIf
        Else
            $pSibling = DllStructGetData(DllStructGetData($pNode, "Parent"), "Left")
            If DllStructGetData($pSibling, "Color") = $RB_RED Then
                DllStructSetData($pSibling, "Color", $RB_BLACK)
                DllStructSetData(DllStructGetData($pNode, "Parent"), "Color", $RB_RED)
                _RBRightRotate($pRoot, DllStructGetData($pNode, "Parent"))
                $pSibling = DllStructGetData(DllStructGetData($pNode, "Parent"), "Left")
            EndIf
            If DllStructGetData(DllStructGetData($pSibling, "Right"), "Color") = $RB_BLACK And DllStructGetData(DllStructGetData($pSibling, "Left"), "Color") = $RB_BLACK Then
                DllStructSetData($pSibling, "Color", $RB_RED)
                $pNode = DllStructGetData($pNode, "Parent")
            Else
                If DllStructGetData(DllStructGetData($pSibling, "Left"), "Color") = $RB_BLACK Then
                    DllStructSetData(DllStructGetData($pSibling, "Right"), "Color", $RB_BLACK)
                    DllStructSetData($pSibling, "Color", $RB_RED)
                    _RBLeftRotate($pRoot, $pSibling)
                    $pSibling = DllStructGetData(DllStructGetData($pNode, "Parent"), "Left")
                EndIf
                DllStructSetData($pSibling, "Color", DllStructGetData(DllStructGetData($pNode, "Parent"), "Color"))
                DllStructSetData(DllStructGetData($pNode, "Parent"), "Color", $RB_BLACK)
                DllStructSetData(DllStructGetData($pSibling, "Left"), "Color", $RB_BLACK)
                _RBRightRotate($pRoot, DllStructGetData($pNode, "Parent"))
                $pNode = $pRoot
            EndIf
        EndIf
    WEnd
    DllStructSetData($pNode, "Color", $RB_BLACK)
EndFunc

Func _RBLeftRotate(ByRef $pRoot, $pNode)
    Local $pRightChild = DllStructGetData($pNode, "Right")
    DllStructSetData($pNode, "Right", DllStructGetData($pRightChild, "Left"))
    If DllStructGetData(DllStructGetData($pRightChild, "Left"), "Left") Then
        DllStructSetData(DllStructGetData($pRightChild, "Left"), "Parent", $pNode)
    EndIf
    DllStructSetData($pRightChild, "Parent", DllStructGetData($pNode, "Parent"))
    If Not DllStructGetData($pNode, "Parent") Then
        $pRoot = $pRightChild
    ElseIf $pNode = DllStructGetData(DllStructGetData($pNode, "Parent"), "Left") Then
        DllStructSetData(DllStructGetData($pNode, "Parent"), "Left", $pRightChild)
    Else
        DllStructSetData(DllStructGetData($pNode, "Parent"), "Right", $pRightChild)
    EndIf
    DllStructSetData($pRightChild, "Left", $pNode)
    DllStructSetData($pNode, "Parent", $pRightChild)
EndFunc

Func _RBRightRotate(ByRef $pRoot, $pNode)
    Local $pLeftChild = DllStructGetData($pNode, "Left")
    DllStructSetData($pNode, "Left", DllStructGetData($pLeftChild, "Right"))
    If DllStructGetData(DllStructGetData($pLeftChild, "Right"), "Right") Then
        DllStructSetData(DllStructGetData($pLeftChild, "Right"), "Parent", $pNode)
    EndIf
    DllStructSetData($pLeftChild, "Parent", DllStructGetData($pNode, "Parent"))
    If Not DllStructGetData($pNode, "Parent") Then
        $pRoot = $pLeftChild
    ElseIf $pNode = DllStructGetData(DllStructGetData($pNode, "Parent"), "Right") Then
        DllStructSetData(DllStructGetData($pNode, "Parent"), "Right", $pLeftChild)
    Else
        DllStructSetData(DllStructGetData($pNode, "Parent"), "Left", $pLeftChild)
    EndIf
    DllStructSetData($pLeftChild, "Right", $pNode)
    DllStructSetData($pNode, "Parent", $pLeftChild)
EndFunc

Func _RBTransplant(ByRef $pRoot, $pNode1, $pNode2)
    If DllStructGetData($pNode1, "Parent") = 0 Then
        $pRoot = $pNode2
    ElseIf $pNode1 = DllStructGetData(DllStructGetData($pNode1, "Parent"), "Left") Then
        DllStructSetData(DllStructGetData($pNode1, "Parent"), "Left", $pNode2)
    Else
        DllStructSetData(DllStructGetData($pNode1, "Parent"), "Right", $pNode2)
    EndIf
    If $pNode2 Then DllStructSetData($pNode2, "Parent", DllStructGetData($pNode1, "Parent"))
EndFunc

Func _RBMinimum($pNode)
    While DllStructGetData($pNode, "Left")
        $pNode = DllStructGetData($pNode, "Left")
    WEnd
    Return $pNode
EndFunc

Func _RBSearch($pNode, $vData)
    While $pNode And $vData <> DllStructGetData($pNode, "Data")
        If $vData < DllStructGetData($pNode, "Data") Then
            $pNode = DllStructGetData($pNode, "Left")
        Else
            $pNode = DllStructGetData($pNode, "Right")
        EndIf
    WEnd
    Return $pNode
EndFunc

; Variant Behavior: While var Data provides flexibility, be mindful when retrieving and using the data. AutoIt's Variants require extra care compared to strongly-typed variables.
; Error Handling Extension: Consider extending error handling to other functions like _RBDelete, _RBInsertFixup, etc. to catch potential issues with invalid pointers or unexpected situations.
; Sophisticated Error Handling: Instead of just returning basic error codes, implement a way to pass more informative error messages, potentially using custom UDFs.
; Advanced Data Handling: If use cases demand seamless work with diverse data types within the tree, investigate how to introduce type checking or templating techniques to streamline working with node data.
; Tree Visualization: Create a function to print out a text-based representation of the tree's structure. This would be invaluable for debugging and understanding its behavior.

Utilizing Mapping with optimization implementations & enhancements: 

Global Const $RB_RED = 0
Global Const $RB_BLACK = 1

Global Const $tagRBNode = "ptr Parent;ptr Left;ptr Right;var Data;int Color"

Func _RBNodeCreate($vData)
    Local $tNode = ObjCreate($tagRBNode)
    If @error Then Return SetError(@error, @extended, 0)
    $tNode.Data = $vData
    Return $tNode
EndFunc

Func _RBInsert(ByRef $pRoot, $vData)
    If Not IsObj($pRoot) Then Return SetError(2, 0, 0) ; Error: Invalid root pointer
    
    Local $pNewNode = _RBNodeCreate($vData)
    If @error Then Return SetError(@error, @extended, 0)
    
    Local $pParent = 0
    Local $pCurrent = $pRoot
    
    While $pCurrent
        $pParent = $pCurrent
        If $vData < $pCurrent.Data Then
            $pCurrent = $pCurrent.Left
        Else
            $pCurrent = $pCurrent.Right
        EndIf
    WEnd
    
    $pNewNode.Parent = $pParent
    
    If $vData < $pParent.Data Then
        $pParent.Left = $pNewNode
    Else
        $pParent.Right = $pNewNode
    EndIf
    
    _RBInsertFixup($pRoot, $pNewNode)
EndFunc

Func _RBDelete(ByRef $pRoot, $vData)
    Local $pNodeToDelete = _RBSearch($pRoot, $vData)
    If Not IsObj($pNodeToDelete) Then Return
    
    Local $pParent = $pNodeToDelete.Parent
    Local $pChild
    Local $originalColor = $pNodeToDelete.Color
    
    If Not $pNodeToDelete.Left Then
        $pChild = $pNodeToDelete.Right
        _RBTransplant($pRoot, $pNodeToDelete, $pChild)
    ElseIf Not $pNodeToDelete.Right Then
        $pChild = $pNodeToDelete.Left
        _RBTransplant($pRoot, $pNodeToDelete, $pChild)
    Else
        Local $pSuccessor = _RBMinimum($pNodeToDelete.Right)
        $originalColor = $pSuccessor.Color
        $pChild = $pSuccessor.Right
        If $pSuccessor.Parent = $pNodeToDelete Then
            $pChild.Parent = $pSuccessor
        Else
            _RBTransplant($pRoot, $pSuccessor, $pChild)
            $pSuccessor.Right = $pNodeToDelete.Right
            $pSuccessor.Right.Parent = $pSuccessor
        EndIf
        _RBTransplant($pRoot, $pNodeToDelete, $pSuccessor)
        $pSuccessor.Left = $pNodeToDelete.Left
        $pSuccessor.Left.Parent = $pSuccessor
        $pSuccessor.Color = $pNodeToDelete.Color
    EndIf
    
    If $originalColor = $RB_BLACK Then _RBDeleteFixup($pRoot, $pChild)
    
    ObjRelease($pNodeToDelete)
EndFunc

Func _RBInsertFixup(ByRef $pRoot, $pNode)
    Local $pParent = 0
    Local $pGrandparent = 0
    Local $pUncle = 0
    
    While $pNode.Parent And $pNode.Parent.Color = $RB_RED
        $pParent = $pNode.Parent
        $pGrandparent = $pParent.Parent
        
        If $pParent = $pGrandparent.Left Then
            $pUncle = $pGrandparent.Right
            If $pUncle And $pUncle.Color = $RB_RED Then
                $pParent.Color = $RB_BLACK
                $pUncle.Color = $RB_BLACK
                $pGrandparent.Color = $RB_RED
                $pNode = $pGrandparent
            Else
                If $pNode = $pParent.Right Then
                    $pNode = $pParent
                    _RBLeftRotate($pRoot, $pNode)
                EndIf
                $pParent.Color = $RB_BLACK
                $pGrandparent.Color = $RB_RED
                _RBRightRotate($pRoot, $pGrandparent)
            EndIf
        Else
            $pUncle = $pGrandparent.Left
            If $pUncle And $pUncle.Color = $RB_RED Then
                $pParent.Color = $RB_BLACK
                $pUncle.Color = $RB_BLACK
                $pGrandparent.Color = $RB_RED
                $pNode = $pGrandparent
            Else
                If $pNode = $pParent.Left Then
                    $pNode = $pParent
                    _RBRightRotate($pRoot, $pNode)
                EndIf
                $pParent.Color = $RB_BLACK
                $pGrandparent.Color = $RB_RED
                _RBLeftRotate($pRoot, $pGrandparent)
            EndIf
        EndIf
    WEnd
    
    $pRoot.Color = $RB_BLACK
EndFunc

Func _RBDeleteFixup(ByRef $pRoot, $pNode)
    Local $pSibling
    While $pNode <> $pRoot And $pNode.Color = $RB_BLACK
        If $pNode = $pNode.Parent.Left Then
            $pSibling = $pNode.Parent.Right
            If $pSibling.Color = $RB_RED Then
                $pSibling.Color = $RB_BLACK
                $pNode.Parent.Color = $RB_RED
                _RBLeftRotate($pRoot, $pNode.Parent)
                $pSibling = $pNode.Parent.Right
            EndIf
            If $pSibling.Left.Color = $RB_BLACK And $pSibling.Right.Color = $RB_BLACK Then
                $pSibling.Color = $RB_RED
                $pNode = $pNode.Parent
            Else
                If $pSibling.Right.Color = $RB_BLACK Then
                    $pSibling.Left.Color = $RB_BLACK
                    $pSibling.Color = $RB_RED
                    _RBRightRotate($pRoot, $pSibling)
                    $pSibling = $pNode.Parent.Right
                EndIf
                $pSibling.Color = $pNode.Parent.Color
                $pNode.Parent.Color = $RB_BLACK
                $pSibling.Right.Color = $RB_BLACK
                _RBLeftRotate($pRoot, $pNode.Parent)
                $pNode = $pRoot
            EndIf
        Else
            $pSibling = $pNode.Parent.Left
            If $pSibling.Color = $RB_RED Then
                $pSibling.Color = $RB_BLACK
                $pNode.Parent.Color = $RB_RED
                _RBRightRotate($pRoot, $pNode.Parent)
                $pSibling = $pNode.Parent.Left
            EndIf
            If $pSibling.Right.Color = $RB_BLACK And $pSibling.Left.Color = $RB_BLACK Then
                $pSibling.Color = $RB_RED
                $pNode = $pNode.Parent
            Else
                If $pSibling.Left.Color = $RB_BLACK Then
                    $pSibling.Right.Color = $RB_BLACK
                    $pSibling.Color = $RB_RED
                    _RBLeftRotate($pRoot, $pSibling)
                    $pSibling = $pNode.Parent.Left
                EndIf
                $pSibling.Color = $pNode.Parent.Color
                $pNode.Parent.Color = $RB_BLACK
                $pSibling.Left.Color = $RB_BLACK
                _RBRightRotate($pRoot, $pNode.Parent)
                $pNode = $pRoot
            EndIf
        EndIf
    WEnd
    $pNode.Color = $RB_BLACK
EndFunc

Func _RBLeftRotate(ByRef $pRoot, $pNode)
    Local $pRightChild = $pNode.Right
    $pNode.Right = $pRightChild.Left
    If $pRightChild.Left Then $pRightChild.Left.Parent = $pNode
    $pRightChild.Parent = $pNode.Parent
    If Not $pNode.Parent Then
        $pRoot = $pRightChild
    ElseIf $pNode = $pNode.Parent.Left Then
        $pNode.Parent.Left = $pRightChild
    Else
        $pNode.Parent.Right = $pRightChild
    EndIf
    $pRightChild.Left = $pNode
    $pNode.Parent = $pRightChild
EndFunc

Func _RBRightRotate(ByRef $pRoot, $pNode)
    Local $pLeftChild = $pNode.Left
    $pNode.Left = $pLeftChild.Right
    If $pLeftChild.Right Then $pLeftChild.Right.Parent = $pNode
    $pLeftChild.Parent = $pNode.Parent
    If Not $pNode.Parent Then
        $pRoot = $pLeftChild
    ElseIf $pNode = $pNode.Parent.Right Then
        $pNode.Parent.Right = $pLeftChild
    Else
        $pNode.Parent.Left = $pLeftChild
    EndIf
    $pLeftChild.Right = $pNode
    $pNode.Parent = $pLeftChild
EndFunc

Func _RBTransplant(ByRef $pRoot, $pNode1, $pNode2)
    If Not $pNode1.Parent Then
        $pRoot = $pNode2
    ElseIf $pNode1 = $pNode1.Parent.Left Then
        $pNode1.Parent.Left = $pNode2
    Else
        $pNode1.Parent.Right = $pNode2
    EndIf
    If $pNode2 Then $pNode2.Parent = $pNode1.Parent
EndFunc

Func _RBMinimum($pNode)
    While $pNode.Left
        $pNode = $pNode.Left
    WEnd
    Return $pNode
EndFunc

Func _RBSearch($pNode, $vData)
    While $pNode And $vData <> $pNode.Data
        If $vData < $pNode.Data Then
            $pNode = $pNode.Left
        Else
            $pNode = $pNode.Right
        EndIf
    WEnd
    Return $pNode
EndFunc

Utilizing a Hybrid approach with optimization implementations & enhancements: 

Global Const $RB_RED = 0
Global Const $RB_BLACK = 1

Global Const $tagRBNode = "ptr Parent;ptr Left;ptr Right;var Data;int Color"

Func _RBNodeCreate($vData)
    Local $tNode = ObjCreate($tagRBNode)
    If @error Then Return SetError(@error, @extended, 0)
    $tNode.Data = $vData
    Return $tNode
EndFunc

Func _RBInsert(ByRef $pRoot, $vData)
    If Not IsObj($pRoot) Then Return SetError(2, 0, 0) ; Error: Invalid root pointer
    
    Local $pNewNode = _RBNodeCreate($vData)
    If @error Then Return SetError(@error, @extended, 0)
    
    Local $pParent = 0
    Local $pCurrent = $pRoot
    
    While $pCurrent
        $pParent = $pCurrent
        If $vData < $pCurrent.Data Then
            $pCurrent = $pCurrent.Left
        Else
            $pCurrent = $pCurrent.Right
        EndIf
    WEnd
    
    $pNewNode.Parent = $pParent
    
    If $vData < $pParent.Data Then
        $pParent.Left = $pNewNode
    Else
        $pParent.Right = $pNewNode
    EndIf
    
    _RBInsertFixup($pRoot, $pNewNode)
EndFunc

Func _RBDelete(ByRef $pRoot, $vData)
    Local $pNodeToDelete = _RBSearch($pRoot, $vData)
    If Not IsObj($pNodeToDelete) Then Return
    
    Local $pParent = $pNodeToDelete.Parent
    Local $pChild
    Local $originalColor = $pNodeToDelete.Color
    
    If Not $pNodeToDelete.Left Then
        $pChild = $pNodeToDelete.Right
        _RBTransplant($pRoot, $pNodeToDelete, $pChild)
    ElseIf Not $pNodeToDelete.Right Then
        $pChild = $pNodeToDelete.Left
        _RBTransplant($pRoot, $pNodeToDelete, $pChild)
    Else
        Local $pSuccessor = _RBMinimum($pNodeToDelete.Right)
        $originalColor = $pSuccessor.Color
        $pChild = $pSuccessor.Right
        If $pSuccessor.Parent = $pNodeToDelete Then
            $pChild.Parent = $pSuccessor
        Else
            _RBTransplant($pRoot, $pSuccessor, $pChild)
            $pSuccessor.Right = $pNodeToDelete.Right
            $pSuccessor.Right.Parent = $pSuccessor
        EndIf
        _RBTransplant($pRoot, $pNodeToDelete, $pSuccessor)
        $pSuccessor.Left = $pNodeToDelete.Left
        $pSuccessor.Left.Parent = $pSuccessor
        $pSuccessor.Color = $pNodeToDelete.Color
    EndIf
    
    If $originalColor = $RB_BLACK Then _RBDeleteFixup($pRoot, $pChild)
    
    ObjRelease($pNodeToDelete)
EndFunc

Func _RBInsertFixup(ByRef $pRoot, $pNode)
    Local $pParent = 0
    Local $pGrandparent = 0
    Local $pUncle = 0
    
    While $pNode.Parent And $pNode.Parent.Color = $RB_RED
        $pParent = $pNode.Parent
        $pGrandparent = $pParent.Parent
        
        If $pParent = $pGrandparent.Left Then
            $pUncle = $pGrandparent.Right
            If $pUncle And $pUncle.Color = $RB_RED Then
                $pParent.Color = $RB_BLACK
                $pUncle.Color = $RB_BLACK
                $pGrandparent.Color = $RB_RED
                $pNode = $pGrandparent
            Else
                If $pNode = $pParent.Right Then
                    $pNode = $pParent
                    _RBLeftRotate($pRoot, $pNode)
                EndIf
                $pParent.Color = $RB_BLACK
                $pGrandparent.Color = $RB_RED
                _RBRightRotate($pRoot, $pGrandparent)
            EndIf
        Else
            $pUncle = $pGrandparent.Left
            If $pUncle And $pUncle.Color = $RB_RED Then
                $pParent.Color = $RB_BLACK
                $pUncle.Color = $RB_BLACK
                $pGrandparent.Color = $RB_RED
                $pNode = $pGrandparent
            Else
                If $pNode = $pParent.Left Then
                    $pNode = $pParent
                    _RBRightRotate($pRoot, $pNode)
                EndIf
                $pParent.Color = $RB_BLACK
                $pGrandparent.Color = $RB_RED
                _RBLeftRotate($pRoot, $pGrandparent)
            EndIf
        EndIf
    WEnd
    
    $pRoot.Color = $RB_BLACK
EndFunc

Func _RBDeleteFixup(ByRef $pRoot, $pNode)
    Local $pSibling
    While $pNode <> $pRoot And $pNode.Color = $RB_BLACK
        If $pNode = $pNode.Parent.Left Then
            $pSibling = $pNode.Parent.Right
            If $pSibling.Color = $RB_RED Then
                $pSibling.Color = $RB_BLACK
                $pNode.Parent.Color = $RB_RED
                _RBLeftRotate($pRoot, $pNode.Parent)
                $pSibling = $pNode.Parent.Right
            EndIf
            If $pSibling.Left.Color = $RB_BLACK And $pSibling.Right.Color = $RB_BLACK Then
                $pSibling.Color = $RB_RED
                $pNode = $pNode.Parent
            Else
                If $pSibling.Right.Color = $RB_BLACK Then
                    $pSibling.Left.Color = $RB_BLACK
                    $pSibling.Color = $RB_RED
                    _RBRightRotate($pRoot, $pSibling)
                    $pSibling = $pNode.Parent.Right
                EndIf
                $pSibling.Color = $pNode.Parent.Color
                $pNode.Parent.Color = $RB_BLACK
                $pSibling.Right.Color = $RB_BLACK
                _RBLeftRotate($pRoot, $pNode.Parent)
                $pNode = $pRoot
            EndIf
        Else
            $pSibling = $pNode.Parent.Left
            If $pSibling.Color = $RB_RED Then
                $pSibling.Color = $RB_BLACK
                $pNode.Parent.Color = $RB_RED
                _RBRightRotate($pRoot, $pNode.Parent)
                $pSibling = $pNode.Parent.Left
            EndIf
            If $pSibling.Right.Color = $RB_BLACK And $pSibling.Left.Color = $RB_BLACK Then
                $pSibling.Color = $RB_RED
                $pNode = $pNode.Parent
            Else
                If $pSibling.Left.Color = $RB_BLACK Then
                    $pSibling.Right.Color = $RB_BLACK
                    $pSibling.Color = $RB_RED
                    _RBLeftRotate($pRoot, $pSibling)
                    $pSibling = $pNode.Parent.Left
                EndIf
                $pSibling.Color = $pNode.Parent.Color
                $pNode.Parent.Color = $RB_BLACK
                $pSibling.Left.Color = $RB_BLACK
                _RBRightRotate($pRoot, $pNode.Parent)
                $pNode = $pRoot
            EndIf
        EndIf
    WEnd
    $pNode.Color = $RB_BLACK
EndFunc

Func _RBLeftRotate(ByRef $pRoot, $pNode)
    Local $pRightChild = $pNode.Right
    $pNode.Right = $pRightChild.Left
    If $pRightChild.Left Then $pRightChild.Left.Parent = $pNode
    $pRightChild.Parent = $pNode.Parent
    If Not $pNode.Parent Then
        $pRoot = $pRightChild
    ElseIf $pNode = $pNode.Parent.Left Then
        $pNode.Parent.Left = $pRightChild
    Else
        $pNode.Parent.Right = $pRightChild
    EndIf
    $pRightChild.Left = $pNode
    $pNode.Parent = $pRightChild
EndFunc

Func _RBRightRotate(ByRef $pRoot, $pNode)
    Local $pLeftChild = $pNode.Left
    $pNode.Left = $pLeftChild.Right
    If $pLeftChild.Right Then $pLeftChild.Right.Parent = $pNode
    $pLeftChild.Parent = $pNode.Parent
    If Not $pNode.Parent Then
        $pRoot = $pLeftChild
    ElseIf $pNode = $pNode.Parent.Right Then
        $pNode.Parent.Right = $pLeftChild
    Else
        $pNode.Parent.Left = $pLeftChild
    EndIf
    $pLeftChild.Right = $pNode
    $pNode.Parent = $pLeftChild
EndFunc

Func _RBTransplant(ByRef $pRoot, $pNode1, $pNode2)
    If Not $pNode1.Parent Then
        $pRoot = $pNode2
    ElseIf $pNode1 = $pNode1.Parent.Left Then
        $pNode1.Parent.Left = $pNode2
    Else
        $pNode1.Parent.Right = $pNode2
    EndIf
    If $pNode2 Then $pNode2.Parent = $pNode1.Parent
EndFunc

Func _RBMinimum($pNode)
    While $pNode.Left
        $pNode = $pNode.Left
    WEnd
    Return $pNode
EndFunc

Func _RBSearch($pNode, $vData)
    While $pNode And $vData <> $pNode.Data
        If $vData < $pNode.Data Then
            $pNode = $pNode.Left
        Else
            $pNode = $pNode.Right
        EndIf
    WEnd
    Return $pNode
EndFunc

 

Edited by LAteNightSpecial
Link to comment
Share on other sites
LAteNightSpecial Seeker

LAteNightSpecial

Posted
  • Author
Posted
16 minutes ago, AspirinJunkie said:

For performance reasons, I see 2 aspects here:

Keeping the nodes as DllStruct should be slower at first, because accessing a node requires that you create a new DLLStruct over a certain pointer.
With Map, on the other hand, access is via the index.
The latter is initially faster than the DLLStruct method.
But: The greater the number of nodes, the more the picture changes.
Access to individual elements of the node map becomes slower and slower.
This means that it basically depends on the number of nodes to see which variant you prefer for performance reasons.

The reason for this behavior of maps is (as far as I can deduce from measured values) that AutoIt maps have a fixed size without any resizing. If the map has a fixed size of 256 elements, for example, then we inevitably have more and more hash collisions the more elements are stored in it. In order to access an element, the subarray at the hash index must then be traversed linearly each time to find the element - this takes time.

Absolutely! Your breakdown of the performance trade-offs between DllStructs and maps for your Red-Black tree implementation is accurate. Let's delve into the details and discuss potential strategies.

Performance Considerations

  • DllStruct Overhead: You're right, there's a slight overhead in creating a new DllStruct instance over a pointer when accessing node properties.

  • Map Hash Collisions: As you've observed, maps in AutoIt likely have a fixed size, making them prone to hash collisions as the number of elements increases. This leads to the linear traversal of subarrays, impacting access time.

Hybrid Approach: Pros and Cons

Your hybrid approach cleverly attempts to balance these factors. However, there's an important caveat: The gains from using DllStructs at smaller scales might be overshadowed by the overhead of the helper functions (_RBGetData, _RBGetChild, etc.) that are needed to make the hybrid method work smoothly.

Strategies

  1. Profiling: Before making any significant changes, profile your code with real-world data under various tree sizes. This will pinpoint the actual bottlenecks and guide optimization efforts.

  2. Selective Optimization: If profiling reveals that node access is the primary bottleneck, consider a more selective optimization:

    • Keep nodes as purely objects (maps).
    • Introduce a DllStruct cache: Maintain a DllStruct representation only for a limited number of the most recently accessed nodes. This would give you fast access for frequently used nodes while avoiding the overhead for the entire tree.

  3. Benchmarking: If your use-case heavily favors a large number of nodes, benchmark an implementation where the nodes are pure DllStructs (no objects involved). This will give you a baseline to compare your hybrid approach against.

Caveats

  • AutoIt's internals regarding map implementation might change in the future, potentially altering the performance characteristics.
  • Premature optimization can lead to more complex code. Make decisions based on profiling results.

Questions to Consider

  • Typical Tree Size: What are the common sizes (number of nodes) of Red-Black trees you'll be working with?
  • Usage Pattern: Are node accesses heavily concentrated on a subset of nodes (recently added, frequently used), or are they more uniformly distributed across the tree?
19 minutes ago, AspirinJunkie said:

I have not yet fully understood the purpose of the _MapPut function.

A $node.Color = $RB_RED should be more performant and meaningful.

To tease out a bit of performance, you could use the _RBNodeCreate() could be rewritten like this: 

Func _RBNodeCreate($data)
    Local Static $node[]
    $node.Color = $RB_RED
    $node.Data = $data
    Return MapAppend($gNodeMap, $node) ; Return the index for reference
EndFunc

The static only creates a new map once, which is not a problem, as a copy of this is passed to MapAppend. And the attributes for Left, Right and Parent are not yet explicitly required here, as these are only explicitly described when they are inserted into the tree.
To be honest, this is not really measurable.

You bring up several excellent points! Let's analyze them in detail:

Role of _MapPut

You're absolutely right about the redundancy of the _MapPut function in the context of Red-Black Trees. In the earlier iterations of our code, where nodes were purely maps, using _MapPut to modify properties made sense. However, in our current hybrid approach, directly assigning to the object property ($node.Color = $RB_RED) is indeed the more efficient and natural way to do it.

Optimizing _RBNodeCreate

Your approach to optimizing _RBNodeCreate is clever:

  • Static Map: Using a static map to avoid recreating the base node structure repeatedly does offer a slight optimization.
  • Preemptive Color: Setting the color to $RB_RED by default is logical given that new nodes are generally inserted as red.
  • Delayed Attributes: Deferring the initialization of Left, Right, and Parent attributes until insertion is a sensible choice that reduces unnecessary overhead during node creation.

Measurability

You are correct in that the performance gains of these optimizations might be difficult to measure in isolation. The benefit is likely to be more noticeable at a larger scale within the complete Red-Black tree operations.

Important Considerations

  1. Trade-Offs: While these optimizations are good, keep in mind the trade-off in code readability. Sometimes, a slightly clearer structure might be preferable over minuscule performance gains.

  2. Profiling: As always, the best way to make informed optimization decisions is to profile your code with realistic datasets to see if node creation is indeed a significant bottleneck.

Let's Continue Refining & Optimizing!

Thank you very much for assisting in this project!

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share
Go to topic listing

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...