Simple implementation of a splay tree.

SplayTree.js

'use strict';

const zig = tree => {
  const newTree = tree.l,
    parent = (newTree.p = tree.p);
  if (parent) {
    if (parent.l === tree) parent.l = newTree;
    else parent.r = newTree;
  }
  tree.p = newTree;
  const child = (tree.l = newTree.r);
  if (child) child.p = tree;
  newTree.r = tree;
  return newTree;
};

const zag = tree => {
  const newTree = tree.r,
    parent = (newTree.p = tree.p);
  if (parent) {
    if (parent.l === tree) parent.l = newTree;
    else parent.r = newTree;
  }
  tree.p = newTree;
  const child = (tree.r = newTree.l);
  if (child) child.p = tree;
  newTree.l = tree;
  return newTree;
};

const splay = node => {
  while (node.p) {
    if (!node.p.p) {
      node.p.l === node ? zig(node.p) : zag(node.p);
    } else if (node.p.l === node && node.p.p.l === node.p) {
      zig(node.p.p);
      zig(node.p);
    } else if (node.p.r === node && node.p.p.r === node.p) {
      zag(node.p.p);
      zag(node.p);
    } else if (node.p.l === node && node.p.p.r === node.p) {
      zig(node.p);
      zag(node.p);
    } else {
      zag(node.p);
      zig(node.p);
    }
  }
  return node;
};

const count = tree => (tree ? count(tree.l) + count(tree.r) + 1 : 0);

class SplayTreeNode {
  constructor(value) {
    this.l = this.r = this.p = null;
    this.value = value;
  }
  getMin() {
    let z = this;
    while (z.l) z = z.l;
    return z;
  }
  getMax() {
    let z = this;
    while (z.r) z = z.r;
    return z;
  }
}

class SplayTree {
  constructor(less = (a, b) => a < b) {
    this.less = less;
    this.root = null;
    this.size = 0;
  }
  get isEmpty() {
    return !this.root;
  }
  get length() {
    return this.size;
  }
  getMin() {
    return this.root.getMin();
  }
  getMax() {
    return this.root.getMax();
  }
  find(value) {
    for (let z = this.root; z; ) {
      if (this.less(z.value, value)) z = z.r;
      else if (this.less(value, z.value)) z = z.l;
      else return z;
    }
    return null;
  }
  promote(value) {
    const z = this.find(value);
    if (z) {
      this.root = splay(z);
    }
    return z;
  }
  splay(node) {
    this.root = splay(node);
    return this;
  }
  insert(value) {
    let z = this.root,
      parent = null;
    while (z) {
      parent = z;
      if (this.less(z.value, value)) z = z.r;
      else if (this.less(value, z.value)) z = z.l;
      else break;
    }
    if (!z) {
      z = new SplayTreeNode(value);
      z.p = parent;
      if (parent) {
        if (this.less(parent.value, value)) parent.r = z;
        else parent.l = z;
      }
      ++this.size;
    }
    this.root = splay(z);
    return this;
  }
  remove(value) {
    const z = this.find(value);
    if (!z) return this;

    splay(z);
    this.root = null;

    let maxNode = null;
    if (z.l) {
      z.l.p = null;
      maxNode = z.l.getMax();
      this.root = splay(maxNode);
    }
    if (z.r) {
      if (maxNode) maxNode.r = z.r;
      else this.root = z.r;
      z.r.p = maxNode;
    }

    --this.size;

    return this;
  }
  splitMaxTree(value) {
    if (!this.root) return new SplayTree(this.less);
    let z = this.root,
      parent = null,
      right;
    while (z) {
      parent = z;
      if (this.less(z.value, value)) {
        z = z.r;
        right = true;
      } else if (this.less(value.z.value)) {
        z = z.l;
        right = false;
      } else break;
    }
    this.root = splay(z || parent);

    const newTree = new SplayTree(this.less);
    if (z || right) {
      newTree.root = this.root.r;
      if (newTree.root) {
        newTree.root.p = null;
        newTree.size = count(newTree.root);
        this.root.r = null;
        this.size -= newTree.size;
      }
    } else {
      newTree.root = this.root;
      newTree.size = this.size;
      this.root = this.root.l;
      if (this.root) {
        this.root.p = null;
        this.size = count(this.root);
        newTree.root.l = null;
        newTree.size -= this.size;
      }
    }
    return newTree;
  }
  [Symbol.iterator]() {
    let current = this.root ? this.root.getMin() : null;
    return {
      next: () => {
        if (!current) return {done: true};
        const last = current;
        if (current.r) {
          current = current.r.getMin();
        } else {
          for (;;) {
            const parent = current.p;
            if (!parent) {
              current = null;
              break;
            }
            if (parent.l === current) {
              current = parent;
              break;
            }
            current = parent;
          }
        }
        return {value: last.value};
      }
    };
  }
  getReverseIterable() {
    return {
      [Symbol.iterator]: () => {
        let current = this.root ? this.root.getMax() : null;
        return {
          next: () => {
            if (!current) return {done: true};
            const last = current;
            if (current.l) {
              current = current.l.getMax();
            } else {
              for (;;) {
                const parent = current.p;
                if (!parent) {
                  current = null;
                  break;
                }
                if (parent.r === current) {
                  current = parent;
                  break;
                }
                current = parent;
              }
            }
            return {value: last.value};
          }
        };
      }
    };
  }
  static from(values, less) {
    const tree = new SplayTree(less);
    for (const value of values) {
      tree.insert(value);
    }
    return tree;
  }
}

module.exports = SplayTree;