Skip to content

Instantly share code, notes, and snippets.

@anbnyc

anbnyc/index.html

Last active July 26, 2017 17:39
Show Gist options
  • Save anbnyc/33c284a218e4ab610bc18474e18c3955 to your computer and use it in GitHub Desktop.
Save anbnyc/33c284a218e4ab610bc18474e18c3955 to your computer and use it in GitHub Desktop.
Download ZIP
Implementation of Red-Black Tree in JavaScript
Raw
index.html
<html>
<head>
<script src="https://cdnjs.cloudflare.com/ajax/libs/vis/4.18.1/vis.min.js"></script>
<script
src="https://code.jquery.com/jquery-3.1.1.min.js"
integrity="sha256-hVVnYaiADRTO2PzUGmuLJr8BLUSjGIZsDYGmIJLv2b8="
crossorigin="anonymous"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/materialize/0.98.0/js/materialize.min.js"></script>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/materialize/0.98.0/css/materialize.min.css">
<style>
#mynetwork {
height: 500px;
border: 1px solid lightgray;
color: aliceblue;
}
.container{
margin-top: 20px;
}
</style>
</head>
<body>
<div class="container">
<h2>Red-Black Tree</h2>
<div class="row">
<h6>A red-black tree has the following properties:</h6>
<p><a href="http://pages.cs.wisc.edu/~cs367-1/readings/Red-Black-Trees/">Source</a></p>
<ul>
<li>The root is black</li>
<li>The children of a red node are black</li>
<li>Every path from the root to a leaf passes through the same number of black nodes</li>
</ul>
</div>
<div class="row">
<input class="col s8" placeholder="Enter a value" id="inputarray" type="text" value="">
<span class="col s1"></span>
<button class="col s3 btn" onclick="addToTree()">Add Value To Tree</button>
</div>
<div id="mynetwork"></div>
</div>
</body>
<script src="./red-black.js"></script>
<script>
let network;
let container = document.getElementById("mynetwork");
var tree = new RedBlackTree(0);
function addToTree(){
let value = parseInt($('#inputarray')[0].value);
if(tree._root.value === 0){
tree._root.value = value;
} else {
tree.insert(value);
}
redraw();
}
function redraw(){
let data = createNodesLinks(tree._root);
destroyNetwork();
createNetwork(data);
}
function createNodesLinks(root){
var nodes = [];
var edges = [];
function traverse(node,key){
nodes.push({id: key, label: node.value, color: node.color, font: '12px arial lightgray'});
if(node.children){
if(node.children[0]){
edges.push({from:key,to:key+"0"})
traverse(node.children[0],key+"0")
}
if(node.children[1]){
edges.push({from:key,to:key+"1"})
traverse(node.children[1],key+"1")
}
}
}
traverse(root,"0");
return {nodes: nodes, edges: edges}
}
function destroyNetwork(){
if(network !== undefined){
network.destroy();
}
}
function createNetwork(data){
const options = {
layout: {
hierarchical: {
direction: "UD",
sortMethod: "directed"
}
}
};
network = new vis.Network(container, data, options);
}
</script>
</html>
Raw
red-black.js
/**
* Constructor for Red-Black Tree initializes with one node at root
* @param {Number} root
*/
function RedBlackTree(root){
this._root = new Node(root,null,false);
}
/**
* Constructor for node assigns value, parent, color, and children if not a leaf
* @param {Number} val
* @param {Node} parent
* @param {Boolean} red
*/
function Node(val,parent,red){
this.value = val;
this.parent = parent;
this.color = red ? 'red' : 'black';
if(val !== null){
this.children = [
new Node(null,this,false),
new Node(null,this,false)
];
}
}
/**
* Insert method adds new node and rebalances as needed
* @param {Number} value
*/
RedBlackTree.prototype.insert = function(value){
var tree = this;
/**
* Travels down the tree (binary search), adds new node, and calls rebalance method
* @param {Node} node
*/
function traverseAndInsert(node){
if(value < node.value){
if(node.children[0].value === null){
node.children[0] = new Node(value,node,true);
rebalance(node.children[0],node,0);
} else {
traverseAndInsert(node.children[0]);
}
} else if (value > node.value){
if(node.children[1].value === null){
node.children[1] = new Node(value,node,true);
rebalance(node.children[1],node,1);
} else {
traverseAndInsert(node.children[1]);
}
}
}
/**
*
* @param {Node} node
* @param {Node} parent
* @param {Number} nodeSide 0/1
*/
function rebalance(node,parent,nodeSide){
parent = parent || node.parent;
//if parent is null, it's the root, which can't be red
if(parent === null){
node.color = "black";
//node and parent can't both be red
} else if(node.color === "red" && parent.color === "red"){
nodeSide = nodeSide || (parent.children[0].value === node.value ? 0 : 1);
let gparent = parent.parent;
let uncleSide = gparent.children[0].value === parent.value ? 1 : 0;
let uncle = gparent.children[uncleSide];
// if parent and its sibling are both red, recolor: turn them both black
if(uncle.color === "red"){
parent.color = uncle.color = "black";
gparent.color = "red";
rebalance(gparent);
// if parent sibling is black or null, rebalance
} else if (uncle.value === null || uncle.color === "black"){
let sibSide = nodeSide === 0 ? 1 : 0;
//node and uncle are on opposite sides of their parents: rotate restructure
if(nodeSide !== uncleSide){
debugger;
let sib = parent.children[sibSide];
parent.parent = gparent.parent;
if(parent.parent === null){
tree._root = parent;
}
parent.color = "black";
gparent.parent = parent;
parent.children[uncleSide] = gparent;
gparent.color = "red";
gparent.children[nodeSide] = sib;
sib.parent = gparent;
//node and uncle are on same side of their parents: flip restructure
} else if (nodeSide === uncleSide){
node.parent = gparent.parent;
if(node.parent === null){
tree._root = node;
}
node.color = "black";
node.children[sibSide] = parent;
parent.parent = node;
node.children[nodeSide] = gparent;
gparent.parent = node;
gparent.color = "red";
gparent.children[sibSide] = new Node(null,gparent,false);
parent.children[nodeSide] = new Node(null,parent,false);
}
}
}
}
//begin the insert process at the root
traverseAndInsert(this._root);
}
/**
* Searches for node with given value and returns node if found
* @param {Number} value
*/
RedBlackTree.prototype.search = function(value){
function subtreeSearch(node){
if (node.value === null) {
return false;
} else if(node.value === value){
return node;
} else if(value < node.value) {
let left = subtreeSearch(node.children[0]);
if(left){
return left;
}
} else if(value > node.value) {
let right = subtreeSearch(node.children[1]);
if(right){
return right;
}
}
}
//begin the search at the root
return subtreeSearch(this._root);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment