I'm reading the chapter Radix Search of the book Algorithms (Robert Sedgwick).
I've made a simple implementation and something isn't behaving as expected.
In program 15.5 you can see that we start with an empty tree where the head is a null node. In figure 15.12 you can see that the null node is always the leftmost node. This is also described in the text:
We use the convention that the leftmost link (the one correspond- ing to a key that is all 0 bits) does not point to any internal node
program 15.7 is the implementation of Patricia-trie insertion.
If you look at the code, there's never a chance for the head reference to change, let's say, to A as depicted in figure 15.12.
Is this a bug?
which edition you read,i have this book(algorithms in c,also writtend by sedgewick).i had discoverd the same error code as you said. first:if the trie is empty ,we first insert a item(sure creat a new node,we named it x),we should make the node be the head of the trie.but the code in the boke don't reflect this. second:if the trie is not empty,when we insert a node(named x) ,firstly we will find a node which has most sane bit with x,determine i(while (bit(v, i) == bit(w, i)) i++;) .if x's fist different bit whith head is 0,case1:head.l = insertR(head.l, x, i, head),otherwise case 2:head.r = insertR(head.r, x, i, head);