Good day.
I'm currently reading the paper "Purely Functional Representations of Catenable Sorted Lists" by Tarjan and Kaplan[link to the paper]. But I have a question about the modified 2-3 finger search trees in Section 3(nodes of degrees 1 to 4 are allowed on left and right spines). Below I briefly describe the problem and where I have the question.
More precisely, I interest in how they maintain the Invariant 3.1 during the insertion.
Invariant 3.1:
- There are no two 4-nodes with a 3-list between them.
- There are no two 1-nodes with a 2-list between them.
They denote the node on the right spine where they insert the element as $v$. If $v$ is node of degree 2 or 3 then $y$ denotes the {2-3}-list where $v$ is. The insertion operation inserts a key into the regular 2-3 tree $T$ to which $v$ points to.
There are two possible cases:
- The height of the tree does not increase.
- The height of the tree increases by one. Then the inserting algorithm instead of splitting the root returns two trees $T_1$ and $T_2$ of the same height as $T$, and a key $k$.
If the case 2 occurs the the degree of $v$ increases by one since it has to point to $T_1$ and $T_2$. We use the operations Fix&Push and Fix&Concatenate(defined in the paper) to maintain the Invariants 3.1. There are four cases according to the change in the degree of $v$.
I have a question about the case 2: degree of $v$ changes from $3$ to $4$. We perform Fix&Push(v, $S_u$) and Fix&Catenate($S_u$, $S_l$), where $S_u$ and $S_l$ are the list containing elements of the spine list(I did not give exact definitions here because I count on the help of the researchers how have read the paper). Consider the following example. Let right spine's list $R$ = {{2}, {3, 3, 3, 3, 3}, 4}. Then $v$ is bolded element(third element) and $y$ = {3, 3, 3, 3, 3}. After the split of $R$ we have: $S_u$ = {2, {3, 3}} and $S_l$ = {{3, 3}, 4}. The degree of $v$ is 4 after the insertion. Then the result of Fix&Push(v, $S_u$) is $S_u$ = {2, {3, 3}}, 4}. And the result of Fix&Catenate($S_u$, $S_l$) is {{2}, {3, 3}, 4, {3, 3}, 4}. This violates the Invariant 3.1(bolded elements). This is due to the fact that Fix&Catenate does not fix the cases like Fix&Catenate({{3, 3}, 4}, {{3, 3}, 4}). It's very easy to fix it: just add the necessary operations in the Fix&Catenate. But I do not understand why did not the authors do this? May be I'm missing something?
Thank you for help. I understand that the description of the problem is vague, but I hope the researches which have read this paper will understand my question.
