Talk:Red black tree sort: Difference between revisions
Content deleted Content added
Created page with "I am creating this task because the Algebraic data types task introduces unnecessary complexity in some languages. --~~~~" |
→Validation issues: new section |
||
Line 1:
I am creating this task because the [[Algebraic data types]] task introduces unnecessary complexity in some languages. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 17:55, 13 June 2022 (UTC)
== Validation issues ==
I took the python implementation and added a validate method to the RBTree class:
<lang python> def validate(self, node):
if self.NULL == node :
return 1
if self.NULL != node.left :
if node != node.left.parent :
self.print_tree()
assert node == node.left.parent
a= self.validate ( node.left )
if self.NULL != node.right :
if node != node.right.parent :
self.print_tree()
assert node == node.right.parent
b= self.validate ( node.right )
if a!=b :
self.print_tree()
print ('a: '+str(a))
print ('b: '+str(b))
assert a==b
return a+1-node.color</lang>
Then I added a call to <tt>self.validate()</tt> to the bottom of <tt>delete_node_helper</tt> and changed the loop to shuffle the first 300 positive integers, insert them, then shuffle the first 150 positive integers and delete them.
This would sometimes (not always) result in a validation error with (a!=b).
I've been noticing the potential for similar issues with some of the other implementations for delete. (But I am not as familiar with some of those other languages, so I will have to rely on someone else to investigate those examples.)
I've added a validation suggestion to the draft task. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 03:18, 20 June 2022 (UTC)
| |||