kalkwst / microlib Goto Github PK

A scapegoat tree is a type of self-balancing binary search tree, which is used to efficiently store and retrieve data. It is similar to other types of self-balancing trees, such as AVL and red-black trees, in that it automatically adjusts the structure of the tree to maintain a balance between its left and right branches. However, it is different in that it adjusts the tree based on a dynamic threshold, rather than a fixed one, which can lead to more efficient use of memory and improved performance of search and insertion operations.

From a more technical perspective, a scapegoat tree is a self-balancing binary search tree that uses a dynamic threshold to ensure balance. It maintains a balance by periodically rebuilding the tree if the size of a subtree exceeds a certain threshold, the value of which is adjusted dynamically. The threshold is calculated by comparing the size of the subtree to the number of nodes in the tree. When a new node is added to the tree, it is placed in the correct position based on its value. If the size of a subtree exceeds the threshold, the subtree is rebuilt to maintain balance. The time complexity for search, insertion and deletion operations in a scapegoat tree is O(log n), but it's slightly worse than AVL or red-black trees, as it needs to rebuild the tree periodically.

A suffix tree is a data structure that is used to efficiently store and search for all possible substrings in a given string. It is a compacted trie of all suffixes of a given text. The tree is built by breaking down the text into substrings called suffixes, and then organizing the suffixes into a tree-like structure. Each leaf node of the tree represents a suffix of the text, and the edges between nodes represent the characters that make up the suffix. This allows for efficient search, insertion, and deletion operations, as well as finding the longest common substring of a given string.

From a more technical perspective, a suffix tree is a data structure that is used to efficiently store and search for all possible substrings in a given string. It is a compacted trie of all suffixes of a given text. The tree is built by breaking down the text into substrings called suffixes, and then organizing the suffixes into a tree-like structure. Each leaf node of the tree represents a suffix of the text, and the edges between nodes represent the characters that make up the suffix. This allows for efficient search, insertion, and deletion operations, as well as finding the longest common substring of a given string in linear time O(n) where n is the length of the string. It also allows for pattern matching, finding the number of occurrences of a pattern in a text and many other string-related problems. The suffix tree is particularly useful for working with large strings or texts, as it allows for efficient search, insertion, and deletion operations, as well as finding the longest common substring of a given string.

A splay tree is a type of self-balancing binary search tree, which is used to efficiently store and retrieve data. It is different from other types of self-balancing trees in that it adjusts the tree based on the usage patterns of the data, rather than by maintaining a specific balance condition. This can lead to improved performance of search and insertion operations, especially when the tree is being used to store data that is accessed frequently.

From a more technical perspective, a splay tree is a self-balancing binary search tree that uses a series of rotations to adjust the tree based on usage patterns. When a node is accessed, it is moved to the root of the tree, and the tree is adjusted accordingly to keep the most frequently accessed nodes closer to the root. This can improve the performance of search and insertion operations, as the nodes that are accessed most frequently are closer to the root and can be accessed faster. The time complexity for search and insertion operations in a splay tree is O(log n) on average, but it can be as fast as O(1) if the accessed node is already in the tree and it's near the root. However, it can be as slow as O(n) if the tree is unbalanced and all nodes are accessed in sequential order.

A treap is a type of binary search tree that is used to efficiently store and retrieve data. It is a combination of a binary search tree and a heap. Each node in the tree has a key and a priority, where the key is used to organize the data in a hierarchical structure similar to a binary search tree, and the priority is used to maintain the heap property, where the parent node has a higher priority than its children. This allows for efficient operations like search, insert and delete with a time complexity of O(log n) where n is the number of nodes in the tree.

From a more technical perspective, a treap is a binary tree data structure that is built by combining a binary search tree and a heap. It has a key and a priority associated with each node, where the key is used to organize the data in a hierarchical structure similar to a binary search tree, and the priority is used to maintain the heap property, where the parent node has a higher priority than its children. This combination of a binary search tree and a heap allows for efficient operations like search, insert and delete with a time complexity of O(log n) where n is the number of nodes in the tree. Additionally, the heap property ensures that the height of the tree remains logarithmic, which ensures that the time complexity of the operations remains logarithmic as well. It's a randomized data structure, the priority is assigned randomly to each node, this way it can be used in situations where the data is not guaranteed to be sorted.

