Talk:Red black tree sort/Wren

Note that if you allow duplicate keys, then a key does not uniquely identify a node. This becomes an issue if the tree is used as a key/value store.

It's true, however, if that if the tree is only used to implement sorting of the keys, we would want to support duplicate keys.

In any event... you would get a small efficiency gain if in insert() you removed the line if (!_allowDups && hasKey(key)) return and added if (!_allowDups && key == y.data) return after the while loop (and I guess you would want to move the var node= ... line to follow this test). --Rdm (talk) 03:04, 15 June 2022 (UTC)

Well, I did it the way I have partly to test that the searchTree method was working properly (which it seems to be) and also to avoid having to create a Node object if there were a duplicate. In Wren this would require a heap allocation and hence, in due course, garbage collection so it's not certain to be more efficient. So, if you don't mind, I'm going to leave it as it is as the code runs near instantly anyway. --PureFox (talk) 08:03, 15 June 2022 (UTC)

It's fine to leave it as it is. (Though if I knew enough about Wren to test the code, I'd be tempted to change it ...but I'd first want to test my hypothetical changes for accuracy, and benchmark those changes for performance, and it's not like I don't have lots of other things to be doing...).

That said, you could move the creation of node to after the while loop if you replaced the reference to node.data in the while loop with a reference to key. This would eliminate any unnecessary Node objects. --Rdm (talk) 18:02, 15 June 2022 (UTC)

OK, I've tested that and it does seem to be faster than before. So, thanks, I've changed the 'master' copy now :) --PureFox (talk) 23:08, 15 June 2022 (UTC)