Description
Hi, this is a question about the book, I hope it's ok if I file it here.
I'm implementing the treap data structure from chapter 3, and I have problems making the insertion code work, page 84.
In particular, these lines of the pseudo-code seems contradictory to the text describing it.
The code:
if node.key <= key then
node ← node.left
else
node ← node.right
The description:
Checks how the new key compares to current node’s key; if it’s not larger, we take the left branch.
It seems that in the code we take the left branch if the new key is larger, contrary to the description.
My tests also seem to show me that making the code match the description seems to work as intended, so it seems the description is right, not the code (?) Please test further if relevant.
if key <= node.key then
node ← node.left
else
node ← node.right
Also, suggestion: maybe avoiding negative formulation like "if it's not larger" would make the description easier to understand ?
Thank you for the book, I hope this helps if I spotted a mistake, and I hope to learn something if I'm wrong and I misunderstood a part of the implementation. Sorry if it was reported before, I did not find it in the erratum.