Monday, March 29, 2010

Red Black Tree Tutorial

On examining the red black tree used for the SortedDictionary class, I realized Microsoft did not use any recursion for insertion and deletion. This seems weird, because I have never come across a top-down tree balancing method. Then I found the Eternally Confuzzled - Red Black Tree Tutorial, which clearly explains how it is done. Thanks Julienne!

Sunday, March 28, 2010

Runtime Complexity of .NET Generic Collection

I had to implement some data structures for my computational geometry class. Deciding whether to implement the data structures myself or using the build-in classes turned out to be a hard decision, as the runtime complexity information is located at the method itself, if present at all. So I went ahead to consolidate all the information in one table, then looked at the source code in Reflector and verified them. Below is my result.
Internal Implement-
ation
Add/insert Add beyond capacity Queue/Push Dequeue/
Pop/Peek
Remove/
RemoveAt
Item[index]/ElementAt(index) GetEnumerator Contains(value)/IndexOf/ContainsValue/Find
List Array O(1) to add, O(n) to insert O(n) - - O(n) O(1) O(1) O(n)
LinkedList Doubly linked list O(1), before/after given node O(1) O(1) O(1) O(1), before/after given node O(n) O(1) O(n)
Stack Array O(1) O(n) O(1) O(1) - - O(1) O(n)
Queue Array O(1) O(n) O(1) O(1) - - O(1) O(n)
Dictionary Hashtable with links to another array index for collision O(1), O(n) if collision O(n) - - O(1), O(n) if collision O(1), O(n) if collision O(1) O(n)
HashSet Hashtable with links to another array index for collision O(1), O(n) if collision O(n) - - O(1), O(n) if collision O(1), O(n) if collision O(1) -
SortedDictionary Red-black tree O(log n) O(log n) - - O(log n) O(log n) O(log n) O(n)
SortedList Array O(n), O(log n) if added to end of list O(n) - - O(n) O(log n) O(1) O(n)
SortedSet Red-black tree O(log n) O(log n) - - O(log n) O(log n) O(log n) -
Note:
Dictionary Add, remove and item[i] has expected O(1) running time
HashSet Add, remove and item[i] has expected O(1) running time
Update 25 April 2010: Added SortedSet