Talk:Red black tree sort: Difference between revisions
that's a good question
(Created page with "I am creating this task because the Algebraic data types task introduces unnecessary complexity in some languages. --~~~~") |
(that's a good question) |
||
| (2 intermediate revisions by 2 users not shown) | |||
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)
: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)
:: 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). --[[User:Rdm|Rdm]] ([[User talk: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 <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)
| |||