Talk:Red black tree sort: Difference between revisions
→Validation issues: new section |
Red-Black Trees in a Functional Setting |
||
Line 1: | 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) |
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) |
||
: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.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 13:46, 20 June 2022 (UTC) |
|||
== Validation issues == |
== Validation issues == |
||
Revision as of 13:46, 20 June 2022
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)