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)

On the talk page for Algebraic data types

I like the task, but I don't think it's a good application of the general case of pattern matching. Pattern 
Matching should probably be geared towards globs and regular expressions, while this page should get moved to 
something like Red-Black Tree. Thoughts? --Short Circuit 22:19, 6 November 2007 (MST)

Are you trying to do this? On Algebraic data types I've added a reference to a paper describing what I think the author wanted done on that task.--Nigel Galloway (talk) 13:46, 20 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)