• remove unnecessary parameters to helper functions • use built-in root adjustment of the rotate functions • swap parameters of the rotation functions, to pass the tree first Signed-off-by: Matej Focko <mfocko@redhat.com>
181 lines
4.9 KiB
JavaScript
181 lines
4.9 KiB
JavaScript
function balanceFactor(node) {
|
|
if (!node) {
|
|
return 0;
|
|
}
|
|
|
|
let [left, right] = [nodeRank(node.left), nodeRank(node.right)];
|
|
return right - left;
|
|
}
|
|
|
|
function updateRank(node) {
|
|
let [left, right] = [nodeRank(node.left), nodeRank(node.right)];
|
|
node.rank = 1 + Math.max(left, right);
|
|
}
|
|
|
|
class AVLTree extends RankedTree {
|
|
isCorrectNode(node, recursive) {
|
|
if (!node) {
|
|
return true;
|
|
}
|
|
|
|
let differences = nodeDifferences(node).sort();
|
|
if (
|
|
(!differences.equals([1, 1]) && !differences.equals([1, 2])) ||
|
|
node.rank != 1 + Math.max(...differences)
|
|
) {
|
|
return false;
|
|
}
|
|
|
|
recursive = recursive ?? true;
|
|
return (
|
|
!recursive ||
|
|
(this.isCorrectNode(node.left) && this.isCorrectNode(node.right))
|
|
);
|
|
}
|
|
|
|
fix0Child(x, y, z, rotateLeft, rotateRight) {
|
|
let newRoot = x.parent;
|
|
|
|
if (!y || nodeDifference(y) == 2) {
|
|
newRoot = rotateRight(this, z);
|
|
this.record("Fixing 0-child by single rotation: by z", z, newRoot);
|
|
|
|
z.demote();
|
|
this.record("Fixing 0-child by single rotation: demoting z", z);
|
|
} else if (nodeDifference(y) == 1) {
|
|
let intermediateRoot = rotateLeft(this, x);
|
|
this.record(
|
|
"Fixing 0-child by double-rotation: first rotation by x",
|
|
x,
|
|
intermediateRoot
|
|
);
|
|
|
|
newRoot = rotateRight(this, z);
|
|
this.record(
|
|
"Fixing 0-child by double-rotation: second rotation by z",
|
|
z,
|
|
newRoot
|
|
);
|
|
|
|
y.promote();
|
|
this.record("Fixing 0-child by double-rotation: promoting y", y);
|
|
|
|
x.demote();
|
|
this.record("Fixing 0-child by double-rotation: demoting x", x);
|
|
|
|
z.demote();
|
|
this.record("Fixing 0-child by double-rotation: demoting z", z);
|
|
}
|
|
}
|
|
|
|
insertRebalance(x) {
|
|
let diffs = nodeDifferences(x.parent).sort();
|
|
while (x.parent && diffs.equals([0, 1])) {
|
|
x.parent.promote();
|
|
this.record(
|
|
"Insertion rebalance: promoting (0, 1) parent",
|
|
x.parent
|
|
);
|
|
|
|
x = x.parent;
|
|
diffs = nodeDifferences(x.parent).sort();
|
|
}
|
|
|
|
if (!x.parent) {
|
|
return;
|
|
}
|
|
|
|
let rankDifference = nodeDifference(x);
|
|
if (rankDifference != 0) {
|
|
return;
|
|
}
|
|
|
|
let xParent = x.parent;
|
|
|
|
if (rankDifference == 0 && x.parent.left === x) {
|
|
this.fix0Child(x, x.right, xParent, rotateLeft, rotateRight);
|
|
} else if (rankDifference == 0 && x.parent.right === x) {
|
|
this.fix0Child(x, x.left, xParent, rotateRight, rotateLeft);
|
|
}
|
|
}
|
|
|
|
deleteRotate(x, y, leaning, rotateLeft, rotateRight) {
|
|
let newRoot = x;
|
|
|
|
let factor = balanceFactor(y);
|
|
switch (factor) {
|
|
case 0:
|
|
case leaning:
|
|
newRoot = rotateLeft(this, x);
|
|
break;
|
|
default:
|
|
let intermediateRoot = rotateRight(this, y);
|
|
this.record(
|
|
"AVL deletion, fixing by double-rotation: by y",
|
|
y,
|
|
intermediateRoot
|
|
);
|
|
|
|
newRoot = rotateLeft(this, x);
|
|
break;
|
|
}
|
|
this.record("AVL deletion, fixing by rotation by x", x, newRoot);
|
|
|
|
[newRoot.left, newRoot.right, newRoot]
|
|
.filter((x) => x)
|
|
.forEach((n) => {
|
|
updateRank(n);
|
|
this.record("Updating rank of nodes affected by rotations", n);
|
|
});
|
|
|
|
return factor != 0;
|
|
}
|
|
|
|
deleteFixup(x, parent) {
|
|
let factor = balanceFactor(x);
|
|
switch (factor) {
|
|
case 0:
|
|
updateRank(x);
|
|
this.record(
|
|
"Updating rank of node affected by the propagation of delete",
|
|
x
|
|
);
|
|
|
|
return true;
|
|
case -1:
|
|
case 1:
|
|
return false;
|
|
}
|
|
|
|
let [z, leaning, toLeft, toRight] = [
|
|
x.left,
|
|
-1,
|
|
rotateRight,
|
|
rotateLeft,
|
|
];
|
|
if (factor == 2) {
|
|
[z, leaning, toLeft, toRight] = [
|
|
x.right,
|
|
1,
|
|
rotateLeft,
|
|
rotateRight,
|
|
];
|
|
}
|
|
|
|
return this.deleteRotate(x, z, leaning, toLeft, toRight);
|
|
}
|
|
|
|
deleteRebalance(node, parent) {
|
|
if (!node && !parent) {
|
|
return;
|
|
}
|
|
|
|
if (!node) {
|
|
[node, parent] = [parent, parent.parent];
|
|
}
|
|
|
|
while (node && this.deleteFixup(node, parent)) {
|
|
[node, parent] = [parent, parent ? parent.parent : null];
|
|
}
|
|
}
|
|
}
|