LAteNightSpecial Posted February 24 Share Posted February 24 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 expandcollapse popup; 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 expandcollapse popup#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 More sharing options...
AspirinJunkie Posted February 25 Share Posted February 25 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 More sharing options...
LAteNightSpecial Posted February 25 Author Share Posted February 25 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. Implement all versions of the Red-Black tree (DllStruct, Map-based, and Hybrid). Create large datasets with representative data. Run timed trials for: Insertion (for multiple data points) Searching (for multiple data points) 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 More sharing options...
AspirinJunkie Posted February 25 Share Posted February 25 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 More sharing options...
LAteNightSpecial Posted February 25 Author Share Posted February 25 (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: expandcollapse popupGlobal 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: expandcollapse popupGlobal 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: expandcollapse popupGlobal 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 February 25 by LAteNightSpecial raphacp 1 Link to comment Share on other sites More sharing options...
LAteNightSpecial Posted February 25 Author Share Posted February 25 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 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. 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. 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 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. 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! raphacp 1 Link to comment Share on other sites More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now