Red-Black Tree in JavaScript with ES6 syntax

immutable-red-black-tree.js

class Node {
  constructor(key, value, color, left = null, right = null) {
    Object.assign(this, { key, value, color, left, right });
  }

  async insert(key, value) {
    const cmp = key < this.key ? "left" : "right";
    const child = this[cmp];
    const newChild = child === null ? new Node(key, value, true) : await child.insert(key, value);
    return newChild.color && this.color ? this.fixup(newChild, cmp) : new Node(this.key, this.value, this.color, cmp === "left" ? newChild : this.left, cmp === "right" ? newChild : this.right);
  }

  fixup(child, cmp) {
    const otherCmp = cmp === "left" ? "right" : "left";
    const sibling = this[otherCmp];
    return sibling !== null && sibling.color ? new Node(sibling.key, sibling.value, true, new Node(this.key, this.value, false, this.left, sibling.left), new Node(child.key, child.value, false, sibling.right, child.right)) : new Node(this.key, this.value, false, cmp === "left" ? child : this.left, cmp === "right" ? child : this.right);
  }
}

export class ImmutableRedBlackTree {
  constructor(root = null) {
    this.root = root;
  }

  async insert(key, value) {
    const newRoot = this.root === null ? new Node(key, value, false) : await this.root.insert(key, value);
    return new ImmutableRedBlackTree(new Node(newRoot.key, newRoot.value, false));
  }
}

// immutable-red-black-tree.test.js

import { ImmutableRedBlackTree } from './immutable-red-black-tree';

test('inserting a value creates a new tree with the correct node', async () => {
  const tree1 = new ImmutableRedBlackTree();
  const tree2 = await tree1.insert('a', 1);
  expect(tree1.root).toBe(null);
  expect(tree2.root.key).toBe('a');
  expect(tree2.root.value).toBe(1);
});

test('inserting multiple values creates a new tree with the correct nodes', async () => {
  const tree1 = new ImmutableRedBlackTree();
  const tree2 = await tree1.insert('a', 1);
  const tree3 = await tree2.insert('b', 2);
  const tree4 = await tree3.insert('c', 3);
  expect(tree1.root).toBe(null);
  expect(tree2.root.key).toBe('a');
  expect(tree3.root.key).toBe('a');
  expect(tree3.root.right.key).toBe('b');
  expect(tree4.root.key).toBe('a');
  expect(tree4.root.right.key).toBe('b');
  expect(tree4.root.right.right.key).toBe('c');
});