Last active
September 13, 2019 18:08
-
-
Save greim/17ccec50e8ac45a35edf08efec5fe059 to your computer and use it in GitHub Desktop.
This file contains 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 characters
'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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment