red-black-tree-node.js

/**
 * @module lib/red-black-tree-node
 * @license MIT Copyright 2015 Daniel Imms (http://www.growingwiththeweb.com)
 */
'use strict';

if (typeof exports === 'object' && typeof define !== 'function') {
  var define = function (factory) {
    factory(require, exports, module);
  };
}

define(function (require, exports, module) {
  var BinaryTreeNode = require('./binary-tree-node');

  /**
   * Creates a red-black tree node.
   *
   * @constructor
   * @param {Object} key The key of the node. If this is undefined the node will
   * be marked as a nil (black) node.
   * @param {RedBlackTreeNode} parent The parent of the node.
   */
  var RedBlackTreeNode = function (key, parent) {
    BinaryTreeNode.call(this, key, parent);

    /**
     * The color of the node.
     * @public
     */
    this.color = typeof key === 'undefined' ? 'black' : 'red';
  };

  RedBlackTreeNode.prototype = Object.create(BinaryTreeNode.prototype);

  RedBlackTreeNode.prototype.constructor = RedBlackTreeNode;

  /**
   * Gets the left child of the node, creating it as a nil (black) node if it
   * didn't exist.
   *
   * @return {RedBlackTreeNode} The left child of the node.
   */
  RedBlackTreeNode.prototype.getLeft = function () {
    if (!this.left) {
      this.left = new RedBlackTreeNode(undefined, this);
    }
    return this.left;
  };

  /**
   * Gets the right child of the node, creating it as a nil (black) node if it
   * didn't exist.
   *
   * @return {RedBlackTreeNode} The right child of the node.
   */
  RedBlackTreeNode.prototype.getRight = function () {
    if (!this.right) {
      this.right = new RedBlackTreeNode(undefined, this);
    }
    return this.right;
  };

  /**
   * @return Whether the node is a nil (black) node.
   */
  RedBlackTreeNode.prototype.isNilNode = function () {
    return typeof this.key === 'undefined';
  };

  module.exports = RedBlackTreeNode;
});