Last active
September 13, 2019 18:08
Revisions
-
greim renamed this gist
Apr 23, 2016 . 1 changed file with 0 additions and 0 deletions.There are no files selected for viewing
File renamed without changes. -
greim created this gist
Apr 23, 2016 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,75 @@ 'use strict'; /* * Binary search tree with in-order iteration. * http://greim.github.io/gen/dist/00-intro.html */ class Tree { add(value) { if (this.root) this.root.add(value); else this.root = new Node(value); } has(value) { if (this.root) return this.root.has(value); else return false; } delete(value) { if (this.root) this.root.delete(value, this, 'root'); } *[Symbol.iterator]() { if (this.root) yield* this.root; } } class Node { constructor(value) { this.value = value; } add(value) { if (value < this.value) { if (this.left) this.left.add(value); else this.left = new Node(value); } else if (value > this.value) { if (this.right) this.right.add(value); else this.right = new Node(value); } } has(value) { if (value < this.value) { if (this.left) return this.left.has(value); else return false; } else if (value > this.value) { if (this.right) return this.right.has(value); else return false; } else if (value === this.value) { return true; } } delete(value, parent, which) { if (value < this.value) { if (this.left) this.left.delete(value, this, 'left'); } else if (value > this.value) { if (this.right) this.right.delete(value, this, 'right'); } else if (value === this.value) { if (this.left) { let node = this.left; while (node.right) node = node.right; this.value = node.value; this.left.delete(this.value, this, 'left'); } else if (this.right) { let node = this.right; while (node.left) node = node.left; this.value = node.value; this.right.delete(this.value, this, 'right'); } else { delete parent[which]; } } } *[Symbol.iterator]() { if (this.left) yield* this.left; yield this.value; if (this.right) yield* this.right; } }