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?
Aucun commentaire:
Enregistrer un commentaire