Make it possible to use objects as a values for binary search tree nodes.

trekhleb · trekhleb · commit 797a6f28a339 · 2018-05-30T07:43:39.000+03:00
diff --git a/src/data-structures/tree/binary-search-tree/BinarySearchTree.js b/src/data-structures/tree/binary-search-tree/BinarySearchTree.js
@@ -5,18 +5,31 @@ export default class BinarySearchTree {
     this.root = new BinarySearchTreeNode();
   }
 
+  /**
+   * @param {*} value
+   */
   insert(value) {
     this.root.insert(value);
   }
 
+  /**
+   * @param {*} value
+   * @return {boolean}
+   */
   contains(value) {
     return this.root.contains(value);
   }
 
+  /**
+   * @param {*} value
+   */
   remove(value) {
     return this.root.remove(value);
   }
 
+  /**
+   * @return {string}
+   */
   toString() {
     return this.root.toString();
   }
diff --git a/src/data-structures/tree/binary-search-tree/BinarySearchTreeNode.js b/src/data-structures/tree/binary-search-tree/BinarySearchTreeNode.js
@@ -1,20 +1,37 @@
 import BinaryTreeNode from '../BinaryTreeNode';
+import Comparator from '../../../utils/comparator/Comparator';
 
 export default class BinarySearchTreeNode extends BinaryTreeNode {
+  /**
+   * @param {*} value
+   * @param {BinaryTreeNode} parent
+   * @param {function} compareFunction
+   */
+  constructor(value = null, parent = null, compareFunction = undefined) {
+    super(value, parent);
+
+    // This comparator is used to compare node values with each other.
+    this.nodeValueComparator = new Comparator(compareFunction);
+  }
+
+  /**
+   * @param {*} value
+   * @return {BinarySearchTreeNode}
+   */
   insert(value) {
-    if (this.value === null) {
+    if (this.nodeValueComparator.equal(this.value, null)) {
       this.value = value;
       return this;
     }
 
-    if (value < this.value) {
+    if (this.nodeValueComparator.lessThan(value, this.value)) {
       // Insert to the left.
       if (this.left) {
         this.left.insert(value);
       } else {
         this.setLeft(new BinarySearchTreeNode(value));
       }
-    } else if (value > this.value) {
+    } else if (this.nodeValueComparator.greaterThan(value, this.value)) {
       // Insert to the right.
       if (this.right) {
         this.right.insert(value);
@@ -26,27 +43,38 @@ export default class BinarySearchTreeNode extends BinaryTreeNode {
     return this;
   }
 
+  /**
+   * @param {*} value
+   * @return {BinarySearchTreeNode}
+   */
   find(value) {
     // Check the root.
-    if (this.value === value) {
+    if (this.nodeValueComparator.equal(this.value, value)) {
       return this;
     }
 
-    if (value < this.value && this.left) {
+    if (this.nodeValueComparator.lessThan(value, this.value) && this.left) {
       // Check left nodes.
       return this.left.find(value);
-    } else if (value > this.value && this.right) {
+    } else if (this.nodeValueComparator.greaterThan(value, this.value) && this.right) {
       // Check right nodes.
       return this.right.find(value);
     }
 
     return null;
   }
 
+  /**
+   * @param {*} value
+   * @return {boolean}
+   */
   contains(value) {
     return !!this.find(value);
   }
 
+  /**
+   * @param {*} value
+   */
   remove(value) {
     const nodeToRemove = this.find(value);
 
@@ -65,7 +93,7 @@ export default class BinarySearchTreeNode extends BinaryTreeNode {
       // Find the next biggest value (minimum value in the right branch)
       // and replace current value node with that next biggest value.
       const nextBiggerNode = nodeToRemove.right.findMin();
-      if (nextBiggerNode !== nodeToRemove.right) {
+      if (!this.nodeComparator.equal(nextBiggerNode, nodeToRemove.right)) {
         this.remove(nextBiggerNode.value);
         nodeToRemove.value = nextBiggerNode.value;
       } else {
@@ -85,6 +113,9 @@ export default class BinarySearchTreeNode extends BinaryTreeNode {
     }
   }
 
+  /**
+   * @return {BinarySearchTreeNode}
+   */
   findMin() {
     if (!this.left) {
       return this;
diff --git a/src/data-structures/tree/binary-search-tree/__test__/BinarySearchTreeNode.test.js b/src/data-structures/tree/binary-search-tree/__test__/BinarySearchTreeNode.test.js
@@ -171,4 +171,35 @@ describe('BinarySearchTreeNode', () => {
 
     expect(removeNotExistingElementFromTree).toThrow();
   });
+
+  it('should be possible to use objects as node values', () => {
+    const nodeValueComparatorCallback = (a, b) => {
+      const normalizedA = a || { value: null };
+      const normalizedB = b || { value: null };
+
+      if (normalizedA.value === normalizedB.value) {
+        return 0;
+      }
+
+      return normalizedA.value < normalizedB.value ? -1 : 1;
+    };
+
+    const obj1 = { key: 'obj1', value: 1, toString: () => 'obj1' };
+    const obj2 = { key: 'obj2', value: 2, toString: () => 'obj2' };
+    const obj3 = { key: 'obj3', value: 3, toString: () => 'obj3' };
+
+    const bstNode = new BinarySearchTreeNode(obj2, null, nodeValueComparatorCallback);
+    bstNode.insert(obj1);
+
+    expect(bstNode.toString()).toBe('obj1,obj2');
+    expect(bstNode.contains(obj1)).toBeTruthy();
+    expect(bstNode.contains(obj3)).toBeFalsy();
+
+    bstNode.insert(obj3);
+
+    expect(bstNode.toString()).toBe('obj1,obj2,obj3');
+    expect(bstNode.contains(obj3)).toBeTruthy();
+
+    expect(bstNode.findMin().value).toEqual(obj1);
+  });
 });

Original file line number	Diff line number	Diff line change
`@@ -5,18 +5,31 @@ export default class BinarySearchTree {`
`5`	`5`	`this.root = new BinarySearchTreeNode();`
`6`	`6`	`}`
`7`	`7`
	`8`	`+ /**`
	`9`	`+ * @param {*} value`
	`10`	`+ */`
`8`	`11`	`insert(value) {`
`9`	`12`	`this.root.insert(value);`
`10`	`13`	`}`
`11`	`14`
	`15`	`+ /**`
	`16`	`+ * @param {*} value`
	`17`	`+ * @return {boolean}`
	`18`	`+ */`
`12`	`19`	`contains(value) {`
`13`	`20`	`return this.root.contains(value);`
`14`	`21`	`}`
`15`	`22`
	`23`	`+ /**`
	`24`	`+ * @param {*} value`
	`25`	`+ */`
`16`	`26`	`remove(value) {`
`17`	`27`	`return this.root.remove(value);`
`18`	`28`	`}`
`19`	`29`
	`30`	`+ /**`
	`31`	`+ * @return {string}`
	`32`	`+ */`
`20`	`33`	`toString() {`
`21`	`34`	`return this.root.toString();`
`22`	`35`	`}`