Fixes in the rotations

mgechev · mgechev · commit 41f5d65a370e · 2014-05-17T16:52:02.000-07:00
diff --git a/src/data-structures/red-black-tree.js b/src/data-structures/red-black-tree.js
@@ -2,23 +2,35 @@
 
   'use strict';
 
-  function Node(key, value, left, right, isRed) {
+  var Colors = {
+    RED: 0,
+    BLACK: 1
+  };
+
+  global.Colors = Colors;
+
+
+  function Node(key, value, left, right, color) {
     this._key = key;
     this._left = left;
     this._right = right;
     this._value = value;
-    this._isRed = isRed;
+    this._color = color;
   }
 
   Node.prototype.isRed = function () {
-    return !!this._isRed;
+    return this._color === Colors.RED;
   };
 
   Node.prototype.flipColor = function () {
-    this._isRed = !this._isRed;
+    if (this._color === Colors.RED) {
+      this._color = Colors.BLACK;
+    } else {
+      this._color = Colors.RED;
+    }
   };
 
-  'key value left right'
+  'key value left right color'
   .split(' ')
   .forEach(function (key) {
     var valueName = key.substr(0, 1).toUpperCase() + key.substr(1, key.length);
@@ -39,7 +51,7 @@
 
   RBTree.prototype.put = function (key, value) {
     this._root = this._put(key, value, this._root);
-    this._root.flipColor();
+    this._root.setColor(Colors.BLACK);
   };
 
   RBTree.prototype.isRed = function (node) {
@@ -52,7 +64,7 @@
   RBTree.prototype._put = function (key, value, node) {
     var newRoot = node;
     if (node === null) {
-      return new Node(key, value, null, null, true);
+      return new Node(key, value, null, null, Colors.RED);
     }
     if (node.getKey() > key) {
       node._left = this._put(key, value, node._left);
@@ -82,6 +94,8 @@
       var temp = x._left;
       node.setRight(temp);
       x._left = node;
+      x.setColor(node.getColor());
+      node.setColor(Colors.RED);
     }
     return x;
   };
@@ -92,6 +106,8 @@
       var temp = x._right;
       node._left = temp;
       x._right = node;
+      x.setColor(node.getColor());
+      node.setColor(Colors.RED);
     }
     return x;
   };
diff --git a/test/data-structures/red-black-tree.spec.js b/test/data-structures/red-black-tree.spec.js
@@ -2,7 +2,8 @@
 
 var mod = require('../../src/data-structures/red-black-tree.js'),
     Node = mod.Node,
-    RBTree = mod.RBTree;
+    RBTree = mod.RBTree,
+    Colors = mod.Colors;
 
 describe('Node', function () {
 
@@ -11,15 +12,12 @@ describe('Node', function () {
   });
 
   it('should set all properties via the constructor', function () {
-    var node = new Node('key', 'value', 1, 2, true);
+    var node = new Node('key', 'value', 1, 2, Colors.RED);
     expect(node.getKey()).toBe('key');
     expect(node.getLeft()).toBe(1);
     expect(node.getRight()).toBe(2);
     expect(node.getValue()).toBe('value');
     expect(node.isRed()).toBeTruthy();
-    node = new Node('key', 'value', null, null, undefined);
-    //if we set isRed to falcy it should be turned to red
-    expect(node.isRed()).toBe(false);
   });
 
   describe('Node flipColor', function () {
@@ -53,6 +51,7 @@ describe('RBTree', function () {
       expect(tree._root.getKey()).toBe('foo');
       expect(tree._root.getValue()).toBe('bar');
     });
+
     it('should be able to insert a node in 1 level tree', function () {
       var tree = new RBTree();
       tree.put(1, 'bar');
@@ -62,7 +61,16 @@ describe('RBTree', function () {
       tree.put(2, 'baz');
       expect(tree._root._right).not.toBeNull();
       expect(tree._root._right._isRed).toBeFalsy();
+
+      tree = new RBTree();
+      tree.put(1, 'bar');
+      tree.put(2, 'bar');
+      tree.put(3, 'bar');
+      tree.put(4, 'bar');
+      console.log(tree._root);
+//      expect(tree._root._right._isRed).toBeFalsy();
     });
+
   });
 
 });