A predicated list decorator is an additional layer of functionality that can be applied to an existing list data structure to enable it to use a specific rule or condition, known as a predicate, to organize its elements. The decorator allows the user to define a specific predicate for the list, which will be used to organize the elements in the list in a specific way, without modifying the underlying list data structure. This enables the user to add this functionality to an existing list without having to change the way the list is implemented.

From a more technical perspective, a predicated list decorator is a design pattern that can be used to add a new layer of functionality to an existing data structure. It is used to add a predicate-based organization to an existing list without having to change its underlying implementation. The decorator pattern is implemented using inheritance and composition, where the decorator class inherits from the list class and adds new methods and/or fields to the list class. The decorator class wraps the existing list object and adds the new predicate-based functionality by overriding the appropriate methods. The new methods of the decorator class use the predicate to organize the elements in the underlying list object. This way, the decorator class can be easily added to any existing list and can be easily removed if it's not needed anymore. The time complexity of the search, insertion and deletion operations in a predicated list decorator depends on the complexity of the predicate and the size of the list.

A transformer queue decorator is an additional layer of functionality that can be applied to an existing queue data structure, allowing it to transform its elements in a specific way, without modifying the underlying queue data structure. The decorator allows the user to define a specific transformation for the queue, which will be used to change the elements in the queue, without changing the way the queue is implemented. This enables the user to add this functionality to an existing queue without having to change the way the queue is implemented.

From a more technical perspective, a transformer queue decorator is a design pattern that can be used to add a new layer of functionality to an existing data structure. It is used to apply a specific transformation to the elements in an existing queue without having to change its underlying implementation. The decorator pattern is implemented using inheritance and composition, where the decorator class inherits from the queue class and adds new methods and/or fields to the queue class. The decorator class wraps the existing queue object and adds the new transformation functionality by overriding the appropriate methods. The new methods of the decorator class use the transformation function to change the elements in the underlying queue object. This way, the decorator class can be easily added to any existing queue and can be easily removed if it's not needed anymore. The time complexity of the enqueue, dequeue and peek operations in a transformer queue decorator depends on the complexity of the transformation function and the size of the queue.

Feel free to propose and/or implement new data structures, I will add them to the list below :)

Lists

• Doubly Linked List (see issue here)
• Skip List (see issue here)
• Unrolled List (see issue here)
• Self-Organizing List (see issue here)
• Tree-List (see issue here)

List Decorators

• Predicated Decorator (see issue here)
• Transformer Decorator (see issue here)
• Lazy Decorator (see issuehere)
• SetUnique Decorator (see issue here)

Queues

• Circular FIFO Queue (see issue here)

Queue Decorators

• Predicated Decorator (see issue here)
• Transformer Decorator (see issue here)
• SetUnique Decorator (see issue here)

Trees

Binary Trees

• AVL Tree (see issue here)
• Binary Search Tree (see issue here)
• Cartesian Tree (see issue here)
• Red-Black Tree (see issue here)
• Rope Tree (see issue here)
• Scapegoat Tree (see issue here)
• Splay Tree (see issue here)
• Threaded Binary Tree (see issue here)
• Treap Tree (see issue here)

B-Trees

• 2-3 Tree (see issue here)
• 2-3-4 Tree (see issue here)

Bit-Splice Trees

• Radix Tree (see issue here)
• Suffix Tree (see issue here)

A circular FIFO (First In First Out) queue is a type of queue data structure that is similar to a regular queue but with the added feature of being able to "wrap around" when it reaches the end. This allows for more efficient use of memory, as the oldest element is overwritten when a new element is added to a full queue, instead of having to allocate additional memory for a new element.

From a more technical perspective, a circular FIFO queue is a data structure that follows the FIFO principle, where the first element added to the queue is the first one to be removed. The difference is that when the last position of the queue is reached, the next element will be added at the first position, overwriting the oldest element. The queue has two pointers, one pointing to the front of the queue and the other pointing to the next free position. When an element is dequeued, the front pointer is incremented, and when an element is enqueued, the next free position pointer is incremented, if the next free position pointer reaches the end of the queue, it wraps around to the first position. This way, the queue can use a fixed amount of memory and it's efficient in terms of memory usage and time complexity, as both enqueue and dequeue operations have constant time complexity O(1).

