Remove Id

[Beakerboy]

• The __eq__ method would evaluate true only when objects had matching Node.id, which would only occur if items were the same object. Comparing the object without this method accomplishes the same thing. The only time this would not be the case is if allowing the user to modify Node.id was desirable behavior.
• the only other thing Node.id was used for was to determine if a node was null. Instead of using Node.id == -1, Node._key is None is as effective and arguably less arbitrary.

[Beakerboy]

If you have a chance, there may be an issue hiding within the rotation methods. If the __eq__() method is changed to return self._key == other._key, A few tests fail. I was hoping to be able to override all the comparator methods, to allow users to do node_1 < node_2 instead of node_1.get_key() < node_2.get_key() but something with allowing duplicates makes this fail. Is this a bug?

Also, have you thought about how to handle duplicate node (ie same key) but with different values? For me it is like being able to construct an array such that if you ask for the value in position 2, the result can be any one of several.

Finally, if there are any changes you’ve been itching to make but have not had the time, let me know (or add it to the repository issues queue) and I can do it for you.

[Beakerboy]

Do you have any thoughts on the direction I’m taking with these changes?

[Beakerboy]

I'm thinking the "==" issue can be remidied through the use of the id() function. Let me know your thoughts on this. Data in the tree should be fungible. The only important attributes should be the values, not any metadata like the memory address*. The comparison functions can be overridden to compare values, but I could add a Node.is_same(node: Node) -> bool function that checks if the provided node is the same object. This way, the spots in the code that ask x == x.parent.left can be changed to x.is_same(x.parent.left) and other places that are concerned about the value of the node can use x == y.

* still awaiting your thought on how to handle situations where the same key is in the tree with multiple values.

[emilydolson]

That all makes sense to me! I hadn't thought about the case where there are multiple nodes with the same key and different values. Should that be allowed? I guess it's a natural consequence of allowing duplicates and also allowing the dictionary-like interface, but it seems like it could lead to unexpected behavior.

Which tests were failing when you updated the equals operator?

[Beakerboy]

Here is a branch with the change to __eq__(): https://github.com/Beakerboy/python-red-black-trees/tree/update_eq and here is a test run: https://github.com/Beakerboy/python-red-black-trees/actions/runs/4872274752/jobs/8690255297?pr=20

It appears that when there are duplicates, the rotation methods will make an invalid tree if only the node values are examined. The comparison node == node.parent.left needs to be asking "am I to the left of my parent" versus "do I have the same value as the object to the left of my parent". It may not all be a bug, but more a semantic distinction that needs to be flushed out.

[Beakerboy]

I don't think any of these "bug" issues are blockers for this pull request, so feel free to merge if you think it's acceptable.