Talk:Red black tree sort

I am creating this task because the Algebraic data types task introduces unnecessary complexity in some languages. --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 self.validate() to the bottom of delete_node_helper 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. --Rdm (talk) 03:18, 20 June 2022 (UTC)