Binary Search Tree optimizations

tshemsedinov · tshemsedinov · commit 7f4bb0b7088f · 2018-03-17T21:28:45.000+02:00
diff --git a/JavaScript/6-bst-opt.js b/JavaScript/6-bst-opt.js
@@ -0,0 +1,33 @@
+'use strict';
+
+// Binary Search Tree
+
+const tree = (data = null, left = null, right = null) => [data, left, right];
+tree.data = (node, data = node[0]) => (node[0] = data, data);
+tree.left = (node, data) => (data ? node[1] = tree(data) : node[1]);
+tree.right = (node, data) => (data ? node[2] = tree(data) : node[2]);
+
+tree.insert = (node, data) => {
+  const i = data < node[0] ? 1 : 2;
+  if (node[i] === null) node[i] = tree(data);
+  else tree.insert(node[i], data);
+};
+
+tree.search = (node, data) => {
+  const value = node[0];
+  if (data === value) return node;
+  const i = data < value ? 1 : 2;
+  return tree.search(node[i], data);
+};
+
+// Usage
+
+const root = tree(5);
+tree.insert(root, 7);
+tree.insert(root, 9);
+tree.insert(root, 2);
+tree.insert(root, 3);
+tree.insert(root, 1);
+
+const node = tree.search(root, 2);
+console.dir(node, { depth: 3 });
diff --git a/JavaScript/7-bst-over.js b/JavaScript/7-bst-over.js
@@ -0,0 +1,28 @@
+'use strict';
+
+// Binary Search Tree
+
+const tree = (data = null, left = null, right = null) => [data, left, right];
+tree.data = (node, data = node[0]) => (node[0] = data, data);
+tree.left = (node, data) => (data ? node[1] = tree(data) : node[1]);
+tree.right = (node, data) => (data ? node[2] = tree(data) : node[2]);
+
+tree.insert = (node, data, i = data < node[0] ? 1 : 2) => (
+  node[i] === null ? node[i] = tree(data) : tree.insert(node[i], data)
+);
+
+tree.search = (node, data, value = node[0]) => (
+  data === value ? node : tree.search(node[data < value ? 1 : 2], data)
+);
+
+// Usage
+
+const root = tree(5);
+tree.insert(root, 7);
+tree.insert(root, 9);
+tree.insert(root, 2);
+tree.insert(root, 3);
+tree.insert(root, 1);
+
+const node = tree.search(root, 2);
+console.dir(node, { depth: 3 });
