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!

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