A Red Black Tree

This JavaScript Reference section displays the code for an example program that shows how to create a red-black tree in JavaScript.

RedBlackTree.html

<!DOCTYPE html>
<html>
	<head>
	    <title>XoaX.net's Javascript</title>
	    <script type="text/javascript" src="RedBlackTree.js"></script>
	</head>
	<body onload="fnInitialization()">
	</body>
</html>

RedBlackTree.js

// Properties of a red-black tree
// 1. Every node is red or black
// 2. The root is black
// 3. Every null leaf is considered black
// 4. Every red node has black children
// 5. All paths from the root to the leaves has the same number of black nodes.

// The Red-Black Tree Node Constructor
function CNode(qData) {
  this.mbRed = true;
  this.mqData = qData;
  this.mqpParent = null;
  this.mqpLeft = null;
  this.mqpRight = null;

  this.mfnNextHighest = function() {
    var qpNext = null;
    if (this.mqpRight != null) { // If there is a right child,
      // the next highest is the least beneath the right child
	  var qpNext = this.mqpRight;
	  while (qpNext.mqpLeft != null) {
        qpNext = qpNext.mqpLeft;
	  }
	} else {
      // If there is no right child, the next highest is the first ancester
      // that that has a left child above this node.
      var qpChild = this;
      var qpNext = qpChild.mqpParent;
      while (qpNext != null && qpNext.mqpRight == qpChild) {
		qpNext = qpNext.mqpParent;
	  }
	}
	return qpNext;
  }
  // Replace the node in its position, using the new data
  this.mfnReplaceNode = function(qpNodeToReplace) {
	this.mbRed = qpNodeToReplace.mbRed;
	this.mqpParent = qpNodeToReplace.mqpParent;
	this.mqpLeft = qpNodeToReplace.mqpLeft;
	this.mqpRight = qpNodeToReplace.mqpRight;
    if (this.mqpParent != null) {
      // It is either a left of right child
      if (this.mqpParent.mqpLeft == qpNodeToReplace) {
        this.mqpParent.mqpLeft = this;
	  } else {
        this.mqpParent.mqpRight = this;
	  }
  	}
    if (this.mqpLeft != null) {
      this.mqpLeft.mqpParent = this;
  	}
    if (this.mqpRight != null) {
      this.mqpRight.mqpParent = this;
  	}
  }

  this.mfnProcessInOrder = function(fnProcessor) {
    if (this.mqpLeft != null) {
      this.mqpLeft.mfnProcessInOrder(fnProcessor);
  	}
  	fnProcessor(this.mqData);
    if (this.mqpRight != null) {
      this.mqpRight.mfnProcessInOrder(fnProcessor);
  	}
  }

  this.mfnDisplayNodeValue = function(sNodeName, qContainer) {
    // The name is a binary number indicating position: 0 = left, 1 = right
    // Try to get the element for this node.
    var qpDisplayElement = document.getElementById(sNodeName);
    // Check whether the element exists. If not, create the whole row.
    if (qpDisplayElement == null) {
      // The length of the string tells us how many elements are at this level.
      var iStringLength = sNodeName.length;
      // If the length is 3, there are 2^(3 - 1)  = 4 elements at this level
      var iElementCount = (1 << (iStringLength - 1));
      var dWidthPercent = ((100)/iElementCount);
      for (var i = 0; i < iElementCount; ++i) {
        var iNameValue = (iElementCount + i);
        var sName = "";
        var iBit = iElementCount;
        while (iBit > 0) {
          sName += ((iBit & iNameValue) ? "1" : "0");
          iBit >>= 1;
        }
        // Create a div
        var qDiv = document.createElement("div");
        var qAttribute = document.createAttribute("id");
        qAttribute.value = sName;
        qDiv.setAttributeNode(qAttribute);
        qDiv.style.float = "left";
        qDiv.style.width = (dWidthPercent-.25) + "%";
        qDiv.style.height = "25px";
        qDiv.style.textAlign = "center";
        qDiv.style.paddingTop = "7px";
        qDiv.style.margin = ".125%";
        // Add the element to the container.
        qContainer.appendChild(qDiv);
	  }
	  qpDisplayElement = document.getElementById(sNodeName);
	}
	qpDisplayElement.style.color = ((this.mbRed) ? "red" : "black");
	qpDisplayElement.style.backgroundColor = ((this.mbRed) ? "LightPink" : "LightGray");
	qpDisplayElement.innerHTML = this.mqData;
	// Call it on the children, if they exist
	if (this.mqpLeft != null) {
      this.mqpLeft.mfnDisplayNodeValue(sNodeName+"0", qContainer);
	}
	if (this.mqpRight != null) {
      this.mqpRight.mfnDisplayNodeValue(sNodeName+"1", qContainer);
	}
  }
}

// The Red-Black Binary Search Tree Constructor
function CRedBlackTree() {
  this.mqpRoot = null;
  this.mfnRotateLeft = function(qpNode) {
	var qpParent		       = qpNode.mqpParent;
	var qpNewTop		       = qpNode.mqpRight;
	qpNode.mqpRight            = qpNewTop.mqpLeft;
	if (qpNewTop.mqpLeft != null) {
		qpNewTop.mqpLeft.mqpParent = qpNode;
	}
	qpNewTop.mqpParent	       = qpParent;
	// If qpNode is the root.
    if (qpParent == null) {
      this.mqpRoot = qpNewTop;
    } else {
      if (qpParent.mqpLeft == qpNode) {
        qpParent.mqpLeft = qpNewTop;
	  } else {
        qpParent.mqpRight = qpNewTop;
	  }
	}
	qpNewTop.mqpLeft = qpNode;
	qpNode.mqpParent = qpNewTop;
  }
  this.mfnRotateRight = function(qpNode) {
	var qpParent		       = qpNode.mqpParent;
	var qpNewTop		       = qpNode.mqpLeft;
	qpNode.mqpLeft             = qpNewTop.mqpRight;
	if (qpNewTop.mqpRight != null) {
		qpNewTop.mqpRight.mqpParent = qpNode;
	}
	qpNewTop.mqpParent	       = qpParent;

	// If qpNode is the root.
    if (qpParent == null) {
      this.mqpRoot = qpNewTop;
    } else {
      if (qpParent.mqpLeft == qpNode) {
        qpParent.mqpLeft = qpNewTop;
	  } else {
        qpParent.mqpRight = qpNewTop;
	  }
	}
	qpNewTop.mqpRight = qpNode;
	qpNode.mqpParent = qpNewTop;
  }

  this.mfnInsert = function(qData) {
    var qpNewNode = new CNode(qData);
    if (this.mfnIsEmpty()) {
      this.mqpRoot = qpNewNode;
      // Make the root black
      qpNewNode.mbRed = false;
	} else {
      var qpParent = null;
      var qpSearch = this.mqpRoot;
      while (qpSearch != null) {
        qpParent = qpSearch;
        if (qData < qpSearch.mqData) {
          qpSearch = qpSearch.mqpLeft;
	    } else {
          qpSearch = qpSearch.mqpRight;
		}
	  }
	  qpNewNode.mqpParent = qpParent;
	  if (qData < qpParent.mqData) {
        qpParent.mqpLeft = qpNewNode;
	  } else {
        qpParent.mqpRight = qpNewNode;
	  }
	  this.mfnFixInsert(qpNewNode);
    }
  }

  this.mfnFixInsert = function(qpNewNode){
    var qpZ = qpNewNode;
    // While red inserted Z has a red parent
    while (qpZ.mqpParent != null && qpZ.mqpParent.mbRed) {
      // If the parent is a left child
      if (qpZ.mqpParent == qpZ.mqpParent.mqpParent.mqpLeft) {
        var qpY = qpZ.mqpParent.mqpParent.mqpRight;
        if (qpY != null && qpY.mbRed) {
          // Case 1 -
          qpZ.mqpParent.mbRed = false;
          qpY.mbRed = false;
          qpZ.mqpParent.mqpParent.mbRed = true;
          qpZ = qpZ.mqpParent.mqpParent;
        } else if (qpZ == qpZ.mqpParent.mqpRight) {
          // Case 2
          qpZ = qpZ.mqpParent;
          this.mfnRotateLeft(qpZ);
        } else {
          // Case 3
          qpZ.mqpParent.mbRed = false;
          qpZ.mqpParent.mqpParent.mbRed = true;
          this.mfnRotateRight(qpZ.mqpParent.mqpParent);
        }
	  } else { // If the parent is a right child
        var qpY = qpZ.mqpParent.mqpParent.mqpLeft;
        if (qpY != null && qpY.mbRed) {
          // Case 1
          qpZ.mqpParent.mbRed = false;
          qpY.mbRed = false;
          qpZ.mqpParent.mqpParent.mbRed = true;
          qpZ = qpZ.mqpParent.mqpParent;
        } else if (qpZ == qpZ.mqpParent.mqpLeft) {
          // Case 2
          qpZ = qpZ.mqpParent;
          this.mfnRotateRight(qpZ);
        } else {
          // Case 3
          qpZ.mqpParent.mbRed = false;
          qpZ.mqpParent.mqpParent.mbRed = true;
          this.mfnRotateLeft(qpZ.mqpParent.mqpParent);
        }
	  }
	}
	// This may never be needed
	this.mqpRoot.mbRed = false;
  }
  this.mfnDelete = function(qpNode) {
    var qpY = null;
    if (qpNode.mqpLeft == null || qpNode.mqpRight == null) {
      qpY = qpNode;
    } else {
      // We really only need this for right children
      qpY = qpNode.mfnNextHighest();
    }
    var qpX = ((qpY.mqpLeft != null) ? qpY.mqpLeft : qpY.mqpRight);
    if (qpX != null) {
      qpX.mqpParent = qpY.mqpParent;
    }
    // This only happens if we are deleting the root
    if (qpY.mqpParent == null) {
      this.mqpRoot = qpX;
	} else if (qpY == qpY.mqpParent.mqpLeft) {
      qpY.mqpParent.mqpLeft = qpX;
	} else {
      qpY.mqpParent.mqpRight = qpX;
	}
	// If we are deleting a black node
	if (!qpY.mbRed && !(qpY.mqpParent == null && qpX == null)) {
	//if (!qpY.mbRed) {
      this.mfnFixBlackDelete(qpX, qpY.mqpParent);
	}
    if (qpY != qpNode) {
		if (this.mqpRoot == qpNode) {
			this.mqpRoot = qpY;
		}
      // This will copy everything except the data
      qpY.mfnReplaceNode(qpNode);
      // Now qpNode is deleted.
	}
  }
  this.mfnFixBlackDelete = function(qpChildOfDelete, qpParentOfDelete){
    var qpX = qpChildOfDelete;
    var qpParent = qpParentOfDelete;
    while (qpX == null || qpX != this.mqpRoot && !qpX.mbRed) {
      if (qpX == qpParent.mqpLeft) {
        var qpW = qpParent.mqpRight;
        if (qpW.mbRed) {
          qpW.mbRed = false;
          qpParent.mbRed = true;
          this.mfnRotateLeft(qpParent);
          qpW = qpParent.mqpRight;
		}
		if ((qpW.mqpLeft == null || !qpW.mqpLeft.mbRed) &&
		    (qpW.mqpRight == null || !qpW.mqpRight.mbRed)) {
          qpW.mbRed = true;
          qpX = qpParent;
          qpParent = qpX.mqpParent;
		} else {
          if (qpW.mqpRight == null || !qpW.mqpRight.mbRed) {
            qpW.mqpLeft.mbRed = false;
            qpW.mbRed = true;
            this.mfnRotateRight(qpW);
            qpW = qpParent.mqpRight;
		  }
		  qpW.mbRed = qpParent.mbRed;
		  qpParent.mbRed = false;
		  qpW.mqpRight.mbRed = false;
		  this.mfnRotateLeft(qpParent);
		  qpX = this.mqpRoot;
		}
	  } else {
        var qpW = qpParent.mqpLeft;
        if (qpW.mbRed) {
          qpW.mbRed = false;
          qpParent.mbRed = true;
          this.mfnRotateRight(qpParent);
          qpW = qpParent.mqpLeft;
		}
		if ((qpW.mqpLeft == null || !qpW.mqpLeft.mbRed) &&
		    (qpW.mqpRight == null || !qpW.mqpRight.mbRed)) {
          qpW.mbRed = true;
          qpX = qpParent;
          qpParent = qpX.mqpParent;
		} else {
          if (qpW.mqpLeft == null || !qpW.mqpLeft.mbRed) {
            qpW.mqpRight.mbRed = false;
            qpW.mbRed = true;
            this.mfnRotateLeft(qpW);
            qpW = qpParent.mqpLeft;
		  }
		  qpW.mbRed = qpParent.mbRed;
		  qpParent.mbRed = false;
		  qpW.mqpLeft.mbRed = false;
		  this.mfnRotateRight(qpParent);
		  qpX = this.mqpRoot;
		}
	  }
	}
	qpX.mbRed = false;
  }
  this.mfDisplay = function(qContainerElement) {
    // The position can be determined by this string
    var sRootNodeName = "1";
    if (this.mqpRoot != null) {
    this.mqpRoot.mfnDisplayNodeValue(sRootNodeName, qContainerElement);
    }
  }
  this.mfFind = function(qData) {
    var qpCurr = this.mqpRoot;
    while (qpCurr != null) {
      if (qData < qpCurr.mqData) {
        qpCurr = qpCurr.mqpLeft;
      } else if(qData > qpCurr.mqData) {
        qpCurr = qpCurr.mqpRight;
      } else {
        return qpCurr;
      }
	}
	return null;
  }
  this.mfProcessInOrder = function(fnProcessor) {
	if (!this.mfnIsEmpty()) {
      this.mqpRoot.mfnProcessInOrder(fnProcessor);
    }
  }
  this.mfnIsEmpty = function() {
    return (this.mqpRoot == null);
  }
}


function fnPrint(qData) {
  var qpPrint = document.getElementById("idOutput");
  qpPrint.innerHTML += qData + " ";
}

function fnInitialization() {
  var qRedBlackTree = new CRedBlackTree();

  // Insert 32 random values
  for (var i = 0; i < 32; ++i) {
	  qRedBlackTree.mfnInsert(Math.round((Math.random()*99)));
  }

  var qDisplayDiv = document.createElement("div");
  qDisplayDiv.style.width = "800px";
  qDisplayDiv.style.height = "250px";
  qDisplayDiv.style.border = "black 1px solid";
  qDisplayDiv.style.backgroundColor = "WhiteSmoke";
  document.body.appendChild(qDisplayDiv);

  // Delete 30 random values, which may or may not be present
  for (var i = 0; i < 30; ++i) {
    var qpDeleteNode = qRedBlackTree.mfFind(Math.round((Math.random()*99)));
    if (qpDeleteNode != null) {
      qRedBlackTree.mfnDelete(qpDeleteNode);
    }
  }
  qRedBlackTree.mfDisplay(qDisplayDiv);

}