A skip list is a data structure that is similar to a linked list but with an added feature of hierarchical levels that allow for faster search and insertion operations. Each node in a skip list contains an element of data and a set of pointers that link to other nodes at different levels. These pointers allow the data to be "skipped" over, making it possible to quickly find a specific element in the list.

From a more technical perspective, a skip list is a probabilistic data structure that is used to implement a sorted dictionary. It is a linked list with multiple levels, each level represents a level of "skipping" and each node in the list contains elements along with a set of forward pointers to other nodes in the list. The highest level contains all the elements in the list and the lower levels have subsets of the elements, where each element has a probability of appearing in the lower levels. Each level of a skip list is a regular singly linked list. The search and insertion operations are done from the highest level and move down the levels until the appropriate element is found or the bottom level is reached. The expected time complexity of search, insertion and deletion operations is O(log n) which is faster than the O(n) time complexity of a typical singly linked list.

A binary search tree (BST) is a type of data structure that is used to efficiently store and retrieve data. It organizes the data in a hierarchical structure, where each node has a value, the left subtree of a node contains values that are less than the node's value, and the right subtree of a node contains values that are greater than the node's value. This allows for efficient searching, insertion, and deletion operations, as the tree can be traversed starting from the root node to reach the desired node in logarithmic time complexity.

From a more technical perspective, a binary search tree (BST) is a binary tree data structure where each node has up to two children, left and right and every node in the left subtree of a node has a value less than the node, and every node in the right subtree of a node has a value greater than the node. This property allows for efficient searching, insertion, and deletion operations, as the tree can be traversed starting from the root node to reach the desired node in a logarithmic time complexity O(log n) where n is the number of nodes in the tree. However, if the tree is not balanced, the time complexity of the operation can be worse than O(n), where n is the number of nodes in the tree. Therefore, it is important to keep the tree balanced by using techniques such as AVL tree or red-black tree to ensure that the time complexity of the operations remains logarithmic.

A red-black tree is a type of self-balancing binary search tree, which is used to efficiently store and retrieve data. It is similar to other types of self-balancing trees, such as AVL and AA trees, in that it automatically adjusts the structure of the tree to maintain a balance between its left and right branches. This ensures that the tree remains relatively balanced even as elements are added or removed, which improves the performance of search and insertion operations.

From a more technical perspective, a red-black tree is a self-balancing binary search tree that uses the concept of colour to ensure balance. Each node in the tree can be coloured either red or black, and the tree is balanced by enforcing certain constraints on the colour of the nodes. The constraints ensure that the number of black nodes on any path from the root to a leaf is the same for all paths and that no red node has a red child. When a new node is added to the tree, it is placed in the correct position based on its value and the tree is adjusted accordingly to maintain the balance and the constraints of the colour. The tree can be adjusted by performing rotations on the nodes and/or flipping the colour of the nodes. This way the tree can be adjusted to maintain the balance and ensure the constraints of the colour. The time complexity for search, insertion and deletion operations in a red-black tree is O(log n), which is faster than the O(n) time complexity of a typical unbalanced binary search tree.

A predicated queue decorator is an additional layer of functionality that can be applied to an existing queue data structure, allowing it to use a specific rule or condition, known as a predicate, to organize its elements. The decorator allows the user to define a specific predicate for the queue, which will be used to organize the elements in the queue in a specific way, without modifying the underlying queue data structure. This enables the user to add this functionality to an existing queue without having to change the way the queue is implemented.

From a more technical perspective, a predicated queue decorator is a design pattern that can be used to add a new layer of functionality to an existing data structure. It is used to add a predicate-based organization to an existing queue without having to change its underlying implementation. The decorator pattern is implemented using inheritance and composition, where the decorator class inherits from the queue class and adds new methods and/or fields to the queue class. The decorator class wraps the existing queue object and adds the new predicate-based functionality by overriding the appropriate methods. The new methods of the decorator class use the predicate to organize the elements in the underlying queue object. This way, the decorator class can be easily added to any existing queue and can be easily removed if it's not needed anymore. The time complexity of the enqueue, dequeue and peek operations in a predicated queue decorator depend on the complexity of the predicate and the size of the queue.

A Cartesian tree is a type of binary tree that can be used to efficiently store and retrieve data. It is built from a given array of data and the tree has the property that the value of a node is greater than or equal to the value of its left child and less than or equal to the value of its right child. This allows for efficient operations like range queries, as it can be used to find the range of elements in a given interval efficiently.

From a more technical perspective, a Cartesian tree is a binary tree that is built from a given array of data. It is constructed by selecting the element that is at the middle of the array, which becomes the root of the tree, and recursively building the left and right subtrees by selecting the middle element of the left and right parts of the array. This way, the value of a node is greater than or equal to the value of its left child and less than or equal to the value of its right child. This property allows for efficient operations like range queries, as it can be used to find the range of elements in a given interval efficiently in a time complexity of O(log n) where n is the number of nodes in the tree. It can also be used to construct a balanced binary search tree from a given array of data, which can be useful in situations where the data is not guaranteed to be sorted.

A rope is a data structure that is used to represent a large string as a collection of smaller strings, called "nodes." This allows for more efficient manipulation of large strings, such as concatenation, insertion, and deletion, as these operations can be performed on individual nodes rather than on the entire string. It's a good data structure to handle large text files or strings where we need to perform many operations like insertions, deletions, and concatenations.

From a more technical perspective, a rope is a binary tree data structure, where each node in the tree represents a substring of the original string. The leaves of the tree are the individual characters of the string, and the internal nodes represent the concatenation of their children nodes. This way, the rope can represent a very large string using a relatively small number of nodes. The tree is balanced by enforcing certain constraints on the size of the nodes, which ensures that the height of the tree is logarithmic with respect to the size of the string. The rope data structure uses a combination of techniques such as concatenation, insertion, and deletion on the individual nodes to perform the operations on the large string efficiently. The time complexity of the operations on a rope is generally O(log n) where n is the size of the string.

An AVL tree is a type of self-balancing binary search tree, which is used to efficiently store and retrieve data. It is similar to other types of self-balancing trees, such as AA and red-black trees, in that it automatically adjusts the structure of the tree to maintain a balance between its left and right branches. This ensures that the tree remains relatively balanced even as elements are added or removed, which improves the performance of search and insertion operations.

From a more technical perspective, an AVL tree is a self-balancing binary search tree that uses the concept of height balance to ensure the balance of the tree. Every node in the tree has a height, which is determined by the number of edges from the node to the leaf. The tree is balanced by ensuring that the difference in height between the left and right subtrees of any node is at most one. When a new node is added to the tree, it is placed in the correct position based on its value and the tree is adjusted accordingly to maintain the balance. The tree can be adjusted by performing rotations on the nodes, this way the tree can be adjusted to maintain the balance and keep the difference in height between the left and right subtrees of any node at most one. The time complexity for search, insertion and deletion operations in an AVL tree is O(log n), which is faster than the O(n) time complexity of a typical unbalanced binary search tree.

A radix tree, also known as a Patricia trie, is a type of tree data structure that is used to efficiently store and retrieve data that is represented as strings. It organizes data in a hierarchical structure, where each node represents a single character in a string, and the edges between nodes represent the characters in the string. It is particularly useful for storing a large number of strings, as it allows for efficient search, insertion, and deletion operations, as well as finding the longest prefix match of a given string.

From a more technical perspective, a radix tree is a tree-like data structure used to store a set of strings. It's a trie where each node represents a character in a string, and the edges between nodes represent the characters in the string. The tree is organized in such a way that common prefixes of the strings are grouped together, which allows for efficient search, insertion, and deletion operations. The time complexity for these operations is O(k) where k is the length of the string, which is faster than other data structures like a hash table or binary search tree. It also allows for finding the longest prefix match of a given string in O(k) time complexity. The radix tree is particularly useful for storing a large number of strings, such as IP addresses, DNS names, or phone numbers, in a way that allows for efficient search, insertion, and deletion operations.

