April 2018
Beginner to intermediate
426 pages
10h 19m
English
In the insertion algorithm, we only used the right-right and left-left rotations. The logic is the same as the AVL tree, however, since we are keeping a reference to the node's parent, we also need to update the node.parent reference to the new parent after the node is rotated.
The code for the left-left rotation (right rotation) is presented as follows (update of parent highlighted):
rotationLL(node) {
const tmp = node.left;
node.left = tmp.right;
if (tmp.right && tmp.right.key) {
tmp.right.parent = node;
}
tmp.parent = node.parent;
if (!node.parent) {
this.root = tmp;
}
else {
if (node === node.parent.left) {
node.parent.left = tmp;
}
else {
node.parent.right = tmp;
}
}
tmp.right = node;
node.parent = tmp; ...