1
$\begingroup$

From Wikipedia:

Even a degenerate tree (linked list) satisfies this condition if α=1, whereas an α=0.5 would only match almost complete binary trees.

A binary search tree that is α-weight-balanced must also be α-height-balanced, that is

height(tree) ≤ ⌊log1/α(size(tree))⌋

By contraposition, a tree that is not α-height-balanced is not α-weight-balanced.

Scapegoat trees are not guaranteed to keep α-weight-balance at all times, but are always loosely α-height-balanced in that

height(scapegoat tree) ≤ ⌊log1/α(size(tree))⌋ + 1.

Violations of this height balance condition can be detected at insertion time, and imply that a violation of the weight balance condition must exist.

From Open Data Structures (it uses a = 2/3):

To implement the add(x) operation, we first increment n and q and then use the usual algorithm for adding x to a binary search tree; we search for x and then add a new leaf u with u.x=x. At this point, we may get lucky and the depth of u might not exceed log3/2q. If so, then we leave well enough alone and don't do anything else.

Unfortunately, it will sometimes happen that depth(u)>log3/2q. In this case, we need to reduce the height.

Here's the code sample from Open Data Structures (http://opendatastructures.org/newhtml/ods/latex/scapegoat.html):

  boolean add(T x) {
        // first do basic insertion keeping track of depth
        Node<T> u = newNode(x);
        int d = addWithDepth(u);
        if (d > log32(q)) {
            // depth exceeded, find scapegoat
            Node<T> w = u.parent;
            while (3*size(w) <= 2*size(w.parent))
                w = w.parent;
            rebuild(w.parent);
        }
        return d >= 0;
    }

q is an over-estimate of the number of elements (n) in the tree so (q <= n). So in the code example, it checks whether depth is greater than

height cannot exceed log1.5(q) per the reference code.

So then we know that: log1.5(n) <= log1.5 (q) height <= log1.5 (q) (mandated by the check in the insertion code)

The following inequalities are provided:

  • q/2≤n≤q
  • log1.5(q) ≤ log1.5(2n) < log1.5(n)+2

So from the second inequality and the log product rule we can get, log1.5(q) ≤ log1.5(2) + log1.5(n) < log1.5(n) + 2, although I'm not sure whether this would be relevant.

Here's a link to Galperin 1993: http://akira.ruc.dk/~keld/teaching/algoritmedesign_f07/Artikler/03/Galperin93.pdf.

So my question is where the "+ 1" comes from for the loose height balance property of the scapegoat tree? Sorry if it's something obvious I'm not seeing...

$\endgroup$
  • $\begingroup$ log1/a, where a is between 0.5 and 1. So log1/a of (2) would be >= 1 then as the min value would be if a = 0.5 which would be 1. $\endgroup$ – smw Nov 21 '19 at 1:30
  • $\begingroup$ height <= log1/a (q) <= log1/a(2) + log1/a(n). height <= log1/a(2) + log1/a(n). Wouldn't that then imply that log1/a(2) = 1 which wouldn't be a true statement, since it could be >= 1. 1<= log1/a(2). $\endgroup$ – smw Nov 21 '19 at 1:38

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.