8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.