Jump to content

Talk:Red black tree sort

From Rosetta Code

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)
Actually, I am trying to do the opposite -- though for similar reasons. Here, I am trying to make room for red-black tree implementations which are not based on pattern matching.
In this context -- once we have more of the details sorted out -- it might be interesting to compare some of the implementations (pattern matching vs non-pattern matching, in languages where an implementation has been supplied for each approach). --Rdm (talk) 18:45, 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)

Cookies help us deliver our services. By using our services, you agree to our use of cookies.