I recently created a red-black tree in C# to better understand how it works. Wit
ID: 645967 • Letter: I
Question
I recently created a red-black tree in C# to better understand how it works. With it, I implemented an in-order enumerator, however I quickly realized that enumerating a tree can have destructive results.
Consider this code:
RedBlackTree<Person> tree = new RedBlackTree<Person>();
tree.Add(new Person("Randy"));
// add more people
...
foreach(var person in tree)
{
if (person.Name == "Randy")
{
person.Name = "Cheeseburger eater";
}
}
The tree requires the generic parameter to implement IComparable interface, in order to correctly determine ordering of items.
If Person class is compared by name, then, by changing the name during enumeration, we might have broken the ordering. e.g. randyNode.CompareTo(randyNode.Right) < 0 might be false, which breaks the fundamental BST property, that left child is smaller than its parent and right child bigger.
In this case, is it better to remove tree enumeration altogether, or should I keep it in, with a huge warning to not modify the items during enumeration?
Explanation / Answer
You'll find with existing C# collections, attempting to mutate the collection while iterating causes exceptions. It would be idiomatic to throw an exception in that scenario in your collection.
The problem that you'll face is that this doesn't matter if you're iterating. If someone changes person.Name, your RBT is already out of order - iteration or no.