A transforming list decorator is a layer of functionality that can be applied to an existing list data structure to enable it to transform its elements in a specific way, without modifying the underlying list data structure. The decorator allows the user to define a specific transformation for the list, which will be used to change the elements in the list, without changing the way the list is implemented. This enables the user to add this functionality to an existing list without having to change the way the list is implemented.

From a more technical perspective, a transforming list decorator is a design pattern that can be used to add a new layer of functionality to an existing data structure. It is used to apply a specific transformation to the elements in an existing list without having to change its underlying implementation. The decorator pattern is implemented using inheritance and composition, where the decorator class inherits from the list class and adds new methods and/or fields to the list class. The decorator class wraps the existing list object and adds the new transformation functionality by overriding the appropriate methods. The new methods of the decorator class use the transformation function to change the elements in the underlying list object. This way, the decorator class can be easily added to any existing list and can be easily removed if it's not needed anymore. The time complexity of the search, insertion and deletion operations in a transforming list decorator depends on the complexity of the transformation function and the size of the list.

A self-organizing list is a data structure that automatically rearranges its elements based on usage patterns. The idea behind this is those elements that are accessed more frequently are moved closer to the front of the list, making them faster to access in the future. This allows for faster access to the most frequently used elements, improving the overall performance of the list.

From a more technical perspective, a self-organizing list is a variation of a linked list that rearranges its elements based on their access frequency. It uses different algorithms to move the elements that are accessed more frequently towards the front of the list. The most common algorithms used for this purpose are the move-to-front, transpose, and count algorithms. Move-to-front moves the accessed element to the front of the list, transpose moves the accessed element one position forward, and the count keeps track of the access count of each element and moves it to the front of the list based on its access count. These algorithms are used to improve the cache locality, and as a result, the access time for the frequently accessed elements becomes faster. These lists are especially useful in scenarios where the elements' access pattern is not random but follows certain rules or patterns.

An unrolled linked list is a variation of the traditional linked list data structure where each node contains a small array of elements instead of a single element. This allows for more efficient memory usage and faster access to elements that are stored close to each other in the list. The size of the array, or the block size, is usually chosen based on the characteristics of the data and the expected usage of the list.

From a more technical perspective, an unrolled linked list is a linked list with the difference that instead of each node containing a single element, it contains an array of elements, called a block. These blocks reduce the number of pointers required, thus decreasing the cache miss rate and improving performance. Each node also contains a pointer to the next node in the list and the number of elements stored in the current node. The size of the block is chosen based on the expected usage of the list, and it can be adjusted based on the performance characteristics. The search and insertion operations are done by traversing the list and looking for the correct position in the current block. The deletion operation is done by copying the elements from the following block to the current block and removing the next one. The time complexity of the search, insertion and deletion operations is usually O(n/b) where b is the block size, which is faster than the O(n) time complexity of a typical singly linked list.

A set-unique list decorator is a layer of functionality that can be applied to an existing list data structure, allowing it to only store unique elements and automatically remove any duplicates. This can be useful for situations where the list should only contain unique elements and the user should not have to manually check for and remove duplicates.

From a more technical perspective, a set-unique list decorator is a design pattern that can be used to add a new layer of functionality to an existing data structure. It is used to ensure that the elements in an existing list are unique, by automatically removing any duplicates when they are added. The decorator pattern is implemented using inheritance and composition, where the decorator class inherits from the list class and adds new methods and/or fields to the list class. The decorator class wraps the existing list object and adds the new set-unique functionality by overriding the appropriate methods. The new methods of the decorator class use a set data structure to keep track of the unique elements, and this way, the decorator class can be easily added to any existing list and can be easily removed if it's not needed anymore. The time complexity of the search, insertion and deletion operations in a set-unique list decorator depends on the size of the list and the complexity of the set operations.

A 2-3-4 tree is a type of self-balancing tree data structure that is used to efficiently store and retrieve data. It is similar to a 2-3 tree, but each node can have up to 4 keys and 5 children, which allows for more efficient storage and retrieval of data by reducing the number of nodes that need to be traversed to locate the data.

