Skip to content

Instantly share code, notes, and snippets.

@tanzaku
Created November 29, 2016 15:45
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tanzaku/141552f7522353e0a8543cbc8669166d to your computer and use it in GitHub Desktop.
Save tanzaku/141552f7522353e0a8543cbc8669166d to your computer and use it in GitHub Desktop.
// O(|h(l) - h(r)|)
private static Node join(Node l, Node v, Node r) {
if (l == null) { return addFirst(r, v); } // O(h)
if (r == null) { return addLast(l, v); } // O(h)
int hl = height(l);
int hr = height(r);
if (hl > hr + 2) {
l.r = join(l.r, v, r);
return balance(l);
}
if (hr > hl + 2) {
r.l = join(l, v, r.l);
return balance(r);
}
// |hr - hl| <= 2 になったときに、このルートに来て再帰が止まる
v.l = l;
v.r = r;
v.update();
return v;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment