src/swap/swap_non_adjacent.js

import assert from 'assert';
import Node from '../types/Node.js';
import swap_color from './swap_color.js';
 
/**
 * Swap pointers and colors of two NON-ADJACENT nodes with three constraints:
 *   - B is not the root
 *   - B is its parent right child
 *   - B's right child is a leaf
 *
 * NOTE: These three constraints are implied because B is A's in-subtree
 * predecessor without being A's left child.
 *
 *         p       q             q           p
 *         |        \             \          |
 *        -A        +B            +A        -B
 *        / \       / \           / \       / \
 *       u   v     x   -     ->  x   -     u   v
 *
 * @param {Node} A - The first node.
 * @param {Node} B - The second node.
 */
 
const swap_non_adjacent = (A, B) => {
	assert(A instanceof Node);
	assert(B instanceof Node);
	const p = A.parent;
	const u = A.left;
	const v = A.right;
	const q = B.parent;
	const x = B.left;
	assert(B.right === null);
	assert(q !== null);
	assert(B === q.right);
 
	if (p !== null) {
		if (A === p.left) p.left = B;
		else p.right = B;
	}
 
	q.right = A;
 
	A.parent = q;
	A.left = x;
	A.right = null;
	B.parent = p;
	B.left = u;
	B.right = v;
 
	if (x !== null) x.parent = A;
	if (u !== null) u.parent = B;
	if (v !== null) v.parent = B;
 
	swap_color(A, B);
};
 
export default swap_non_adjacent;