From a more technical perspective, a 2-3-4 tree is a self-balancing tree data structure that is similar to a 2-3 tree. Each node in the tree can have up to 4 keys and 5 children, which allows for more efficient storage and retrieval of data by reducing the number of nodes that need to be traversed to locate the data. The tree is organized in such a way that each node has either three children (if it has one or two keys) or four children (if it has three keys). This allows for efficient search, insertion, and deletion operations, as the tree can be traversed starting from the root node to reach the desired node in logarithmic time complexity O(log n) where n is the number of nodes in the tree. Additionally, the tree is balanced by ensuring that the number of nodes in the left and right subtrees of any node is roughly equal, which ensures that the time complexity of the operations remains logarithmic as well. The 2-3-4 tree is an extension of the 2-3 tree, which allows the tree to hold more keys per node, therefore it improves the space utilization and reduces the number of nodes in the tree which results in fewer disk accesses and faster search, insertion and deletion.

List of Algorithms that should be added to the MicroLib.Random project
Feel free to propose and/or implement more algorithms, I will add them to the list below :)

Int32 Provider

• Doty-Humphrey Small Fact Counting 32 Generator
• ISAAC Generator
• Jenkins Small Fast Generator
• Marsaglia's KISS Generator
• L32X64Mix Generator
• Mersenne Twister Generator
• Middle Square Weyl Sequence Generator
• Marsaglia's Multiply With Carry Generator
• PCG-MCG-XSH-RR Generator
• PCG-MCG-XSH-RS Generator
• PCG-LCG-XSH-RR Generator
• PCG-LCG-XSH-RS Generator
• XoRoShiRo64Star Generator
• XoRoShiRo64StarStar Generator
• XoShiRo128Plus Generator
• XoShiRo128PlusPlus Generator
• XoShiRo128StarStar Generator
• Well1024a Generator
• Well44497a Generator
• Well512a Generator

Int64 Provider

• Doty-Humphrey Small Fact Counting 64 Generator
• Jenkins Small Fast 64 Generator
• L128X1024Mix Generator
• L128X128Mix Generator
• L128X256Mix Generator
• L64X1024Mix Generator
• L64X128StarStar Generator
• L64X256Mix Generator
• Mersenne Twister 64
• PCG-LCG-RXS-M-XS Generator
• SplitMix 64 Generator
• XoRoShiRo1024PlusPlus Generator
• XoRoShiRo1024Star Generator
• XoRoShiRo1024StarStar Generator
• XoRoShiRo128Plus Generator
• XoRoShiRo128PlusPlus Generator
• XoRoShiRo128StarStar Generator
• XorShift1024Star Generator
• XoShiRo256Plus Generator
• XoShiRo256PlusPlus Generator
• XoShiRo256StarStar Generator
• XoShiRo512Plus Generator
• XoShiRo512PlusPlus Generator
• XoShiRo512StarStar Generator

A doubly linked list is similar to a regular linked list, but each node contains an additional reference to the previous node in the list. This allows for more efficient traversal in both directions, as you can move both forwards and backward through the list by following the references. This makes it useful for data structures that can traverse the list in both directions like queues and dequeues.

From a more technical perspective, a doubly linked list is a more advanced version of a linked list, where each node contains an additional pointer, typically called the previous pointer, in addition to the next pointer. This allows for the traversal of the list in both directions. The doubly linked list has a head and a tail that point to the first and last elements respectively. Each node in the doubly linked list contains three fields: data, previous pointer, and next pointer. The previous pointer of the head points to null and the next pointer of the tail points to null. This data structure allows for constant-time insertions and deletions at both ends, making it useful for implementing queues and dequeues. It also allows traversing the list in both directions, but it requires more memory to store the additional pointer in each node.

A tree list is a data structure that combines the features of a linked list and a tree data structure. It allows for efficient insertion, deletion, and search of elements by organizing the data in a hierarchical tree-like structure. Each node in a tree list contains an element of data and a set of pointers to other nodes, which form a tree-like structure. This allows for fast access to specific elements in the list, even when the list contains a large number of elements.

From a more technical perspective, a tree list is a data structure that is based on a linked list and a tree. Each node in the tree list contains an element of data and a set of pointers to other nodes, which form a tree-like structure. The tree-like structure is used to organize the data in a hierarchical way, which allows for fast access to specific elements in the list. The top node in the tree is called the root node, and it serves as the entry point to the tree. Each child node has a parent node and it can have zero or more children nodes. The tree list allows for fast search, insertion and deletion operations by traversing the tree, which is faster than the linear traversal of a linked list. The time complexity of the search, insertion and deletion operations is usually O(log n), which is faster than the O(n) time complexity of a typical singly linked list.

