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:

  1. There are no two 4-nodes with a 3-list between them.
  2. 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:

  1. The height of the tree does not increase.
  2. 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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.