2
$\begingroup$

I am working on some binary-search-tree research and was surprised to find no mention of an algorithm to join two Scapegoat Trees. This is where two trees $L$ and $R$ are joined to create a single tree $T$, given that all values in $L$ are less than all values in $R$ and that all values are unique.

For this problem, the maximum height of a tree is $2\times\lfloor{\log_2(n)\rfloor}+1$ where $n$ is the total number of nodes in the tree and height is the number of nodes along the longest path (maximum depth + 1).

I have tried some ideas but none have passed the height invariant checks so far. Does anyone know of a resource that explores this idea, or can provide a reasonable approach for this problem? You can assume that every node is annotated with its size to make things easier.

Can this be done in $O(log(n))$ without exceeding the height bound?

One approach might be to use a simple BST join (remove max of $L$ or min of $R$ to be the root) and have the balance restored over the next few insertions, but that means the height upper-bound is not always guaranteed, especially after multiple joins.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ It would not hurt to find sketches of approaches/ideas you rejected included above. $\endgroup$
    – greybeard
    Commented Oct 20, 2021 at 5:25
  • $\begingroup$ @greybeard some ideas I have tried: basic join based on tree size; basic join with median partitioning on the way back up to the root; descend until subtree of L is in balance with R, then proceed with simple join, also with median partitioning along the spine back up to the root. None of these work because the max height might be in the left subtree of L. I think it's a dead-end to think of this in terms of size. $\endgroup$
    – rtheunissen
    Commented Oct 20, 2021 at 16:37
  • $\begingroup$ @greybeard I've also considered stitching together the trees in the same way randomized search trees (rbst, treap, zip tree) are joined, with a merge path choosing from either L or R top-down until either L or R is nil. The decision is whether to choose from L or R - based on subtree size? $\endgroup$
    – rtheunissen
    Commented Oct 20, 2021 at 17:18
  • $\begingroup$ My height upper-bound on the entire tree is 2 * floor(log2(n)) + 1 $\endgroup$
    – rtheunissen
    Commented Oct 20, 2021 at 17:36

1 Answer 1

Reset to default
1
$\begingroup$

What I remember of more formal/theoretical discussion of (somewhat "basic") trees does not keep extra information about a whole tree beyond the regular information in the root node.
Seeing scapegoat trees keeping the size, anyway, and using a balance limit on trees rather than on nodes, I mused about keeping height, too. (Neither helping split…)

I figured the most simple idea you rejected was finding the rightmost node $rL \in L$ and the leftmost node $lR \in R$ (neither of which needs to be a leaf) and "rotating" the deeper to become the common root.
Guess: The height of the joint tree is one larger than the max. height of $L$, $R$ more likely than not.
And repeated joins keep increasing height.

If you knew the heights, the root of the higher (lighter to break ties) would be the joint root, with the "inner" child replaced by a join with the other tree by the previously sketched method.
Problems:
• analysis promises to be a PITA
• no(?) way to know the new height - you could keep upper (and lower) limits
 much the same way scapegoat trees keep max_size to provide for deletions

I'm afraid that at the end of the day, you are joining
- one of the original trees (the shape of which you do know something about) with
- a tree you know nothing about

One viable heuristic might be

  • set estimated size to the size of the bigger tree,
    candidate to its root
  • while estimated size is bigger than the size of the smaller tree
    and candidate has a child closer to the gap,
      • set candidate to that child
      • halve estimated size
  • now, make candidate a child of the node closest to the gap in the smaller tree
    and put the root thereof in the place candidate was in
Improve this answer
$\endgroup$
14
  • $\begingroup$ "I mused about keeping height, too" is what I was thinking too, to keep a height-upper bound similarly to the size, also reset when the entire tree is rebuilt on delete. The decision to remove the max of L or the min of R is then based on which tree has the greater height upper-bound. I have no tested this theory yet. "Analysis promises to be a PITA", at the moment I'm only interested in practical correctness. If all invariants are met throughout random and fixed distribution testing, the formal proof can follow in time. I'll try tracking a height upper-bound. Thank you for this response. $\endgroup$
    – rtheunissen
    Commented Oct 20, 2021 at 16:34
  • $\begingroup$ Even when knowing the exact height, the strategy to join the inner child of the higher tree does not always work. I've sketched a quick example where the solution is to simply "append" R to L. pastebin.com/uy4aeHvS $\endgroup$
    – rtheunissen
    Commented Oct 20, 2021 at 18:32
  • $\begingroup$ In the example above, if you instead try to join R and L, where R then has the greater height, the resulting height is 8 because removing the min of R to be the joining node does not reduce the height of that subtree, which ultimately exceeds the height bound. See pastebin.com/4cnCTsRn I think this is on the right track though. $\endgroup$
    – rtheunissen
    Commented Oct 20, 2021 at 19:07
  • 1
    $\begingroup$ we know some things about both trees we know some about $L$ and $R$. We choose a new root (wait - if sizes are close, we can use one of "the gap nodes" as the new root with $L$ and $R$ as children with good results - special case). The (all too?) obvious choice for disparate sizes is picking the root of the bigger tree, leaving a join between the smaller tree and one of the bigger one's sub-trees: That's what I was calling end of the day, and I know nothing about that subtree (for $alpha$ sufficiently close to one). $\endgroup$
    – greybeard
    Commented Oct 22, 2021 at 22:11
  • 1
    $\begingroup$ I'll run some brute-force simulations … way to go. For trees too big to wait for brute force results, you may want to do pseudorandom samples. $\endgroup$
    – greybeard
    Commented Oct 22, 2021 at 22:12

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.