A lazy list decorator is a layer of functionality that can be applied to an existing list data structure, allowing it to generate its elements only when they are accessed by the user, rather than generating all the elements up front. This can be useful for situations where the list is very large or the elements are expensive to generate, as it allows the user to access only the elements they need while minimizing the amount of computation required.

We should change the exception throwing to the new built in methods provided by Microsoft.
https://learn.microsoft.com/en-us/dotnet/api/system.argumentexception.throwifnullorempty?view=net-7.0
https://learn.microsoft.com/en-us/dotnet/api/system.argumentnullexception.throwifnull?view=net-7.0#system-argumentnullexception-throwifnull(system-object-system-string)

The ArgumentException.ThrowIfNullOrEmpty was introduced in .NET 7 & ArgumentNullException.ThrowIfNull on .NET 6.

Example:
from

    protected AbstractCollectionDecorator(ICollection<T> collection)
    {
        _collection = collection ?? throw new ArgumentNullException(nameof(collection));
    }

to

    protected AbstractCollectionDecorator(ICollection<T> collection)
    {
        ArgumentNullException.ThrowIfNull(collection);
        _collection = collection;
    }

A 2-3 tree is a type of self-balancing tree data structure that is used to efficiently store and retrieve data. It is similar to a binary search tree, but each node can have up to 3 keys and 4 children, which allows for more efficient storage and retrieval of data by reducing the number of nodes that need to be traversed to locate the data.

From a more technical perspective, a 2-3 tree is a self-balancing tree data structure that is similar to a binary search tree. Each node in the tree can have up to 3 keys and 4 children, which allows for more efficient storage and retrieval of data by reducing the number of nodes that need to be traversed to locate the data. The tree is organized in such a way that each node has either two children (if it has one key) or three children (if it has two keys). This allows for efficient search, insertion, and deletion operations, as the tree can be traversed starting from the root node to reach the desired node in logarithmic time complexity O(log n) where n is the number of nodes in the tree. Additionally, the tree is balanced by ensuring that the number of nodes in the left and right subtrees of any node is roughly equal, which ensures that the time complexity of the operations remains logarithmic as well.

A threaded binary tree is a type of binary tree where each node has a "thread" that links to its in-order predecessor or successor. This allows for efficient traversal of the tree in an in-order sequence without the need for recursion or stack. This can be useful in situations where in-order traversal of the tree is frequently required and the overhead of recursion or stack usage is not desirable.

From a more technical perspective, a threaded binary tree is a variation of a binary tree where each node has a left and right pointer, as in a regular binary tree, but also has a "thread" flag that indicates if the pointer is a child or a thread. The threads link a node to its in-order predecessor or successor, allowing for efficient traversal of the tree in an in-order sequence without the need for recursion or stack. The use of threads also makes it possible to traverse the tree using only a single pointer, which can be useful in situations where memory is limited. The time complexity for traversing the tree is O(n) where n is the number of nodes in the tree, which is faster than the O(n log n) of a regular binary tree traversal.

A set-unique queue decorator is an additional layer of functionality that can be applied to an existing queue data structure, allowing it to only store unique elements and automatically remove any duplicates. This can be useful for situations where the queue should only contain unique elements and the user should not have to manually check for and remove duplicates.

From a more technical perspective, a set-unique queue decorator is a design pattern that can be used to add a new layer of functionality to an existing data structure. It is used to ensure that the elements in an existing queue are unique, by automatically removing any duplicates when they are added. The decorator pattern is implemented using inheritance and composition, where the decorator class inherits from the queue class and adds new methods and/or fields to the queue class. The decorator class wraps the existing queue object and adds the new set-unique functionality by overriding the appropriate methods. The new methods of the decorator class use a set data structure to keep track of the unique elements, and this way, the decorator class can be easily added to any existing queue and can be easily removed if it's not needed anymore. The time complexity of the enqueue, dequeue and peek operations in a set-unique queue decorator depend on the size of the queue and the complexity of the set operations.