Last active
June 8, 2017 00:41
-
-
Save ConnerAiken/ad31faf979010a04e978c0e82bd8bfa3 to your computer and use it in GitHub Desktop.
Binary search tree example in javascript
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 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